Matematika Diskrit : INDUKSI MATEMATIKA

 Induksi Matematika merupakan suatu teknik yang dikembangkan untuk membuktikan pernyataan  Induksi Matematika digunakan untuk mengecek hasil proses yang terjadi secara berulang sesuai dengan pola tertentu  Induksi Matematika digunakan untuk membuktikan universal statements  n  A S(n) dengan A  N dan N adalah himpunan bilangan positif atau himpunan bilangan asli.  S(n) adalah fungsi propositional TAHAPAN INDUKSI MATEMATIKA  Basis Step : Tunjukkan bahwa S(1) benar  Inductive Step : Asumsikan S(k) benar Akan dibuktikan S(k)  S(k+1) benar  Conclusion : S(n) adalah benar untuk setiap n bilangan integer positif PEMBUKTIAN INDUKSI MATEMATIKA Contoh 1 : Buktikan bahwa : 1 + 2 + 3 + … + n = ½ n(n+1) untuk setiap n bilangan integer positif Jawab :  Basis : Untuk n = 1 akan diperoleh : 1 = ½ 1 . (1+1)  1 = 1  Induksi : misalkan untuk n = k asumsikan 1 + 2 + 3 + …+ k = ½ k (k+1)  adib. Untuk n = k+1 berlaku 1 + 2 + 3 + …+ (k+1) = ½ (k+1) (k+2) Jawab :  1 + 2 + 3 + …+ (k+1) = (k+1) (k+2) / 2 1 + 2 + 3 + …+ k + (k+1) = (k+1) (k+2) / 2 k (k+1) / 2 + (k+1) = (k+1) (k+2) / 2 (k+1) [ k/2 +1 ] = (k+1) (k+2) / 2 (k+1) ½ (k+2) = (k+1) (k+2) / 2 (k+1) (k+2) / 2 = (k+1) (k+2) / 2  Kesimpulan : 1 + 2 + 3 + …+ n = ½ n (n +1) Untuk setiap bilanga bulat positif n Contoh 2 : Buktikan bahwa : 1 + 3 + 5 + … + (2n - 1) = n2 untuk setiap n bilangan bulat positif Jawab :  Basis : Untuk n = 1 akan diperoleh : 1 = 12  1 = 1  Induksi : misalkan untuk n = k asumsikan 1 + 3 + 5 + …+ (2k – 1) = k2  adib. Untuk n = k + 1 berlaku 1 + 3 + 5 + …+ (2 (k + 1) – 1) = (k + 1)2 1 + 3 + 5 + …+ (2k + 1) = (k + 1)2 1 + 3 + 5 + …+ ((2k + 1) – 2) + (2k + 1) = (k + 1)2 1 + 3 + 5 + …+ (2k - 1) + (2k + 1 ) = (k + 1)2 k 2 + (2K + 1) = (k + 1)2 k 2 + 2K + 1 = k 2 + 2K + 1 Kesimpulan : 1 + 3 + 5 + … + n = (2n - 1) = n2 Untuk setiap bilangan bulat positif n Contoh 3 : Buktikan bahwa : n 3 + 2n adalah kelipatan 3 untuk setiap n bilangan bulat positif Jawab :  Basis : Untuk n = 1 akan diperoleh : 1 = 13 + 2(1)  1 = 3 , kelipatan 3  Induksi : misalkan untuk n = k asumsikan k 3 + 2k = 3x  adib. Untuk n = k + 1 berlaku (k + 1)3 + 2(k + 1) adalah kelipatan 3 (k 3 + 3k 2 + 3 k+1) + 2k + 2 (k 3 + 2k) + (3k 2 + 3k + 3) (k 3 + 2k) + 3 (k 2 + k + 1) Induksi 3x + 3 (k 2 + k + 1) 3 (x + k 2 + k + 1) Kesimpulan : n 3 + 2n adalah kelipatan 3 Untuk setiap bilangan bulat positif n