Induksi Matematika

Induksi matematika ialah suatu metode pembuktian deduktif yang dipakai untuk menunjukan pernyataan matematika yang bergantung pada himpunan bilangan yang terurut rapi (well ordered set), ibarat bilangan orisinil ataupun himpunan bab tak kosong dari bilangan asli.

Perlu ditekankan bahwa induksi matematika hanya dipakai untuk menunjukan kebenaran dari suatu pernyataan atau rumus, bukan untuk menurunkan rumus. Atau lebih tegasnya induksi matematika tidak sanggup dipakai untuk menurunkan atau menemukan rumus.

Berikut beberapa teladan pernyataan matematika yang sanggup dibuktikan dengan induksi matematika :
P(n) : 2 + 4 + 6 + ... + 2n = n(n + 1), n bilangan asli
P(n) : 6ⁿ + 4 habis dibagi 5, untuk n bilangan asli.
P(n) : 4n < 2ⁿ, untuk setiap bilangan orisinil n ≥ 4

Cara yang paling gampang untuk memahami prinsip kerja induksi matematika ialah dengan mengamati pengaruh domino. Kita sanggup mulai dengan mengajukan pertanyaan "kapan semua domino akan jatuh".

Ada dua kondisi yang harus dipenuhi biar semua domino tersebut jatuh.
Pertama : domino 1 harus jatuh.
Kedua : benar bahwa setiap domino yang jatuh akan menjatuhkan sempurna satu domino berikutnya. Artinya jikalau domino 1 jatuh maka domino 2 niscaya jatuh, jikalau domino 2 jatuh maka domino 3 niscaya jatuh dan seterusnya. Secara umum sanggup kita katakan jika domino k jatuh maka domino (k + 1) juga jatuh dan implikasi ini berlaku untuk semua domino.

Jika kedua kondisi diatas telah terpenuhi, sudah dipastikan semua domino akan jatuh.

Prinsip Induksi Matematika

Misalkan P(n) adalah suatu pernyataan yang bergantung pada n. P(n) benar untuk setiap n bilangan orisinil jikalau memenuhi 2 kondisi berikut :

P(1) benar, artinya untuk n = 1 maka P(n) bernilai benar.
Untuk setiap bilangan orisinil k, jikalau P(k) benar maka P(k + 1) juga benar.

Prinsip diatas sanggup diperluas untuk pernyataan yang bergantung pada himpunan bab tak kosong dari bilangan asli.

Perluasan Prinsip Induksi Matematika
Misalkan P(n) adalah suatu pernyataan yang bergantung pada n. P(n) benar untuk setiap bilangan orisinil n ≥ m jikalau memenuhi 2 kondisi berikut :

P(m) benar, artinya untuk n = m, maka P(n) bernilai benar
Untuk setiap bilangan orisinil k ≥ m, jikalau P(k) benar maka P(k + 1) juga benar.

Untuk memperlihatkan P(1) benar, kita cukup mensubstitusikan n = 1 pada P(n). Jika P(n) disajikan dalam bentuk persamaan, berarti ruas kiri harus sama dengan ruas kanan pada dikala n = 1, barulah kita simpulkan P(1) benar. Cara yang sama sanggup kita terapkan untuk memperlihatkan P(m) benar.

Kembali lagi pada kasus domino diatas, biar domino (k + 1) jatuh, terlebih dahulu domino k harus jatuh, barulah implikasi "jika domino k jatuh maka domino (k + 1) jatuh" sanggup terjadi.

Jadi, untuk memperlihatkan implikasi "jika P(k) benar maka P(k + 1) benar", terlebih dulu kita harus menganggap atau mengasumsikan bahwa P(k) benar. Kemudian menurut perkiraan tersebut kita tunjukkan P(k + 1) juga benar. Proses perkiraan P(k) benar ini disebut dengan hipotesis induksi.

Untuk memperlihatkan P(k + 1) benar, sanggup kita mulai dari hipotesis, yaitu dari perkiraan P(k) benar ataupun dari kesimpulan, yaitu dari P(k + 1) itu sendiri.

Langkah-Langkah Pembuktian Induksi Matematika

Dari uraian-uraian diatas, langkah-langkah pembuktian induksi matematika sanggup kita urutkan sebagai berikut :

Langkah dasar : Tunjukkan P(1) benar.
Langkah induksi : Asumsikan P(k) benar untuk sebarang k bilangan asli, lalu tunjukkan P(k+ 1) juga benar menurut perkiraan tersebut.
Kesimpulan : P(n) benar untuk setiap bilangan orisinil n.

Pembuktian Deret

Sebelum masuk pada pembuktian deret, ada beberapa hal yang perlu dipahami dengan baik menyangkut deret.

