Induksi Matematika

Dalam matematika, induksi matematika merupakan sebuah dasar aksioma bagi beberapa teorema yang melibatkan bilangan asli. Pembuktian suatu pernyataan matematis dengan induksi matematika dilakukan pada objek matematika yang bersifat diskrit, misalnya teori bilangan, teori graf, dan kombinatorika. Matematikawan menggunakan induksi matematika untuk menjelaskan pernyataan matematika yang telah diketahui kebenarannya.

Prinsip induksi matematis dapat dijelaskan secara umum dalam dua tahap yaitu langkah awal atau asumsi induktif dan langkah induksi dasar. Penggunaan induksi matematika utamanya dilakukan pada tiga jenis masalah matematika yaitu seri umum, habis dibagi dan ketidaksetaraan. Kemampuan pembuktian induksi matematika secara benar ditentukan oleh tingkat pemahaman konsep. Setiap prosedur induksi matematika yang digunakan pada suatu konsep matematika dapat ditentukan melalui pemahaman relasional.

Teorema matematika didasarkan pada sekumpulan aksioma dan definisi. Pembuktian semua jenis teorema dilakukan dengan menggunakan aksioma dan definisi, atau menggunakan teorema-teorema yang telah terbukti kebenarannya. Teorema dalam matematika tidak didasarkan kepada hasil-hasil eksperimen yang tidak dapat dibuktikan kebenarannya. Matematika tidak dapat menerima argumentasi bahwa suatu pernyataan matematis adalah benar hanya dengan eksperimen-eksperimen dan observasi-observasi. Pierre de Fermat (1601- 1665) membuktikan bahwa pada konjektur Fermat, persamaan tidak akan menghasilkan bilangan bulat berbentuk positif pada sebarang bilangan bulat yang bernilai lebih dari 2. Para matematikawan memerlukan waktu lebih dari tiga abad untuk menemukan pembuktian konjektur Fermat. Pada tahun 1994, konjektur Fermat dibuktikan oleh matematikawan berkebangsaan Inggris yaitu Andrew Wiles.

 

Sejarah penggunaan induksi matematika dijelaskan oleh Bussey dalam artikel yang ditulisnya pada tahun 1917. Dalam artikel tersebut dijelaskan bahwa proses induksi matematika telah digunakan untuk pertama kali oleh D. Franciscus Maurolycus (1494- 1575). Maurolycus adalah matewatikawan berkebangsaan Italia dan kenalan dari Blaise Pascal (1623-1662). Penggunaan induksi matematika dilakukan oleh Maurolycus dalam bukunya yang terbit pada tahun 1575. Maurolycus menggunakan induksi matematika untuk membuktikan bahwa bilangan-bilangan ganjil terbentuk dengan cara berturut-turut menambahkan 2 terhadap bilangan ganjil pertama, yaitu 1. Pembuktikan lain yang diperolehnya dengan induksi yaitu jumlah n bilangan ganjil pertama adalah kuadrat n. Pembuktian matematika yang dilakukan oleh Pascal maupun Maurolycus tidak pernah menggunakan istilah induksi. Istilah induksi digunakan pertama kalinya pada tahun 1956 oleh John Wallis. Dalam bukunya yang berjudul Arithmetica Infinitorum, Wallis menggunakan isitlah per modum inductionis. Pada tahun 1838, Augustus de Morgan (1806-1871) memperkenalkan istilah induksi matematika ke publik melalui artikel induction yang ditulisnya untuk jurnal Penny Cyclopedia.

Pada tahun 1889, Giuseppe Peano (1858-1932) merumuskan prinsip induksi matematika ke dalam lima aksioma. Di dalam kelima aksioma ini, disajikan definisi lengkap tentang bilangan asli. Kelima aksioma tersebut adalah:

