16 0 160 KB
1.3. Induksi Matematika Prinsip induksi matematika merupakan suatu alat penting untuk pembuktian hasil-hasil tentang bilangan-bilangan bulat. Teorema 1.2 (Prinsip Pertama Induksi Matematika). Jika suatu himpunan bilangan bulat positif S memuat 1, dan untuk setiap bilangan bulat positif n, S memuat n + 1 jika S memuat n maka S adalah himpunan semua bilangan asli positif.
Teorema itu bermakna, Step 1 (Basis step). Harus ditunjukkan bahwa hasilnya benar untuk n = 1. Step 2 (Induction hypotheses). Diasumsikan bahwa hasilnya benar untuk n = k. Step 3 (Inductive step). Harus ditunjukkan bahwa hasilnya benar untuk n = k + 1. Contoh 1.6. Dengan induksi matematika, tunjukkan bahwa n ! ≤ n n , ∀ n ∈ N . Penyelesaian. (i). Untuk n = 1: n ! = 1! = 1 dan n n = 11 = 1 . Sehingga berlaku 1! ≤ 11 . (ii). Anggap benar untuk n = k yaitu berlaku bahwa k ! ≤ k k (iii). Akan ditunjukkan benar untuk n = k + 1 yaitu berlaku (k + 1)! ≤ (k + 1) k +1 .
(k + 1)! = (k + 1) ⋅ k ! ≤ (k + 1) ⋅ k k ≤ (k + 1)(k + 1) k = (k + 1) k +1 . (Lemma: tunjukkan nn ≤ (n + 1)n , ∀n ∈ N ) Teorema 1.3 (Prinsip Kedua Induksi Matematika/ Induksi Matematika Kuat). Jika suatu himpunan bilangan bulat positif S memuat 1, dan mempunyai sifat bahwa untuk setiap bilangan bulat positif n, jika S memuat semua bilangan bulat positif 1, 2, 3, …, n, maka S juga memuat n + 1, adalah himpunan semua bilangan asli positif.
1
Teorema itu bermakna, Step 1 (Basis step). Harus ditunjukkan bahwa hasilnya benar untuk n = 1. Step 2 (Induction hypotheses). Diasumsikan bahwa hasilnya benar untuk n = 2, 3, …,k. Step 3 (Inductive step). Harus ditunjukkan bahwa hasilnya benar untuk n = k + 1. Definisi Rekursif. Suatu fungsi f dikatakan terdefinisi secara rekursif jika nilai f di 1 adalah dirinci (diketahui) dan jika untuk setiap bilangan bulat positif n suatu aturan diberikan untuk menentukan f ( n + 1) dari f (n) . Contoh 2. (Rosen, Hal 25 no. 33). Didefinisikan suatu fungsi f secara rekursif dengan f(1) = 1, f(2) = 5 dan f ( n + 1) = f ( n ) + 2 ⋅ f ( n − 1), untuk n > 2 . Tunjukkan bahwa f (n) = 2 n + (−1) n , untuk semua n∈ N SELESAIAN. (i). Untuk n = 1. f(1) = 1 dan 2 + (−1) = 2 + (−1) = 1. Jadi f(1) = 2 + (−1) . Dgn dmk benar untuk n = 1.
(ii). Anggap benar untuk n = 2, 3, …, (k – 1), k yaitu berlaku f(n) = 2 + (−1) , untuk n = 2, 3, … , (k – 1), k.
(iii). Akan dibuktikan benar untuk n = k + 1 , yaitu berlaku f(k+1) = 2 + (−1) . Bukti: f(k+1) = ( )
+ 2 ∙ ( − 1)
= [ 2 + (−1) ] + 2∙ [ 2
+ (−1)
= 2 + 2 + (−1) + 2 ∙ (−1) = 2 ∙ 2 + (−1)
= 2
+ (−1)
.
[ (−1)
]
+ 2 ∙ (−1)
2
]
Teorema 1.2 (Prinsip Ketiga Induksi Matematika). Jika suatu himpunan bilangan bulat positif S memuat m, dan untuk setiap bilangan bulat positif n > m, S memuat n + 1 jika S memuat n maka S adalah himpunan semua bilangan asli positif lebih besar atau sama dengan m. Teorema itu bermakna, Step 1 (Basis step). Harus ditunjukkan bahwa hasilnya benar untuk n = m. Step 2 (Induction hypotheses). Diasumsikan bahwa hasilnya benar untuk n = k > m. Step 3 (Inductive step). Harus ditunjukkan bahwa hasilnya benar untuk n = k + 1. Contoh. Gunakan induksi matematika untuk membuktikan 2n < n !, untuk n ≥ 4 . Penyelesaian. (i). Untuk n = 4: 2n = 24 = 16 dan n ! = 4! = 24 . Jadi berlaku 2 4 < 4! . (ii). Anggap benar untuk n = k (k > 4) yaitu berlaku bahwa 2 k < k ! (iii). Akan ditunjukkan benar untuk n = k + 1 yaitu berlaku 2 k +1 < (k + 1)! .
2 k+1 = 2 k ⋅ 2 < k !⋅ 2 < k !⋅ (k + 1) = (k + 1)! Karena
2 2 . Tunjukkan bahwa f (n) = 2 n + (−1) n , untuk semua n∈ N 6. Didefinisikan A(1) = 1 dan A(n) = 4 + A(n - 1), untuk n ≥ 2 . Tunjukkan bahwa A( n ) = 4 n − 3, untuk n ∈ N dan n ≥ 2 . 7. Carilah rumus jumlah dari
1 1 1 1 + + + ... + . 1⋅ 4 4 ⋅ 7 7 ⋅10 (3n − 2)(3n + 1) Kemudian buktikan rumus tersebut dengan induksi matematika. 8. For what integers n is
9. Let
=
= 5 and
!
>
(
=
)!
? Prove your answer by induction.
+ 6∙
Show by strong mathematical induction that 10. Let
= 2,
= 0,
= 9∙
= −14 and − 23 ∙
, for
≥ 2.
= 3 − (−2) if
+ 15 ∙
Show by strong mathematical induction that
4
, for
= 3
≥3.
−5
+ 2,
≥1.
≥ 1.