Jika P(n) : u₁ + u₂ + u₃ + ... + u_n = S_n , maka
P(1) : u₁ = S₁
P(k) : u₁ + u₂ + u₃ + ... + u_k = S_k
P(k + 1) : u₁ + u₂ + u₃ + ... + u_k + u_k+1 = S_k+1

Contoh 1
Buktikan 2 + 4 + 6 + ... + 2n = n(n + 1), untuk setiap n bilangan asli.

Jawab :
P(n) : 2 + 4 + 6 + ... + 2n = n(n + 1)
Akan dibuktikan P(n) benar untuk setiap n ∈ N

Langkah Dasar :
Akan ditunjukkan P(1) benar
2 = 1(1 + 1)
Jadi, P(1) benar

Langkah Induksi :
Asumsikan P(k) benar yaitu
2 + 4 + 6 + ... + 2k = k(k + 1), k ∈ N

Akan ditunjukkan P(k + 1) juga benar, yaitu
2 + 4 + 6 + ... + 2k + 2(k + 1) = (k + 1)(k + 1 + 1)

Dari perkiraan :
2 + 4 + 6 + ... + 2k = k(k + 1)
Tambahkan kedua ruas dengan u_k+1 :
2 + 4 + 6 + ... + 2k + 2(k + 1) = k(k + 1) + 2(k + 1)
2 + 4 + 6 + ... + 2k + 2(k + 1) = (k + 1)(k + 2)
2 + 4 + 6 + ... + 2k + 2(k + 1) = (k + 1)(k + 1 + 1)
Jadi, P(k + 1) benar

Berdasarkan prinsip induksi matematika, terbukti bahwa P(n) benar untuk setiap n bilangan asli.

Contoh 2
Buktikan 1 + 3 + 5 + ... + (2n − 1) = n² benar, untuk setiap n bilangan asli

Jawab :
P(n) : 1 + 3 + 5 + ... + (2n − 1) = n²
Akan ditunjukkan P(n) benar untuk setiap n ∈ N

Langkah Dasar :
Akan ditunjukkan P(1) benar
1 = 1²
Jadi, P(1) benar

Langkah Induksi :
Asumsikan P(k) benar, yaitu
1 + 3 + 5 + ... + (2k − 1) = k², k ∈ N

Akan ditunjukkan P(k + 1) juga benar, yaitu
1 + 3 + 5 + ... + (2k − 1) + (2(k + 1) − 1) = (k + 1)²

Dari perkiraan :
1 + 3 + 5 + ... + (2k − 1) = k²
Tambahkan kedua ruas dengan u_k+1 :
1 + 3 + 5 + ... + (2k − 1) + (2(k + 1) − 1) = k² + (2(k + 1) − 1)
1 + 3 + 5 + ... + (2k − 1) + (2(k + 1) − 1) = k² + 2k + 1
1 + 3 + 5 + ... + (2k − 1) + (2(k + 1) − 1) = (k + 1)²
Jadi, P(k + 1) juga benar

Berdasarkan prinsip induksi matematika, terbukti bahwa P(n) benar untuk setiap n bilangan asli.

Pembuktian Keterbagian

Pernyataan "a habis dibagi b" bersinonim dengan :

a kelipatan b
b faktor dari a
b membagi a

Jika p habis dibagi a dan q habis dibagi a, maka (p + q) juga habis dibagi a.
Sebagai contoh, 4 habis dibagi 2 dan 6 habis dibagi 2, maka (4 + 6) juga habis dibagi 2

Contoh 3
Buktikan 6ⁿ + 4 habis dibagi 5, untuk setiap n bilangan asli.

Jawab :
P(n) : 6ⁿ + 4 habis dibagi 5
Akan dibuktikan P(n) benar untuk setiap n ∈ N.

Langkah Dasar :
Akan ditunjukkan P(1) benar
6¹ + 4 = 10 habis dibagi 5
Jadi, P(1) benar

Langkah Induksi :
Asumsikan P(k) benar, yaitu
6^k + 4 habis dibagi 5, k ∈ N

Akan ditunjukkan P(k + 1) juga benar, yaitu
6^k+1 + 4 habis dibagi 5.

6^k+1 + 4 = 6(6^k)+ 4
6^k+1 + 4 = 5(6^k) + 6^k + 4

Karena 5(6^k) habis dibagi 5 dan 6^k + 4 habis dibagi 5, alhasil 5(6^k) + 6^k + 4 juga habis dibagi 5.
Jadi, P(k + 1) benar.

Berdasarkan prinsip induksi matematika, terbukti bahwa 6ⁿ + 4 habis dibagi 5, untuk setiap n bilangan asli.