1. 1 adalah bilangan asli.
2. Terdapat satu bilang turutan yang unik dan bentuk bilangan asli pada setiap bilangan asli.
3. Bilangan turutan yang sama mustahil ditemukan pada dua bilangan asli yang berbeda.
4. 1 bukan merupakan turutan dari sebarang bilangan asli
5. Sifat yang dimiliki oleh 1 dan turutan semua bilangan asli, pasti dimiliki juga oleh semua bilangan asli.

Dalam pembuktian tidak langsung, induksi matematika melibatkan dua proposisi, yaitu basis induksi dan hipotesis induksi. Pembuktian dilakukan dalam tiga langkah yaitu langkah basis, hipotesis induksi, dan langkah induksi.

Pembuktian cara induksi matematika ingin membuktikan bahwa teori atau sifat itu benar untuk semua bilangan asli atau semua bilangan dalam himpunan bagiannya. Caranya ialah dengan menunjukkan bahwa sifat itu benar untuk n = 1 (atau S(1) adalah benar), kemudian ditunjukkan bahwa bila sifat itu benar untuk n = k (bila S(k) benar) menyebabkan sifat itu benar untuk n = k + 1 (atau S(k + 1) benar).

Bilangan (termasuk jumlah deret)

• Buktikan bahwa ${\displaystyle 1+3+5+\cdots +2n-1=n^{2}}$  untuk jumlah n bilangan ganjil pertama adalah n²!

Persamaan yang perlu dibuktikan:

${\displaystyle S(n)=1+3+5+\cdots +2n-1=n^{2}}$ 

Langkah pembuktian pertama:
untuk ${\displaystyle n=1}$ , benar bahwa ${\displaystyle \ S(1)=1^{2}=1}$ 

Langkah pembuktian kedua:
andaikan benar untuk ${\displaystyle n=k}$ , yaitu

${\displaystyle S(k)=1+3+5+\cdots +2k-1=k^{2}}$ , maka akan dibuktikan benar pula untuk ${\displaystyle n=k+1}$ , yaitu

${\displaystyle S(k+1)=1+3+5+\cdots +2k-1+2(k+1)-1=(k+1)^{2}}$ 

sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa ${\displaystyle k^{2}=1+3+5+...+2k-1}$  sesuai dengan pengandaian awal

${\displaystyle [1+3+5+\cdots +2k-1]+2(k+1)-1=k^{2}+2(k+1)-1}$ 

kemudian padankan bentuk sederhana tadi dengan sebelah kanan

${\displaystyle k^{2}+2(k+1)-1=(k+1)^{2}}$ 
${\displaystyle \ k^{2}+2k+1=(k+1)^{2}}$ , ingat bahwa ${\displaystyle (k+1)^{2}=k^{2}+2k+1}$ 
${\displaystyle \ (k+1)^{2}=(k+1)^{2}}$  (terbukti benar)

Kesimpulan:
Jadi, ${\displaystyle S(n)}$  benar untuk jumlah n bilangan ganjil pertama adalah n² karena memenuhi kedua langkah pembuktian

• Buktikan bahwa ${\displaystyle 1+2+3+4+5+\cdots +n={\frac {n(n+1)}{2}}}$  untuk setiap bilangan bulat positif adalah n!

Persamaan yang perlu dibuktikan:

${\displaystyle S(n)=1+2+3+4+5+\cdots +n={\frac {n(n+1)}{2}}}$ 

Langkah pembuktian pertama:
untuk ${\displaystyle n=1}$ , benar bahwa ${\displaystyle \ S(1)={\frac {1(1+1)}{2}}=1}$ 

Langkah pembuktian kedua:
andaikan benar untuk ${\displaystyle n=k}$ , yaitu

${\displaystyle S(k)=1+2+3+4+5+\cdots +k={\frac {k(k+1)}{2}}}$ , maka akan dibuktikan benar pula untuk ${\displaystyle n=k+1}$ , yaitu

${\displaystyle S(k+1)=1+2+3+4+5+\cdots +k+k+1={\frac {(k+1)[(k+1)+1]}{2}}}$ 

sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa ${\displaystyle {\frac {k(k+1)}{2}}=1+2+3+4+5+\cdots +k}$  sesuai dengan pengandaian awal

${\displaystyle [1+2+3+4+5+\cdots +k]+k+1={\frac {k(k+1)}{2}}+k+1}$ 

kemudian padankan bentuk sederhana tadi dengan sebelah kanan

${\displaystyle {\frac {k(k+1)}{2}}+k+1={\frac {(k+1)[(k+1)+1]}{2}}}$ 
${\displaystyle (k+1)({\frac {k}{2}}+1)={\frac {(k+1)[(k+1)+1]}{2}}}$ 
${\displaystyle (k+1)({\frac {k+2}{2}})={\frac {(k+1)[(k+1)+1]}{2}}}$ 
${\displaystyle {\frac {(k+1)[(k+1)+1]}{2}}={\frac {(k+1)[(k+1)+1]}{2}}}$ 
${\displaystyle {\frac {(k+1)[(k+1)+1]}{2}}={\frac {(k+1)[(k+1)+1]}{2}}}$  (terbukti benar)

Kesimpulan:
Jadi, ${\displaystyle S(n)}$  benar untuk setiap bilangan bulat positif adalah n karena memenuhi kedua langkah pembuktian

Pertidaksamaan

• Buktikan bahwa ${\displaystyle 4n<2^{n}}$  untuk semua bilangan bulat positif n ≥ 5!

Persamaan yang perlu dibuktikan:

${\displaystyle S(n)=4n<2^{n}}$ 

Langkah pembuktian pertama:
untuk ${\displaystyle n=5}$ , benar bahwa ${\displaystyle 4(5)<2^{5}}$ 

Langkah pembuktian kedua:
andaikan benar untuk ${\displaystyle n=k}$ , yaitu

${\displaystyle S(k)=4k<2^{k}}$ , maka akan dibuktikan benar pula untuk ${\displaystyle n=k+1}$ , yaitu

${\displaystyle S(k+1)=4(k+1)<2^{k+1}}$ 

sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa ${\displaystyle 4k}$  sesuai dengan pengandaian awal

${\displaystyle 4(k+1)=4k+4}$  (karena 4 < 4k)
${\displaystyle =4k+4k}$ 

kemudian padankan bentuk sederhana tadi dengan sebelah kanan

${\displaystyle 4k+4k<2^{k+1}}$ 
${\displaystyle 2(4k)<2^{k+1}}$ 
${\displaystyle 2(2^{k})<2^{k+1}}$ , ingat bahwa ${\displaystyle a^{m}a^{n}=a^{m+n}}$ 
${\displaystyle 2^{k+1}<2^{k+1}}$  (terbukti benar)

Kesimpulan:
Jadi, ${\displaystyle S(n)}$  benar untuk semua bilangan bulat positif n ≥ 5 karena memenuhi kedua langkah pembuktian

Faktor (termasuk kali atau bagi)

• Buktikan bahwa salah satu faktor dari ${\displaystyle n^{3}+3n^{2}+2n}$  adalah 3 untuk semua bilangan bulat positif n!

Persamaan yang perlu dibuktikan:

${\displaystyle S(n)=n^{3}+3n^{2}+2n}$ 

Langkah pembuktian pertama:
untuk ${\displaystyle n=1}$ , benar bahwa ${\displaystyle 1^{3}+3(1)^{2}+2(1)=6}$ 

Langkah pembuktian kedua:
andaikan benar untuk ${\displaystyle n=k}$ , yaitu

${\displaystyle k^{3}+3k^{2}+2k}$ , maka akan dibuktikan benar pula untuk ${\displaystyle n=k+1}$ , yaitu

${\displaystyle (k+1)^{3}+3(k+1)^{2}+2(k+1)}$ 

sekarang tunjukkan bahwa 3 adalah faktor dari ${\displaystyle (k+1)^{3}+3(k+1)^{2}+2(k+1)}$ 

