Induksi Matematika (3 Bentuk) [PDF]

Citation preview

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.