Bilangan lingkaran a habis dibagi bilangan lingkaran b jikalau terdapat bilangan lingkaran m sehingga berlaku a = bm.
Sebagai contoh, "10 habis dibagi 5" benar alasannya ialah terdapat bilangan lingkaran m = 2 sehingga 10 = 5.2. Jadi, pernyataan "10 habis dibagi 5" sanggup kita tulis menjadi "10 = 5m, untuk m bilangan bulat"
Berdasarkan konsep diatas, pembuktian keterbagian sanggup pula diselesaikan dengan cara sebagai berikut.

Contoh 4
Buktikan n³ + 2n habis dibagi 3, untuk setiap n bilangan asli

Jawab :
P(n) : n³ + 2n = 3m, dengan m ∈ \(\mathbb{Z}\)
Akan dibuktikan P(n) benar untuk setiap n ∈ \(\mathbb{N}\)

Langkah Dasar :
Akan ditunjukkan P(1) benar
1³ + 2.1 = 3 = 3.1
Jadi, P(1) benar

Langkah Induksi :
Asumsikan P(k) benar, yaitu
k³ + 2k = 3m, k ∈ \(\mathbb{N}\)

Akan ditunjukkan P(k + 1) juga benar, yaitu
(k + 1)³ + 2(k + 1) = 3p, p ∈ \(\mathbb{Z}\)

(k + 1)³ + 2(k + 1) = (k³ + 3k² + 3k + 1) + (2k + 2)
(k + 1)³ + 2(k + 1) = (k³ + 2k) + (3k² + 3k + 3)
(k + 1)³ + 2(k + 1) = 3m + 3(k² + k + 1)
(k + 1)³ + 2(k + 1) = 3(m + k² + k + 1)

Karena m bilangan lingkaran dan k bilangan asli, maka (m + k² + k + 1) adalah bilangan bulat.
Misalkan p = (m + k² + k + 1), maka
(k + 1)³ + 2(k + 1) = 3p, dengan p ∈ \(\mathbb{Z}\)
Jadi, P(k + 1) benar

Berdasarkan prinsip induksi matematika, terbukti bahwa n³ + 2n habis dibagi 3, untuk setiap n bilangan asli.

Pembuktian Pertidaksamaan

Berikut sifat-sifat pertidaksamaan yang sering digunakan
1. Sifat transitif
a > b > c ⇒ a > c atau
a < b < c ⇒ a < c

2. a < b dan c > 0 ⇒ ac < bc atau
a > b dan c > 0 ⇒ ac > bc

3. a < b ⇒ a + c < b + c atau
a > b ⇒ a + c > b + c

Sebelum masuk pada teladan soal, ada baiknya kita latihan memakai sifat-sifat diatas untuk memperlihatkan implikasi "jika P(k) benar maka P(k + 1) juga benar".

Misalkan
P(k) : 4k < 2^k
P(k + 1) : 4(k + 1) < 2^k+1
Jika diasumsikan P(k) benar untuk k ≥ 5, tunjukkan P(k + 1) juga benar !

Ingat bahwa sasaran kita ialah menunjukkan
4(k + 1) < 2^k+1 = 2(2^k) = 2^k + 2^k (TARGET)

Kita sanggup mulai dari ruas kiri pertaksamaan diatas
4(k + 1) = 4k + 4
4(k + 1) < 2^k + 4 (karena 4k < 2^k)
4(k + 1) < 2^k + 2^k (karena 4 < 4k < 2^k)
4(k + 1) = 2(2^k)
4(k + 1) = 2^k+1

Berdasarkan sifat transitif kita simpulkan
4(k + 1) < 2^k+1

Mengapa 4k sanggup menjelma 2^k ?
Berdasarkan sifat 3, kita diperbolehkan menambahkan kedua ruas suatu pertaksamaan dengan bilangan yang sama, alasannya ialah tidak akan merubah nilai kebenaran pertaksamaan tersebut. Karena 4k < 2^k benar, alhasil 4k + 4 < 2^k + 4 juga benar.

Darimana kita tahu, 4 harus diubah menjadi 2^k ?
Perhatikan target. Hasil sementara kita ialah 2^k + 4 sedangkan sasaran kita ialah 2^k + 2^k.
Untuk k ≥ 5, maka 4 < 4k dan 4k < 2^k adalah benar, sehingga 4 < 2^k juga benar (sifat transitif). Akibatnya 2^k + 4 < 2^k + 2^k benar (sifat 3).

Contoh 5
Buktikan untuk setiap bilangan orisinil n ≥ 4 berlaku
3n < 2ⁿ

Jawab :
P(n) : 3n < 2ⁿ
Akan dibuktikan P(n) berlaku untuk n ≥ 4, n ∈ \(\mathbb{N}\)

