Matematika SMA/MA/SMK/MAK
Induksi Matematika
Pembuktian kebenaran pernyataan matematika untuk semua bilangan asli
A. Pengertian Induksi Matematika
Induksi Matematika adalah suatu metode pembuktian matematis yang digunakan untuk membuktikan bahwa suatu pernyataan \(P(n)\) bernilai benar untuk semua bilangan asli \(n \geq n_0\), di mana \(n_0\) biasanya bernilai 1.
Prinsip Induksi Matematika terdiri dari dua langkah utama:
Langkah-langkah Induksi Matematika
- Langkah Basis (Basis Step): Buktikan bahwa pernyataan \(P(n_0)\) benar untuk nilai awal, biasanya \(n = 1\).
- Langkah Induksi (Inductive Step): Asumsikan bahwa \(P(k)\) benar untuk suatu bilangan asli \(k\) (disebut hipotesis induksi), kemudian buktikan bahwa \(P(k+1)\) juga benar.
Jika kedua langkah terpenuhi, maka \(P(n)\) benar untuk semua \(n \geq n_0\).
Perhatikan pola penjumlahan bilangan asli berikut:
| \(n\) | Penjumlahan | Hasil | \(\frac{n(n+1)}{2}\) |
|---|---|---|---|
| 1 | 1 | 1 | \(\frac{1 \cdot 2}{2} = 1\) |
| 2 | 1+2 | 3 | \(\frac{2 \cdot 3}{2} = 3\) |
| 3 | 1+2+3 | 6 | \(\frac{3 \cdot 4}{2} = 6\) |
| 4 | 1+2+3+4 | 10 | \(\frac{4 \cdot 5}{2} = 10\) |
| 5 | 1+2+3+4+5 | 15 | \(\frac{5 \cdot 6}{2} = 15\) |
Amati bahwa rumus \(1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\) tampaknya selalu benar. Namun, kita tidak bisa menguji untuk semua bilangan asli satu per satu. Disinilah Induksi Matematika berperan.
- Mengapa kita tidak cukup membuktikan suatu pernyataan dengan menguji beberapa nilai saja?
- Bagaimana cara memastikan suatu rumus berlaku untuk semua bilangan asli?
- Apa yang terjadi jika langkah basis gagal?
- Mengapa langkah induksi menggunakan asumsi \(P(k)\) benar?
Analogi Induksi Matematika sering digambarkan seperti efek domino:
🎯 Langkah Basis = Menjatuhkan domino pertama
🔗 Langkah Induksi = Memastikan setiap domino yang jatuh akan menjatuhkan domino berikutnya
✅ Kesimpulan = Semua domino pasti jatuh
Secara logis, jika kita tahu domino pertama jatuh (basis), dan setiap domino yang jatuh pasti menjatuhkan yang berikutnya (induksi), maka semua domino akan jatuh (semua \(P(n)\) benar).
B. Struktur Pembuktian Induksi Matematika
Berikut format baku penulisan pembuktian dengan Induksi Matematika:
Buktikan: \(P(n)\) benar untuk semua \(n \geq 1\)
Langkah 1: Basis Induksi
Untuk \(n = 1\): Tunjukkan bahwa \(P(1)\) benar.
Langkah 2: Hipotesis Induksi
Asumsikan \(P(k)\) benar untuk suatu bilangan asli \(k\).
Langkah 3: Langkah Induksi
Buktikan bahwa \(P(k+1)\) benar dengan menggunakan hipotesis induksi.
Kesimpulan:
Karena langkah basis dan langkah induksi terpenuhi, maka \(P(n)\) benar untuk semua \(n \geq 1\). ∎
Mari kita coba buktikan pernyataan sederhana:
Pernyataan: Buktikan bahwa \(1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\) untuk semua \(n \geq 1\).
Langkah 1: Basis (\(n = 1\))
Ruas kiri: \(1\)
Ruas kanan: \(\frac{1(1+1)}{2} = \frac{2}{2} = 1\)
Ruas kiri = Ruas kanan ✓, jadi \(P(1)\) benar.
Langkah 2: Hipotesis Induksi
Asumsikan \(P(k)\) benar: \(1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}\)
Langkah 3: Buktikan \(P(k+1)\)
Kita perlu menunjukkan: \(1 + 2 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}\)
Ruas kiri: \(\underbrace{1 + 2 + \cdots + k}_{\frac{k(k+1)}{2}} + (k+1)\)
\(= \frac{k(k+1)}{2} + (k+1)\)
\(= \frac{k(k+1) + 2(k+1)}{2}\)
\(= \frac{(k+1)(k+2)}{2}\)
Ini sama dengan ruas kanan \(P(k+1)\). ✓
Kesimpulan: \(P(n)\) benar untuk semua \(n \geq 1\). ∎
Setelah memahami contoh di atas, jelaskan dengan bahasa sendiri:
- Mengapa langkah basis penting dalam pembuktian induksi?
- Apa fungsi hipotesis induksi dalam langkah pembuktian?
- Bagaimana hubungan antara \(P(k)\) dan \(P(k+1)\)?
C. Jenis-Jenis Pernyataan yang Dibuktikan
Induksi Matematika umumnya digunakan untuk membuktikan:
1. Rumus Penjumlahan (Sigma)
Contoh: \(\displaystyle\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}\)
2. Ketidaksamaan (Pertidaksamaan)
Contoh: \(2^n > n\) untuk semua \(n \geq 1\)
3. Sifat Keterbagian (Divisibilitas)
Contoh: \(n^3 – n\) habis dibagi 6 untuk semua \(n \geq 1\)
4. Rumus Deret dan Barisan
Contoh: \(1 + 3 + 5 + \cdots + (2n-1) = n^2\)
D. Contoh Soal dan Pembahasan
MUDAH Contoh Soal Tingkat Mudah
Contoh 1
Buktikan dengan induksi matematika bahwa \(1 + 3 + 5 + \cdots + (2n-1) = n^2\) untuk semua \(n \geq 1\).
Pembahasan:
Langkah 1: Basis (\(n = 1\))
Ruas kiri: \(2(1)-1 = 1\)
Ruas kanan: \(1^2 = 1\)
RK = RKn ✓
Langkah 2: Hipotesis Induksi
Asumsikan benar untuk \(n=k\): \(1+3+5+\cdots+(2k-1) = k^2\)
Langkah 3: Buktikan \(P(k+1)\)
Tunjukkan: \(1+3+5+\cdots+(2k-1)+(2(k+1)-1) = (k+1)^2\)
\(= k^2 + (2k+1)\) (menggunakan hipotesis)
\(= k^2 + 2k + 1 = (k+1)^2\) ✓
Terbukti. ∎
Contoh 2
Buktikan bahwa \(2 + 4 + 6 + \cdots + 2n = n(n+1)\) untuk semua \(n \geq 1\).
Pembahasan:
Langkah 1: Basis (\(n = 1\))
Ruas kiri: \(2(1) = 2\)
Ruas kanan: \(1(1+1) = 2\) ✓
Langkah 2: Hipotesis Induksi
Asumsikan: \(2+4+6+\cdots+2k = k(k+1)\)
Langkah 3: Buktikan \(P(k+1)\)
\(2+4+\cdots+2k+2(k+1)\)
\(= k(k+1) + 2(k+1)\)
\(= (k+1)(k+2)\)
\(= (k+1)((k+1)+1)\) ✓
Terbukti. ∎
Contoh 3
Buktikan bahwa \(1 + 2 + 4 + 8 + \cdots + 2^{n-1} = 2^n – 1\) untuk semua \(n \geq 1\).
Pembahasan:
Langkah 1: Basis (\(n = 1\))
Ruas kiri: \(2^{1-1} = 2^0 = 1\)
Ruas kanan: \(2^1 – 1 = 1\) ✓
Langkah 2: Hipotesis Induksi
Asumsikan: \(1+2+4+\cdots+2^{k-1} = 2^k – 1\)
Langkah 3: Buktikan \(P(k+1)\)
\(1+2+4+\cdots+2^{k-1}+2^k\)
\(= (2^k – 1) + 2^k\)
\(= 2 \cdot 2^k – 1 = 2^{k+1} – 1\) ✓
Terbukti. ∎
Contoh 4
Buktikan bahwa \(n < 2^n\) untuk semua \(n \geq 1\).
Pembahasan:
Langkah 1: Basis (\(n = 1\))
\(1 < 2^1 = 2\) ✓
Langkah 2: Hipotesis Induksi
Asumsikan: \(k < 2^k\)
Langkah 3: Buktikan \(k+1 < 2^{k+1}\)
\(k + 1 < 2^k + 1\) (dari hipotesis: \(k < 2^k\))
\(\leq 2^k + 2^k\) (karena \(1 \leq 2^k\) untuk \(k \geq 1\))
\(= 2 \cdot 2^k = 2^{k+1}\) ✓
Terbukti. ∎
Contoh 5
Buktikan bahwa \(3^n – 1\) habis dibagi 2 untuk semua \(n \geq 1\).
Pembahasan:
Langkah 1: Basis (\(n = 1\))
\(3^1 – 1 = 2\), dan \(2\) habis dibagi 2. ✓
Langkah 2: Hipotesis Induksi
Asumsikan \(3^k – 1\) habis dibagi 2, artinya \(3^k – 1 = 2m\) untuk suatu bilangan bulat \(m\).
Langkah 3: Buktikan \(3^{k+1} – 1\) habis dibagi 2
\(3^{k+1} – 1 = 3 \cdot 3^k – 1\)
\(= 3(3^k – 1) + 3 – 1\)
\(= 3(2m) + 2\)
\(= 6m + 2 = 2(3m + 1)\)
Ini habis dibagi 2. ✓
Terbukti. ∎
SEDANG Contoh Soal Tingkat Sedang
Contoh 6
Buktikan bahwa \(\displaystyle\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}\) untuk semua \(n \geq 1\).
Pembahasan:
Langkah 1: Basis (\(n = 1\))
Ruas kiri: \(1^2 = 1\)
Ruas kanan: \(\frac{1 \cdot 2 \cdot 3}{6} = 1\) ✓
Langkah 2: Hipotesis Induksi
Asumsikan: \(1^2+2^2+\cdots+k^2 = \frac{k(k+1)(2k+1)}{6}\)
Langkah 3: Buktikan \(P(k+1)\)
\(1^2+2^2+\cdots+k^2+(k+1)^2\)
\(= \frac{k(k+1)(2k+1)}{6} + (k+1)^2\)
\(= \frac{k(k+1)(2k+1) + 6(k+1)^2}{6}\)
\(= \frac{(k+1)[k(2k+1) + 6(k+1)]}{6}\)
\(= \frac{(k+1)(2k^2+7k+6)}{6}\)
\(= \frac{(k+1)(k+2)(2k+3)}{6}\)
\(= \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}\) ✓
Terbukti. ∎
Contoh 7
Buktikan bahwa \(\displaystyle\sum_{i=1}^{n} i^3 = \left[\frac{n(n+1)}{2}\right]^2\) untuk semua \(n \geq 1\).
Pembahasan:
Langkah 1: Basis (\(n = 1\))
Ruas kiri: \(1^3 = 1\)
Ruas kanan: \(\left[\frac{1 \cdot 2}{2}\right]^2 = 1\) ✓
Langkah 2: Hipotesis Induksi
Asumsikan: \(1^3+2^3+\cdots+k^3 = \left[\frac{k(k+1)}{2}\right]^2\)
Langkah 3: Buktikan \(P(k+1)\)
\(1^3+2^3+\cdots+k^3+(k+1)^3\)
\(= \left[\frac{k(k+1)}{2}\right]^2 + (k+1)^3\)
\(= (k+1)^2\left[\frac{k^2}{4} + (k+1)\right]\)
\(= (k+1)^2 \cdot \frac{k^2+4k+4}{4}\)
\(= (k+1)^2 \cdot \frac{(k+2)^2}{4}\)
\(= \left[\frac{(k+1)(k+2)}{2}\right]^2\) ✓
Terbukti. ∎
Contoh 8
Buktikan bahwa \(n^2 + n\) habis dibagi 2 untuk semua \(n \geq 1\).
Pembahasan:
Langkah 1: Basis (\(n = 1\))
\(1^2 + 1 = 2\), habis dibagi 2. ✓
Langkah 2: Hipotesis Induksi
Asumsikan \(k^2+k\) habis dibagi 2, yakni \(k^2+k = 2m\).
Langkah 3: Buktikan \((k+1)^2+(k+1)\) habis dibagi 2
\((k+1)^2+(k+1) = k^2+2k+1+k+1\)
\(= (k^2+k) + 2k + 2\)
\(= 2m + 2(k+1)\)
\(= 2(m+k+1)\), habis dibagi 2. ✓
Terbukti. ∎
Contoh 9
Buktikan bahwa \(\displaystyle\sum_{i=1}^{n} \frac{1}{i(i+1)} = \frac{n}{n+1}\) untuk semua \(n \geq 1\).
Pembahasan:
Langkah 1: Basis (\(n = 1\))
Ruas kiri: \(\frac{1}{1 \cdot 2} = \frac{1}{2}\)
Ruas kanan: \(\frac{1}{1+1} = \frac{1}{2}\) ✓
Langkah 2: Hipotesis Induksi
Asumsikan: \(\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+\cdots+\frac{1}{k(k+1)} = \frac{k}{k+1}\)
Langkah 3: Buktikan \(P(k+1)\)
\(\frac{k}{k+1} + \frac{1}{(k+1)(k+2)}\)
\(= \frac{k(k+2)+1}{(k+1)(k+2)}\)
\(= \frac{k^2+2k+1}{(k+1)(k+2)}\)
\(= \frac{(k+1)^2}{(k+1)(k+2)} = \frac{k+1}{k+2}\) ✓
Terbukti. ∎
Contoh 10
Buktikan bahwa \(4^n – 1\) habis dibagi 3 untuk semua \(n \geq 1\).
Pembahasan:
Langkah 1: Basis (\(n = 1\))
\(4^1 – 1 = 3\), habis dibagi 3. ✓
Langkah 2: Hipotesis Induksi
Asumsikan \(4^k – 1\) habis dibagi 3, yakni \(4^k – 1 = 3m\), sehingga \(4^k = 3m + 1\).
Langkah 3: Buktikan \(4^{k+1} – 1\) habis dibagi 3
\(4^{k+1} – 1 = 4 \cdot 4^k – 1\)
\(= 4(3m+1) – 1\)
\(= 12m + 4 – 1\)
\(= 12m + 3 = 3(4m+1)\)
Habis dibagi 3. ✓
Terbukti. ∎
SULIT Contoh Soal Tingkat Sulit
Contoh 11
Buktikan bahwa \(n^3 – n\) habis dibagi 6 untuk semua \(n \geq 1\).
Pembahasan:
Langkah 1: Basis (\(n = 1\))
\(1^3 – 1 = 0 = 6 \cdot 0\), habis dibagi 6. ✓
Langkah 2: Hipotesis Induksi
Asumsikan \(k^3 – k\) habis dibagi 6, yakni \(k^3 – k = 6m\).
Langkah 3: Buktikan \((k+1)^3 – (k+1)\) habis dibagi 6
\((k+1)^3 – (k+1)\)
\(= k^3 + 3k^2 + 3k + 1 – k – 1\)
\(= (k^3 – k) + 3k^2 + 3k\)
\(= 6m + 3k(k+1)\)
Karena \(k(k+1)\) selalu genap (perkalian dua bilangan berurutan), maka \(k(k+1) = 2p\).
\(= 6m + 3(2p) = 6m + 6p = 6(m+p)\)
Habis dibagi 6. ✓
Terbukti. ∎
Contoh 12
Buktikan bahwa \(2^n > n^2\) untuk semua \(n \geq 5\).
Pembahasan:
Langkah 1: Basis (\(n = 5\))
\(2^5 = 32 > 25 = 5^2\) ✓
Langkah 2: Hipotesis Induksi
Asumsikan \(2^k > k^2\) untuk suatu \(k \geq 5\).
Langkah 3: Buktikan \(2^{k+1} > (k+1)^2\)
\(2^{k+1} = 2 \cdot 2^k > 2k^2\) (dari hipotesis)
Perlu ditunjukkan: \(2k^2 \geq (k+1)^2\)
\(2k^2 \geq k^2 + 2k + 1\)
\(k^2 – 2k – 1 \geq 0\)
\(k^2 – 2k – 1 = (k-1)^2 – 2\)
Untuk \(k \geq 5\): \((5-1)^2 – 2 = 14 > 0\) ✓
Jadi \(2^{k+1} > 2k^2 \geq (k+1)^2\) ✓
Terbukti. ∎
Contoh 13
Buktikan bahwa \(\displaystyle\sum_{i=1}^{n} i \cdot i! = (n+1)! – 1\) untuk semua \(n \geq 1\).
Pembahasan:
Langkah 1: Basis (\(n = 1\))
Ruas kiri: \(1 \cdot 1! = 1\)
Ruas kanan: \(2! – 1 = 1\) ✓
Langkah 2: Hipotesis Induksi
Asumsikan: \(1\cdot1! + 2\cdot2! + \cdots + k\cdot k! = (k+1)! – 1\)
Langkah 3: Buktikan \(P(k+1)\)
\(1\cdot1!+2\cdot2!+\cdots+k\cdot k!+(k+1)\cdot(k+1)!\)
\(= [(k+1)!-1] + (k+1)\cdot(k+1)!\)
\(= (k+1)![1+(k+1)] – 1\)
\(= (k+1)!(k+2) – 1\)
\(= (k+2)! – 1\) ✓
Terbukti. ∎
Contoh 14
Buktikan bahwa \(\displaystyle\sum_{i=0}^{n} r^i = \frac{r^{n+1}-1}{r-1}\) untuk \(r \neq 1\) dan semua \(n \geq 0\).
Pembahasan:
Langkah 1: Basis (\(n = 0\))
Ruas kiri: \(r^0 = 1\)
Ruas kanan: \(\frac{r^1-1}{r-1} = \frac{r-1}{r-1} = 1\) ✓
Langkah 2: Hipotesis Induksi
Asumsikan: \(1+r+r^2+\cdots+r^k = \frac{r^{k+1}-1}{r-1}\)
Langkah 3: Buktikan \(P(k+1)\)
\(1+r+\cdots+r^k+r^{k+1}\)
\(= \frac{r^{k+1}-1}{r-1} + r^{k+1}\)
\(= \frac{r^{k+1}-1+r^{k+1}(r-1)}{r-1}\)
\(= \frac{r^{k+1}-1+r^{k+2}-r^{k+1}}{r-1}\)
\(= \frac{r^{k+2}-1}{r-1}\) ✓
Terbukti. ∎
Contoh 15
Buktikan bahwa \(n! > 2^n\) untuk semua \(n \geq 4\).
Pembahasan:
Langkah 1: Basis (\(n = 4\))
\(4! = 24 > 16 = 2^4\) ✓
Langkah 2: Hipotesis Induksi
Asumsikan \(k! > 2^k\) untuk suatu \(k \geq 4\).
Langkah 3: Buktikan \((k+1)! > 2^{k+1}\)
\((k+1)! = (k+1) \cdot k!\)
\(> (k+1) \cdot 2^k\) (dari hipotesis)
Karena \(k \geq 4\), maka \(k+1 \geq 5 > 2\), sehingga:
\((k+1) \cdot 2^k > 2 \cdot 2^k = 2^{k+1}\) ✓
Terbukti. ∎
E. Latihan Soal
Kerjakan soal-soal berikut menggunakan metode Induksi Matematika!
MUDAH
1. Buktikan bahwa \(1+2+3+\cdots+n = \frac{n(n+1)}{2}\) untuk semua \(n \geq 1\).
2. Buktikan bahwa \(3+6+9+\cdots+3n = \frac{3n(n+1)}{2}\) untuk semua \(n \geq 1\).
3. Buktikan bahwa \(1+4+7+\cdots+(3n-2) = \frac{n(3n-1)}{2}\) untuk semua \(n \geq 1\).
4. Buktikan bahwa \(2^n \geq n+1\) untuk semua \(n \geq 1\).
5. Buktikan bahwa \(5^n – 1\) habis dibagi 4 untuk semua \(n \geq 1\).
SEDANG
6. Buktikan bahwa \(\displaystyle\sum_{i=1}^{n} (2i-1)^2 = \frac{n(2n-1)(2n+1)}{3}\) untuk semua \(n \geq 1\).
7. Buktikan bahwa \(\displaystyle\sum_{i=1}^{n} \frac{1}{(2i-1)(2i+1)} = \frac{n}{2n+1}\) untuk semua \(n \geq 1\).
8. Buktikan bahwa \(n^3 + 2n\) habis dibagi 3 untuk semua \(n \geq 1\).
9. Buktikan bahwa \(7^n – 1\) habis dibagi 6 untuk semua \(n \geq 1\).
10. Buktikan bahwa \(\displaystyle\sum_{i=1}^{n} i(i+1) = \frac{n(n+1)(n+2)}{3}\) untuk semua \(n \geq 1\).
SULIT
11. Buktikan bahwa \(n^5 – n\) habis dibagi 5 untuk semua \(n \geq 1\).
12. Buktikan bahwa \(3^{2n} – 1\) habis dibagi 8 untuk semua \(n \geq 1\).
13. Buktikan bahwa \(\displaystyle\sum_{i=1}^{n} \frac{i}{(i+1)!} = 1 – \frac{1}{(n+1)!}\) untuk semua \(n \geq 1\).
14. Buktikan bahwa \((1+x)^n \geq 1 + nx\) untuk semua \(n \geq 1\) dan \(x > -1\) (Ketidaksamaan Bernoulli).
15. Buktikan bahwa \(\displaystyle\sum_{i=1}^{n} i^2 \cdot 2^i = (n^2-2n+3)\cdot 2^{n+1} – 6\) untuk semua \(n \geq 1\).