${\displaystyle (k+1)^{3}+3(k+1)^{2}+2(k+1)=k^{3}+3k^{2}+3k+1+3k^{2}+6k+3+2k+2}$ 
${\displaystyle =(k^{3}+3k^{2}+2k)+(3k^{2}+9k+6)}$ 
${\displaystyle =(k^{3}+3k^{2}+2k)+3\cdot (k^{2}+3k+2)}$ 

karena 3 adalah faktor dari ${\displaystyle 3\cdot (k^{2}+3k+2)}$  dan 3 juga merupakan faktor ${\displaystyle k^{3}+3k^{2}+2k}$ , maka 3 adalah faktor dari ${\displaystyle (k+1)^{3}+3(k+1)^{2}+2(k+1)}$ . Dengan menggabungkan hasil pada langkah pembuktian 1 dan 2.

Kesimpulan:
Jadi, ${\displaystyle S(n)}$  benar untuk 3 adalah faktor ${\displaystyle n^{3}+3n^{2}+2n}$  untuk semua bilangan bulat positif n karena memenuhi kedua langkah pembuktian

• Buktikan bahwa 3 adalah faktor ${\displaystyle 4^{n}-1}$  untuk semua bilangan bulat positif n!

Persamaan yang perlu dibuktikan:

${\displaystyle S(n)=4^{n}-1}$ 

Langkah pembuktian pertama:
untuk ${\displaystyle n=1}$ , benar bahwa ${\displaystyle 4^{1}-1=3}$ 

Langkah pembuktian kedua:
andaikan benar untuk ${\displaystyle n=k}$ , yaitu

${\displaystyle 4^{k}-1}$ , maka akan dibuktikan benar pula untuk ${\displaystyle n=k+1}$ , yaitu

${\displaystyle 4^{k+1}-1}$ 

sekarang tunjukkan bahwa 3 adalah faktor dari ${\displaystyle 4^{k+1}-1}$ 

${\displaystyle 4^{k+1}-1=4^{k+1}-4^{k}+4^{k}-1}$ 
${\displaystyle =4^{k}(4-1)+(4^{k}-1)}$ 
${\displaystyle =4^{k}\cdot 3+(4^{k}-1)}$ 

karena 3 adalah faktor dari ${\displaystyle 4k\cdot 3}$  dan 3 juga merupakan faktor ${\displaystyle 4^{k}-1}$ , maka 3 adalah faktor dari ${\displaystyle 4^{k+1}-1}$ . Dengan menggabungkan hasil pada langkah pembuktian 1 dan 2.

Kesimpulan:
Jadi, ${\displaystyle S(n)}$  benar untuk 3 adalah faktor ${\displaystyle 4^{n}-1}$  untuk semua bilangan bulat positif n karena memenuhi kedua langkah pembuktian

• Buktikan bahwa ${\displaystyle 5^{n}-1}$  habis dibagi 4 untuk semua bilangan bulat positif n!

Persamaan yang perlu dibuktikan:

${\displaystyle S(n)=5^{n}-1}$ 

Langkah pembuktian pertama:
untuk ${\displaystyle n=1}$ , benar bahwa ${\displaystyle 5^{1}-1=4}$ 

Langkah pembuktian kedua:
andaikan benar untuk ${\displaystyle n=k}$ , yaitu

${\displaystyle 5^{k}-1}$ , maka akan dibuktikan benar pula untuk ${\displaystyle n=k+1}$ , yaitu

${\displaystyle 5^{k+1}-1}$ 

sekarang tunjukkan bahwa ${\displaystyle 5^{k+1}-1}$  habis dibagi 4

${\displaystyle 5^{k+1}-1=5^{k+1}-5^{k}+5^{k}-1}$ 
${\displaystyle =5^{k}(5-1)+(5^{k}-1)}$ 
${\displaystyle =5^{k}\cdot 4+(5^{k}-1)}$ 