Langkah Dasar :
Akan ditunjukkan P(4) benar
3.4 = 12 < 2⁴ = 16
Jadi, P(4) benar

Langkah Induksi :
Asumsikan P(k) benar, yaitu
3k < 2^k, k ≥ 4

Akan ditunjukkan P(k + 1) juga benar, yaitu
3(k + 1) < 2^k+1

3(k + 1) = 3k + 3
3(k + 1) < 2^k + 3 (karena 3k < 2^k)
3(k + 1) < 2^k + 2^k (karena 3 < 3k < 2^k)
3(k + 1) = 2(2^k)
3(k + 1) = 2^k+1

Jadi, P(k + 1) juga benar

Berdasarkan prinsip induksi matematika, terbukti bahwa P(n) berlaku untuk setiap bilangan orisinil n ≥ 4.

Contoh 6
Buktikan untuk setiap bilangan orisinil n ≥ 2 berlaku
3ⁿ > 1 + 2n

Jawab :
P(n) : 3ⁿ > 1 + 2n
Akan dibuktikan P(n) berlaku untuk n ≥ 2, n ∈ \(\mathbb{N}\)

Langkah Dasar :
Akan ditunjukkan P(2) benar
3² = 9 > 1 + 2.2 = 5
Jadi, P(1) benar

Langkah Induksi :
Asumsikan P(k) benar, yaitu
3^k > 1 + 2k, k ≥ 2

Akan ditunjukkan P(k + 1) juga benar, yaitu
3^k+1 > 1 + 2(k + 1)

3^k+1 = 3(3^k)
3^k+1 > 3(1 + 2k) (karena 3^k > 1 + 2k)
3^k+1 = 3 + 6k
3^k+1 > 3 + 2k (karena 6k > 2k)
3^k+1 = 1 + 2k + 2
3^k+1 = 1 + 2(k + 1)

Jadi, P(k + 1) juga benar

Berdasarkan prinsip induksi matematika, terbukti bahwa P(n) berlaku untuk setiap bilangan orisinil n ≥ 2.

Contoh 7
Buktikan untuk setiap bilangan orisinil n ≥ 5 berlaku
2n − 3 < 2^n-2

Jawab :
P(n) : 2n − 3 < 2^n-2
Akan dibuktikan P(n) berlaku untuk n ≥ 5, n ∈ \(\mathbb{N}\)

Langkah Dasar :
Akan ditunjukkan P(5) benar
2.5 − 3 = 7 < 2^5-2 = 8
Jadi, P(1) benar

Langkah Induksi :
Asumsikan P(k) benar, yaitu
2k − 3 < 2^k-2 , k ≥ 5

Akan ditunjukkan P(k + 1) juga benar, yaitu
2(k + 1) − 3 < 2^k+1-2

2(k + 1) − 3 = 2k + 2 − 3
2(k + 1) − 3 = 2k − 3 + 2
2(k + 1) − 3 < 2^k-2 + 2 (karena 2k − 3 < 2^k-2)
2(k + 1) − 3 < 2^k-2 + 2^k-2 (karena 2 < 2k − 3 < 2^k-2)
2(k + 1) − 3 = 2(2^k-2)
2(k + 1) − 3 = 2^k+1-2

Jadi, P(k + 1) juga benar

Berdasarkan prinsip induksi matematika, terbukti bahwa P(n) berlaku untuk setiap bilangan orisinil n ≥ 5.

Contoh 8
Buktikan untuk setiap bilangan orisinil n ≥ 4 berlaku
(n + 1)! > 3ⁿ

Jawab :
P(n) : (n + 1)! > 3ⁿ
Akan dibuktikan P(n) berlaku untuk n ≥ 4, n ∈ \(\mathbb{N}\)

Langkah Dasar :
Akan ditunjukkan P(4) benar
(4 + 1)! > 3⁴
ruas kiri : 5! = 5.4.3.2.1 = 120
ruas kanan : 3⁴ = 81
Jadi, P(1) benar

Langkah Induksi :
Asumsikan P(k) benar, yaitu
(k + 1)! > 3^k , k ≥ 4

Akan ditunjukkan P(k + 1) juga benar, yaitu
(k + 1 + 1)! > 3^k+1

(k + 1 + 1)! = (k + 2)!
(k + 1 + 1)! = (k + 2)(k + 1)!
(k + 1 + 1)! > (k + 2)(3^k) (karena (k + 1)! > 3^k)
(k + 1 + 1)! > 3(3^k) (karena k + 2 > 3)
(k + 1 + 1)! = 3^k+1

Jadi, P(k + 1) juga benar

Berdasarkan prinsip induksi matematika, terbukti bahwa P(n) berlaku untuk setiap bilangan orisinil n ≥ 4.

Sumber http://smatika.blogspot.com