Induksi matematika

Sebuah deskripsi tidak formal dari induksi matematika dapat diilustrasikan dengan mengacu kepada efek sekuensial dari jatuhnya domino.

Induksi matematika merupakan pembuktian deduktif, meski namanya induksi. Induksi matematika atau disebut juga induksi lengkap sering dipergunakan untuk pernyataan-pernyataan yang menyangkut bilangan-bilangan asli.

Induksi matematika terbagi 2 yaitu umum dan kuat.

Matematika umum

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).

A. Bilangan (termasuk jumlah deret)

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

Persamaan yang perlu dibuktikan:

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

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

Langkah pembuktian kedua:
andaikan benar untuk $n=k$, yaitu

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

$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 $k^{2}=1+3+5+...+2k-1$ sesuai dengan pengandaian awal

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

kemudian padankan bentuk sederhana tadi dengan sebelah kanan

$k^{2}+2(k+1)-1=(k+1)^{2}$

$\ k^{2}+2k+1=(k+1)^{2}$, ingat bahwa $(k+1)^{2}=k^{2}+2k+1$

$\ (k+1)^{2}=(k+1)^{2}$ (terbukti benar)

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

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

Persamaan yang perlu dibuktikan:

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

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

Langkah pembuktian kedua:
andaikan benar untuk $n=k$, yaitu

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

$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 ${\frac {k(k+1)}{2}}=1+2+3+4+5+\cdots +k$ sesuai dengan pengandaian awal

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

kemudian padankan bentuk sederhana tadi dengan sebelah kanan

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

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

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

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

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

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

B. Pertidaksamaan

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

Persamaan yang perlu dibuktikan:

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

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

Langkah pembuktian kedua:
andaikan benar untuk $n=k$, yaitu

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

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

sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa $4k$ sesuai dengan pengandaian awal

$4(k+1)=4k+4$ (karena 4 < 4k)

$=4k+4k$

kemudian padankan bentuk sederhana tadi dengan sebelah kanan

$4k+4k<2^{k+1}$

$2(4k)<2^{k+1}$

$2(2^{k})<2^{k+1}$, ingat bahwa $a^{m}a^{n}=a^{m+n}$

$2^{k+1}<2^{k+1}$ (terbukti benar)

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

C. Faktor (termasuk kali atau bagi)

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

Persamaan yang perlu dibuktikan:

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

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

andaikan benar untuk $n=k$, yaitu

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

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

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

$(k+1)^{3}+3(k+1)^{2}+2(k+1)=k^{3}+3k^{2}+3k+1+3k^{2}+6k+3+2k+2$

$=(k^{3}+3k^{2}+2k)+(3k^{2}+9k+6)$

$=(k^{3}+3k^{2}+2k)+3(k^{2}+3k+2)$

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

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

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

Persamaan yang perlu dibuktikan:

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

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

Langkah pembuktian kedua:
andaikan benar untuk $n=k$, yaitu

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

$4^{k+1}-1$

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

$4^{k+1}-1=4^{k+1}-4^{k}+4^{k}-1$

$=4^{k}(4-1)+(4^{k}-1)$

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

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

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

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

Persamaan yang perlu dibuktikan:

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

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

Langkah pembuktian kedua:
andaikan benar untuk $n=k$, yaitu

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

$5^{k+1}-1$

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

$5^{k+1}-1=5^{k+1}-5^{k}+5^{k}-1$

$=5^{k}(5-1)+(5^{k}-1)$

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

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

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

D. Faktorisasi

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

Persamaan yang perlu dibuktikan:

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

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

Langkah pembuktian kedua:
andaikan benar untuk $n=k$, yaitu

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

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

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

$x^{k+1}-y^{k+1}=x^{k+1}-x^{k}y+x^{k}y-y^{k+1}$

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

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

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

E. Barisan

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

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

Persamaan yang perlu dibuktikan:

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

Langkah pembuktian pertama:
untuk beberapa penjumlahan $n$ dari pertama, benar bahwa

$S(1)={\frac {1}{4}}={\frac {1^{2}}{2(1)(1+1)}}$

$S(2)={\frac {1}{4}}+{\frac {1}{12}}={\frac {4}{12}}={\frac {2^{2}}{2(2)(2+1)}}$

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

$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 $n=k$, yaitu

$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 $n=k+1$, yaitu

$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 ${\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

$[{\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

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

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

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

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

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

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

Matematika kuat

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

Referensi

• Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (edisi ke-3rd). Addison-Wesley. ISBN 0-201-89683-4.  (Section 1.2.1: Mathematical Induction, pp. 11-21.)
• Kolmogorov, Andrey N. (1975). Introductory Real Analysis. Silverman, R. A. (trans., ed.). New York: Dover. ISBN 0-486-61226-0.  (Section 1.3.8: Transfinite induction, pp. 28-29.)
• Franklin, J. (1996). Proof in Mathematics: An Introduction. Sydney: Quakers Hill Press. ISBN 1-876192-00-3.  (Ch. 8.)

History

• Acerbi, F. (2000). "Plato: Parmenides 149a7-c3. A Proof by Complete Induction?". Archive for History of Exact Sciences. 55: 57–76. doi:10.1007/s004070000020. 
• Bussey, W. H. (1917). "The Origin of Mathematical Induction". The American Mathematical Monthly. 24 (5): 199–207. 
• Cajori, Florian (1918). "Origin of the Name "Mathematical Induction"". 25 (5): 197–201. 
• "Could the Greeks Have Used Mathematical Induction? Did They Use It?". Physis. XXXI: 253–265. 1994. 
• Freudenthal, Hans (1953). "Zur Geschichte der vollständigen Induction". Archives Internationales d'Histiore des Sciences. 6: 17–37. 
• Rabinovitch, Nachum L. (1970). "Rabi Levi Ben Gershon and the Origins of Mathematical Induction". Archive for the History of Exact Science. 6: 237–248. doi:10.1007/BF00327237. 
• Rashed, Roshdi (1972). "L'induction mathématique: al-Karajī, as-Samaw'al". Archive for History of Exact Sciences. 9: 1–12. doi:10.1007/BF00348537. 
• Ungure, S. (1991). "Greek Mathematics and Mathematical Induction". Physis. XXVIII: 273–289. 
• Ungure, S. (1994). "Fowling after Induction". Physis. XXXI: 267–272. 
• Vacca, G. (1909). "Maurolycus, the First Discoverer of the Principle of Mathematical Induction". Bulletin of the American Mathematical Society. 16: 70–73. 
• Yadegari, Mohammad (1978). "The Use of Mathematical Induction by Abū Kāmil Shujā' Ibn Aslam (850-930)". Isis. 69 (2): 259–262. 
• Kuntarti, Sri Kurnianingsih (2007). Matematika SMA dan MA jilid 3B untuk Kelas XII Semester II Program IPA. Sulistiyono. Jakarta: Esis. ISBN 978-979-015-297-7. 
• https://ruangles.co.id  Induksi matematika