INDUKSI MATEMATIKA

Induksi matematika merupakan teknik pembuktian yang baku di dalam matematika. Induksi matematika berawal pada akhir abad ke-19 dua orang matematikawan yang mempelopori perkembangan indusksi matematika adalah R.Dedekin dan G.Peano.

A.    Proposisi Perihal Bilangan Bulat

Di dalam matematika, banyak teorema yang menyatakan bahwa p(n) benar unruk semua bilangan bulat positif n, yang dalam hal ini p(n) disebut juga fungsi proposisi. Contoh-contoh  proposisi prihal bilangan bulat yaitu:

-          Setiap bilangan bulat positif n(n≥2)  dapat dinyatakn  sebagai perkalian dari (satu atau lebih) bilangan prima.

-          Untuk semua n≥1,n3+2n  adalah kelipatan 3.

-          Untuk biaya pos sebesar n sen dolar n≥8  selalu dapat digunakan hanya perangko 3 sen dan 5 sen dolar.

-          Di dalam sebuah pesta, setiap tamu berjabat tangan dengan tamu lainnya hanya sekali.Jika ada n orang tamu maka jumlah jabat tangan yang terjadi adalah nn-12.

Proposisi-proposisi semacam diataslah yang dapat dibuktikan dengan induksi matematika.

B.     Prinsip Induksi Sederhana

Prinsip induksi sederhana berbunyi sebagai berikut:

Misalkan p(n) adalah proposisi perihal bilangan bulat positif dan kita ingin membuktikan bahwa p(n) benar untuk setiap bilangan bulat positif n. Untuk membuktikan proposisi ini,kita hanya perlu menunjukkan bahwa:

-          P(1) benar,dan

-          Jika p(n) benar maka p(n+1) juga benar untuk setiap n≥1.

Sehingga p (n) benar untuk semua bilangan bulat positif n.

Langkah 1 dinamakan basis induksi, sedangkan langkah 2 dinamakan langkah induksi.

C.    Prinsip Induksi yang Dirampatkan

Prinsip induksi sederhan dapat dirampatkan (generalized) untuk menunjukan halini sebagai berikut:

Misalkan p (n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n≥n0 . Untuk membuktikan ini kita hanya perlu menunjukan bahwa:

-          p(n0)  benar,dan

-          jika p(n) benar maka p(n+1) benar untuk setiap n≥n0

Sehingga p(n) benar untuk semua bilangan bulat n≥n0.

D.    Prinsip Induksi Kuat

Versi induksi yang lebih kuat adalah seagai berikut:

Misalkan p(n) adalah peryataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n≥n0.  Untuk membuktikan ini kita hanya perlu menunjukan bahwa:

-          p( n0 ) benar, dan

-          jika p n0, p n0+1,…..,p(n) benar, maka p(n+1) juga benar untuk setiap bilangan bulat n≥n0.  

Sehingga p(n) benar untuk semua bilangan bulat n≥n0.

E.     Bentuk Induksi Secara Umum

Relasi biner “<” pada himpunan X dikatakan terurut dengan baik ( atau himpunan X dikatakan terurut dengan baik dengan “<”) bila memiliki properti berikut:

      1.            Diberikan x,y,z ∈X , jika x<y dan y<z, maka x<z.

      2.            Diberikan x,y∈X . Salah satu dari kemungkinan ini benar: x<y atau y<z atau x=z.

      3.            Jika A adalah himpunan bagian tidak kosong dari X, terdapat elemen x∈A  sedemikian sehingga x≤y  untuk semua y∈A.  Dengan kata lain, setiap himpunan bagian tidak kosong dari X mengandung “elemen terkecil”.

Himpunan bilangan riil tak-negatif tidak terurut dengan baik oleh relasi “<”. Himpunan ini mempunyai properti (i) dan (ii) tetapi tidak (iii).sebagai contoh, himpunan semua bilangan riil yang lebih besar dari 1, yaitu {x|x adalah bilangan riil dan x>1}, tidak mengandund elemen terkecil.