karena ${\displaystyle 5k\cdot 4}$  dan ${\displaystyle 5^{k}-1}$  habis dibagi 4, maka ${\displaystyle 5^{k+1}-1}$  habis dibagi 4. Dengan menggabungkan hasil pada langkah pembuktian 1 dan 2.

Kesimpulan:
Jadi, ${\displaystyle S(n)}$  benar untuk ${\displaystyle 5^{n}-1}$  habis dibagi 4 untuk semua bilangan bulat positif n karena memenuhi kedua langkah pembuktian

Faktorisasi

• Buktikan bahwa x - y adalah faktor ${\displaystyle x^{n}-y^{n}}$  untuk semua bilangan bulat positif n!

Persamaan yang perlu dibuktikan:

${\displaystyle S(n)=x^{n}-y^{n}}$ 

Langkah pembuktian pertama:
untuk ${\displaystyle n=1}$ , benar bahwa ${\displaystyle x^{1}-y^{1}=x-y}$ 

Langkah pembuktian kedua:
andaikan benar untuk ${\displaystyle n=k}$ , yaitu

${\displaystyle x^{k}-y^{k}}$ , maka akan dibuktikan benar pula untuk ${\displaystyle n=k+1}$ , yaitu

${\displaystyle x^{k+1}-y^{k+1}}$ 

sekarang tunjukkan bahwa x - y adalah faktor dari ${\displaystyle x^{k+1}-y^{k+1}}$ 

${\displaystyle x^{k+1}-y^{k+1}=x^{k+1}-x^{k}y+x^{k}y-y^{k+1}}$ 
${\displaystyle =x^{k}(x-y)+(x^{k}-y^{k})y}$ 

karena x - y adalah faktor dari ${\displaystyle x^{k}\cdot (x-y)}$  dan x - y juga merupakan faktor ${\displaystyle (x^{k}-y^{k})\cdot y}$ , maka x - y adalah faktor dari ${\displaystyle x^{k+1}-y^{k+1}}$ . Dengan menggabungkan hasil pada langkah pembuktian 1 dan 2.

Kesimpulan:
Jadi, ${\displaystyle S(n)}$  benar untuk x - y adalah faktor ${\displaystyle x^{n}-y^{n}}$  untuk semua bilangan bulat positif n karena memenuhi kedua langkah pembuktian

Barisan

Temukan hasil rumus untuk penjumlahan berhingga berikut kemudian buktikan hasil rumus tersebut dengan induksi matematika!

${\displaystyle {\frac {1}{4}}+{\frac {1}{12}}+{\frac {1}{24}}+\cdots +{\frac {1}{2n(n+1)}}}$ 

Persamaan yang perlu dibuktikan:

${\displaystyle S(n)={\frac {1}{4}}+{\frac {1}{12}}+{\frac {1}{24}}+\cdots +{\frac {1}{2n(n+1)}}}$ 

Langkah pembuktian pertama:
untuk beberapa penjumlahan ${\displaystyle n}$  dari pertama, benar bahwa

${\displaystyle S(1)={\frac {1}{4}}={\frac {1^{2}}{2(1)(1+1)}}}$ 
${\displaystyle S(2)={\frac {1}{4}}+{\frac {1}{12}}={\frac {4}{12}}={\frac {2^{2}}{2(2)(2+1)}}}$ 
${\displaystyle S(3)={\frac {1}{4}}+{\frac {1}{12}}+{\frac {1}{24}}={\frac {9}{24}}={\frac {3^{2}}{2(3)(3+1)}}}$ 
${\displaystyle S(4)={\frac {1}{4}}+{\frac {1}{12}}+{\frac {1}{24}}+{\frac {1}{40}}={\frac {16}{40}}={\frac {4^{2}}{2(4)(4+1)}}}$ 

Langkah pembuktian kedua:
andaikan benar untuk ${\displaystyle n=k}$ , yaitu

