INDUKSI MATEMATIKA

Induksi Matematika

        Metode pembuktian untuk proposisi perihal biangan bulat adalah induksi matematika.Induksi matematik merupakan teknik pembuktian yang baku di dalam matematika.Mealui induksi matematik kita dapat mengurangi angkah - langkah pembuktian bahwa semua bilangan bulat termasuk ke dalam suatu himpunan kebenaran dengan hanya sejumlah langkah terbatas. 

Contoh proposisi perihal bilangan bulat:

1. Jumlah bilangan bulat positif dari 1 sampai adalah .
2. Jumlah buah bilangan ganjil positif pertama adalah .
3. Untuk semua , adalah kelipatan 3.
4. Untuk semua bilangan bulat tak negatif n,
5. Untuk membayar biaya pos sebesar sen selalu dapat digunakan biaya perangko 3 sen
6. dan 5 sen.

PRINSIP INDUKSI SEDERHANA adalah Jika p(n) adalah pernyataan perihal bilangan bulat positif dan kita dapat membuktika bahwa p(n) benar untuk semua bilangan bulat positif n dengan langkah - langkah berikut :

1. Langkah 1 : P(1) benar/terdefinisi  → Basis Induksi, dan
2. Langkah 2 : Untuk semua bilangan bulat positif n→ 1, jika p(n) benar maka p(n+1) jugabenar → Hipotesis Induksi

Bila kita sudah menunjukkan kedua langkah tersebut benar maka kita sudah membuktikan

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

CONTOH SOAL

Buktikan dengan induksi matematika bahwa untuk semua bilangan asli n berlaku :
1+2+3+4+….+n=12n(n+1)

Betul

Bukti :
Misalkan P(n) adalah 1+2+3+4+….+n=12n(n+1)
P(n)$P(n)$benar untuk n=1$n=1$ karena 1=12(1)(1+1)
Andaikan P(n) benar, maka tunjukan bahwa p(n+1) juga benar sehingga:
1+2+3+4+……..n+(n+1)

=12n(n+1)+(n+1)

=(n+1)(12n+1)

=(n+1)×12(n+2)

=12(n+1)[(n+1)+1]

=p(n+1)
Jadi terbukti benar bahwa P(n+1) juga benar.
Dengan demikian pernyataan 1+2+3+4+…+n=12n(n+1) terbukti benar.

PRINSIP INDUKSI YANG DIRAMPATKAN

Prinsip induksi yang dirampatkan adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n≥ n0 .Untuk membuktikannya hanya perlu menunjukkan bahwa:

1. Basis Induksi: p (n0) benar, dan

2. Hipotesis Induksi : Untuk semua bilangan bulat n ≥ n0 , jika p(n) benar maka p(n+1) juga benar.

CONTOH:
Buktikan dengan induksi matematika bahwa 3n< n! untuk n bilangan bulat positif yang lebih besar dari 6
Jawab :

Misalkan p(n) adalah proposisi bahwa 3n< n! untuk n bilangan bulat positif yang lebih besar dari 6

Basis induksi

p(7) benar à 37 < 7! « 2187 < 5040

Langkah induksi

Misalkan bahwa p(n) benar, yaitu asumsikan bahwa 3n< n! adalah benar. Perlihatkan juga bahwa p(n+1) juga benar, yaitu 3n+1< (n+1)!

Hal ini dapat ditunjukkan sbb :

             3n+1 < (n+1)!

             3 . 3n < (n+1) . n!

             3n . 3 / (n+1) < n!

Menurut hipotesis induksi, 3n < n!,sedangkan untuk n > 6, nilai 3/(n+1) < 1, sehingga 3/(n+1) akan memperkecil nilai di ruas kiri persamaan. Efek nettonya, 3n .3/(n+1) < n! jelas benar

Langkah (i) dan (ii) dibuktikan benar, maka terbukti bahwa 3n < n! untuk n bilangan bulat positif lebih besar dari 6.

PRINSIP INDUKSI KUAT
Pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n ≥ n0.Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa:

1. p(n0) benar, dan
2. untuk semua bilangan bulat n ≥ n0 , jika p(n0), p(n0+1), …, p(n) benar maka p(n+1) juga benar.

CONTOH:

Bilangan bulat positif disebut prima jika dan hanya jika bilangan bulat tersebut habis dibagi dengan 1 dan dirinya sendiri.
Buktikan dengan induksi matematika (prinsip induksi kuat) bahwa setiap bilangan
bulat positif n(n ³ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.

Jawab :

Misalkan p(n) adalah proposisi setiap bilangan bulatpositif n(n ³ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima

(i)Basis induksi

p(2) benar à 2 sendiri adalah bilangan prima dan 2 dinyatakan sebagai perkalian dari satu buah bilangan prima, yaitu dirinya sendiri.

(ii)Langkah induksi

Misalkan p(n) benar, asumsikan bahwa bilangan 2, 3, …,n dapat dinyatakan sebagai perkalian (satu atau lebih) bilangan prima (hipotesis induksi). Perlihatkan juga bahwa p(n+1) benar, yaitu n + 1 juga dapat dinyatakan sebagai perkalian bilangan prima.

Hal ini dapat ditunjukkan sbb :

Jika n + 1 bilangan prima à perkalian satu atau lebih bilangan prima

Jika n + 1 bukan bilangan prima à terdapaat bilangan bulat positif a yang membagi habis
n + 1 tanpa sisa

                                    (n+1)/a= b atau (n+1) = ab

            dimana2 £ a £ b £ n.Menurut hipotesis induksi, a dan b dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima.Ini berarti bahwa n+1 jelas dapat dinyatakan sebagai

perkalian bilangan prima, karena n+1 = ab.Langkah (i) dan (ii) dibuktikan benar, maka terbukti bahwa setiap bilangan bulat positif n(n ³ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.

BENTUK INDUKSI SECARA UMUM

Relasi biner " < "pada himpunan X dikatakan terurut dengan baik (atau himpunan X dikatakanterurut dengan baik dengan"  < " bila memiliki properti berikut:

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

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

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".

Bentuk induksi secara umum dapat dituiskan sebagai berikut:

Misalkan X terurut dengan baik oleh " <  ", dan p(x) adalah pernyataan perihal elemen x dari X. Kita ingin membuktikan bahwa p(x) benar untuk semua x ∈ X. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa:

1. p(x 0 ) benar, yang dalam hal ini x 0 adalah elemen terkecil di dalam X, dan

2. Untuk semua y < x 0 di dalam X, jika p(x) benar untuk semua x > x0 di dalam X sehingga p(x) benar untuk semua x ∈ X.