What Are You Looking For?

A. DEFINISI

Induksi matematik merupakan teknik pembuktian yang baku di dalam matematika, khususnya yang menyangkut bilangan bulat positif. Melalui induksi matematik kita dapat mengurangi langkah-langkah pembuktian bahwa semua bilangan bulat termasuk ke dalam suatu himpunan kebenaran dengan hanya sejumlah langkah terbatas.

B. PRINSIP INDUKSI MATEMATIK

1. Prinsip Induksi Sederhana

2. Prinsip Induksi yang Dirampatkan

3. Prinsip Induksi Kuat

 

C. PEMBAHASAN

1. Prinsip Induksi Sederhana

 

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

• p(1) benar, dan

• Untuk semua bilangan bulat positif n ≥ 1, jika p(n) benar maka p(n+1) juga benar.

# Langkah 1 dinamakan basis induksi

# Langkah 2 dinamakan langkah induksi

# Asumsi jika p(n) benar dinamakan hipotesis induksi.

Contoh:

Tunjukkan bahwa untuk n ≥ 1, 1+2+…+n = n(n+1)/2!

Pembuktian :

Basis induksi. untuk n=1 diperoleh 1 = 1(1+1)/2, ini jelas benar sebab

1 = 1 (1+1)/2

= 1 (2)/2

= 2/2

= 1

Langkah induksi. Andaikan untuk n ≥ 1 pernyataan

1+2+3+…+n = n(n+1)/2 adalah benar (hipotesis induksi)

Kita harus menunjukkan bahwa:

1+2+3+…+n + (n+1) = (n+1)[(n+1)]/2 juga benar.

Untuk membuktikan ini tunjukkan bahwa:

1+2+3+…+ n + (n+1) = (1+2+3+…+n )+(n+1)

= [n(n+1)/2]+(n+1)

= [ (n2+n)/2]+(n+1)

= [ (n2+n)/2]+[(2n+2)/2]

= (n2+3n+2)/2

= [ (n2+n)/2]+[(2n+2)/2]

= (n2+3n+2)/2

= ( n+1)[(n+1)+1]/2

Karena langkah basis dan langkah induksi keduanya telah

dibuktikan benar, maka untuk semua bilangan bulat positif

n, terbukti bahwa:

1+2+3+…+n = n(n+1)/2

2. Prinsip Induksi yang Dirampatkan

 

Prinsip induksi sederhana dapat dirampatkan (generalized).

Misalkan p(n) adalah pernyataan perihal bilangan bulat n ≥ n₀. Untuk membuktikannya perlu menunjukkan bahwa :

1. p(n₀) benar

2. Jika p(n) benar, maka p(n+1) juga benar untuk setiap n ≥ n₀sehingga p(n) benar untuk semua bilangan bulat n ≥ n₀

Contoh soal :

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

Jawab :

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

Basis induksi

p(7) benar 3⁷< 7! → 2187 < 5040

Langkah induksi

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

Hal ini dapat ditunjukkan sbb :

3ⁿ⁺¹ < (n+1)!

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

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

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

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

3. Prinsip Induksi Kuat

 

Prinsip induksi yang lebih kuat adalah sbb :

1. p(n₀) benar

2. Jika p(n₀), p(n₀+1), …, p(n) benar, maka p(n+1) juga benar untuk setiap n ≥ n₀ sehingga p(n) benar untuk semua bilangan bulat n ≥ n₀

Versi induksi yang lebih kuat mirip dengan induksi sederhana, perbedaannya adalah pada langkah (ii) :

• Hipotesis induksi yang lebih kuat bahwa semua pernyataan p(1), p(2), …, p(n) adalah benar

• Hipotesis induksi sederhana bahwa p(n) benar

Prinsip induksi kuat memungkinkan kita mencapai kesimpulan yang sama meskipun memberlakukan andaian yang lebih banyak.

Contoh soal :

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.

Penyelesaian :

Basis induksi

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

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 :

1. Jika n + 1 bilangan prima, maka jelas ia dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima

2. Jika n + 1 bukan bilangan prima maka terdapat bilangan bulat positif a yang membagi habis n + 1 tanpa sisa, dengan kata lain

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

dimana 2 ≤ 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.

4. Bentuk Induksi Secara Umum

Membuat bentuk umum metode induksi sehingga dapat diterapkan tidak hanya untuk pembuktian proposisi yang menyangkut himpunan bilangan bulat positif tetapi juga pembuktian yang menyangkut himpunan obyek yang lebih umum.

Syaratnya himpunan obyek tersebut harus mempunyai :

1. Keterurutan

2. Elemen terkecil

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

3.Diberikan x, y, z ϵ X, jika x < y dan y < z maka x < z

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

5.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”.

Misalkan X terurut baik oleh “<“ dan p(x) adalah pernyataan perihal elemen x dari X. Pembuktian bahwa p(x) benar untuk semua x ϵ X. Untuk pembuktiannya hanya perlu menunjukkan bahwa :

p(x₀) benar, yang dalam hal ini x₀adalah elemen terkecil di dalam X

Jika p(y) benar untuk y < x, maka p(x) juga benar untuk setiap x > x₀di dalam X Sehingga p(x) benar untuk semua x ϵ X

5. Aplikasi Induksi Matematik Untuk Membuktikan Kebenaran Program

 

 

function Exp2(N:integer, M: integer )

{menghitung N2M }

Algoritma:

R ← 1

k ← 2*M

While (k > 0)

R ← R * N

k ← k – 1

end

return R

{ Computes : R = N2M

Loop invariant : R x Nk = N2M

}

Buktikan algoritma di atas benar dengan induksi matematika (semua variabel menggambarkan bilangan bulat non negatif)

Misal R_n dan K_n adalah nilai berturut-turut dari R dan K, setelah melewati loop while sebanyak n kali, n ≥ 0.

Misalkan p(n) adalah pernyataan: R_n x N^Kn = N^2M , n ≥ 0. Akan ditunjukkan bahwa p(n) benar dengan induksi matematika

(i) Basis:

Untuk n = 0, maka R₀ = 1, K₀= 2M adalah nilai variabel sebelum melewati loop.Maka pernyataan p(0): R₀ x N^K0 = N^2M

1 x N^2M = N^2M

adalah benar

(ii) Langkah Induksi

Asumsikan bahwa p(n) adalah benar untuk suatu n ≥ 0 setelah melewati loop n kali. Sehingga pernyataan p(n) dapat ditulis : R_n x N^Kn = N^2M .Harus ditunjukkan bahwa untuk satu tambahan loop, maka

R_n+1 x N^K_n+1 = N^2M

Hal ini ditunjukkan sebagai berikut: Setelah satu tambahan melewati loop,

R_n+1 = R_n x N dan K_n+1 = K_n – 1 maka

R_n+1 x N^K_n+1 = (R_n x N) x N^{Kn – 1} (dari hipotesis)

= (R_n x N) x N^Kn x N-1

= R_n x N^Kn

= N^2M

Jadi, R_n+1 x N^K_n+1 = N^2M

Sehingga p(n+1) menjadi benar. Karena itu, dengan prinsip dari induksi matematika, p(n) adalah benar untuk setiap n ≥ 0

 

SUMBER :

http://yos3prens.wordpress.com/2013/10/06/induksi-matematika/