${\displaystyle S(k)={\frac {1}{4}}+{\frac {1}{12}}+{\frac {1}{24}}+\cdots +{\frac {1}{2k(k+1)}}={\frac {k^{2}}{2k(k+1)}}}$ , maka akan dibuktikan benar pula untuk ${\displaystyle n=k+1}$ , yaitu

${\displaystyle S(k+1)={\frac {1}{4}}+{\frac {1}{12}}+{\frac {1}{24}}+\cdots +{\frac {1}{2k(k+1)}}+{\frac {1}{2(k+1)((k+1)+1)}}={\frac {(k+1)^{2}}{2(k+1)[(k+1)+1]}}}$ 

sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa ${\displaystyle {\frac {k^{2}}{2k(k+1)}}={\frac {1}{4}}+{\frac {1}{12}}+{\frac {1}{24}}+\cdots +{\frac {1}{2k(k+1)}}}$  sesuai dengan pengandaian awal

${\displaystyle [{\frac {1}{4}}+{\frac {1}{12}}+{\frac {1}{24}}+\cdots +{\frac {1}{2k(k+1)}}]+{\frac {1}{2(k+1)[(k+1)+1]}}={\frac {k^{2}}{2k(k+1)}}+{\frac {1}{2(k+1)[(k+1)+1]}}}$ 

kemudian padankan bentuk sederhana tadi dengan sebelah kanan

${\displaystyle {\frac {k^{2}}{2k(k+1)}}+{\frac {1}{2(k+1)((k+1)+1)}}={\frac {(k+1)^{2}}{2(k+1)[(k+1)+1]}}}$ 
${\displaystyle {\frac {k^{2}}{2k(k+1)}}+{\frac {1}{2(k+1)(k+2)}}={\frac {(k+1)^{2}}{2(k+1)[(k+1)+1]}}}$ 
${\displaystyle {\frac {k^{2}(k+2)+k}{2k(k+1)(k+2)}}={\frac {(k+1)^{2}}{2(k+1)[(k+1)+1]}}}$ 
${\displaystyle {\frac {k(k^{2}+2k+1)}{2k(k+1)(k+2)}}={\frac {(k+1)^{2}}{2(k+1)[(k+1)+1]}}}$ 
${\displaystyle {\frac {(k+1)^{2}}{2(k+1)[(k+1)+1]}}={\frac {(k+1)^{2}}{2(k+1)[(k+1)+1]}}}$  (terbukti benar)

Kesimpulan:
Jadi, ${\displaystyle S(n)}$  benar untuk hipotesis induksi matematika karena memenuhi kedua langkah pembuktian

Misalkan S(n) adalah pernyataan yang didefinisikan untuk bilangan bulat n, dan misalkan a dan b adalah bilangan bulat sedemikian sehingga a ≤ b. Jika dua pernyataan berikut bernilai benar,

S(a), S(a + 1), ..., dan S(b) semuanya bernilai benar. (langkah dasar) Untuk sebarang bilangan bulat k ≥ b, jika S(i) benar untuk semua bilangan bulat i mulai a sampai k, maka S(k + 1) benar. (langkah induksi)

Maka untuk semua bilangan bulat n ≥ a, S(n) benar. (Asumsi bahwa S(i) benar untuk semua bilangan bulat i mulai dari a sampai k disebut sebagai hipotesis induksi. Cara lain untuk menyatakan hipotesis induksi adalah dengan menyatakan bahwa S(a), S(a + 1), ..., S(k) semuanya bernilai benar.)

A. Bilangan (termasuk jumlah deret)

B. Barisan

C. Teori

Penalaran pada matematika formal

Induksi matematika digunakan untuk mengatasi kelemahan dari penalaran induktif. Penggunaan induksi matematika dapat memberikan kesimpulan yang berlaku umum. Sebaliknya, penalaran induktif yang dilakukan melalui pengalaman dan pengamatan, tidak menjamin adanya kesimpulan yang berlaku secara umum. Kesimpulan yang berlaku secara umum di dalam matematika formal hanya dapat diperoleh melalui induksi matematika.