INDUKSI MATEMATIKA

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

§ Indukasi 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 : Sumsikan 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 :

q Basis : Untuk n = 1 akan diperoleh :

1 = ½ 1 . (1+1) ® 1 = 1

q Induksi : misalkan untuk n = k asumsikan 1 + 2 + 3 + …+ k = ½ k (k+1)

q adib. Untuk n = k+1 berlaku

1 + 2 + 3 + …+ (k+1) = ½ (k+1) (k+2)

Jawab :

q 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

q Kesimpulan : 1 + 2 + 3 + …+ n = ½ n (n +1)

Untuk setiap bilanga bulat positif n

Contoh 2 :

Buktikan bahwa :

1 + 3 + 5 + … + n = (2n - 1) = n²

untuk setiap n bilangan bulat positif

Jawab :

q Basis : Untuk n = 1 akan diperoleh :

1 = 1² ® 1 = 1

q Induksi : misalkan untuk n = k asumsikan 1 + 3 + 5 + …+ (2k – 1) = k²

q adib. Untuk n = k + 1 berlaku

1 + 3 + 5 + …+ (2 (k + 1) – 1) = (k + 1)²

1 + 3 + 5 + …+ (2k + 1) = (k + 1)²

1 + 3 + 5 + …+ ((2k + 1) – 2) + (2k + 1) = (k + 1)²

1 + 3 + 5 + …+ (2k - 1) + (2k + 1 ) = (k + 1)²

k ² + (2K + 1) = (k + 1)²

k ² + 2K + 1 = k ² + 2K + 1

Kesimpulan : 1 + 3 + 5 + … + n = (2n - 1) = n²

Untuk setiap bilangan bulat positif n

Contoh 3 :

Buktikan bahwa :

N ³ + 2n adalah kelipatan 3

untuk setiap n bilangan bulat positif

Jawab :

q Basis : Untuk n = 1 akan diperoleh :

1 = 1³ + 2(1) ® 1 = 3 , kelipatan 3

q Induksi : misalkan untuk n = k asumsikan k ³ + 2k = 3x

q adib. Untuk n = k + 1 berlaku

(k + 1)³ + 2(k + 1) adalah kelipatan 3

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

(k ³ + 2k) + (3k ² + 3k + 3)

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

Induksi

3x + 3 (k ² + k + 1)

3 (x + k ² + k + 1)

Kesimpulan : N ³ + 2n adalah kelipatan 3

Untuk setiap bilangan bulat positif n

Referensi :

1. Introduction To Algoritms, Thomas N. Cormen, Charles E. Leiserson, Ronald L. Ruvest. MIT Press
2. Computer Algorithms: introduction to design and analysis. 2^nd ed., Sara Baase, Reading,Mass: Addison-Wesley Company, 1993
3. Analisis dan Desain Berorientasi Objek, Ariesto Hadi Sutopo, JJ Learning: Yogyakarta, 2002
4. Pengantar Analisis Algoritma, Suryadi MT, Gunadarma: Jakarta, 1992
5. Referensi silabus utama:
   http://www.cs.ucl.ac.uk/teaching/syllabus/ug/1b12.htm
   http://www.cs.caltech.edu/~cs138/
   http://www.lehigh.edu/~tkr2/teaching/ie170/
   http://hercule.csci.unt.edu/~ian/classes/fall03/csci4450/info.html
   http://highered.mcgrawhill.com/sites/0070131511/student_view0/chapter1/chapter_overview.