Rangkuman induksi matematika

INDUKSI MATEMATIKA

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.

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

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

C. 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}$

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(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}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}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

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

E. Barisan

Temukan rumus untuk penjumlahan berhingga berikut kemudian buktikan 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