Induksi Matematika

Definisi & Fungsi

• Metoda pembuktian yang baku di dalam matematika.
• Digunakan untuk membuktikan pernyataan perihal bilangan bulat positif.
• Dapat mengurangi pembuktian bahwa semua bilangan bulat positif termasuk ke dalam suatu himpunan kebenaran dengan jumlah langkah terbatas

Prinsip Induksi Matematika Sederhana

t— 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 bahwa :

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) juga benar à  Hipotesis Induksi

t Bila kita sudah menunjukkan kedua langkah tersebut benar maka kita sudah membuktikan bahwa    p(n) benar untuk semua bilangan bulat positif n

Contoh

8—  Tunjukkan bahwa jumlah n buah bilangan ganjil positif pertama adalah n² melalui induksi matematik.

—8  Penyelesaian

1.     Langkah 1(Basis induksi): Untuk n = 1, kita peroleh jumlah satu buah bilangan ganjil positif pertama adalah 1² = 1. Ini benar karena jumlah satu buah bilangan ganjil positif pertama adalah 1

2.      Langkah 2 (Hipotesis induksi):  Andaikan untuk n ³ 1 pernyataan 1 + 3 + 5 + … + (2n – 1) = n²   adalah benar [bilangan ganjil positif ke-n adalah (2n – 1)].

Kita harus memperlihatkan bahwa   1 + 3 + 5 + … + (2n – 1) + (2n + 1) = (n + 1)² juga benar.

Hal ini dapat kita tunjukkan sebagai berikut:

1 + 3 + 5 + … + (2n – 1) + (2n + 1) = [1 + 3 + 5 + … + (2n – 1)] + (2n + 1)

                                                                                  = n² + (2n + 1)

                                                                                  = n² + 2n + 1

                                                                                  = (n + 1)² à benar

            Karena langkah 1 dan langkah 2 keduanya telah dibuktikan benar,  maka jumlah n buah bilangan ganjil positif pertama adalah n² .

Prinsip Induksi yang Dirampatkan

t—     Misalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n)      benar untuk semua bilangan bulat  n ³ n₀.

t—       Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa:

1.      Basis Induksi: p(n₀) benar, dan

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

Contoh

8—  Tunjukkan bahwa untuk n ³ 1, 1+2+3+…+n = n (n+1) / 2 melalui induksi matematik.

8—  Penyelesaian

1.      Langkah 1(Basis induksi ): Untuk n = 1, kita peroleh 1 = 1 (1+1) / 2.

1= 1 (1+1) / 2 = 1 (2) / 2 = 2/2 = 1 à benar dan terdefinisi

2.      Langkah 2 (Hipotesis induksi) :  Andaikan bahwa untuk n ³ 1, 1 + 2 + 3 +… + n = n (n+1) / 2 adalah benar (hipotesi induksi).

            Kita harus menunjukkan bahwa

            1 + 2 + 3 +… + n + (n+1) = (n+1) [(n+1) + 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)

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

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

                                                        = (n² + 3n + 2) / 2

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

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

            Karena langkah 1 dan langkah 2 keduanya telah dibuktikan benar,  maka untuk semua bilangan bulat positif n terbukti  1 + 2 + 3 + … + n  = n (n+1) / 2.

Prinsip Induksi Kuat

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

1.      p(n₀) benar, dan

2.     untuk semua bilangan bulat  n ³ n₀,  jika p(n₀ ), p(n₀+1), …, p(n) benar maka p(n+1) juga benar.

Contoh

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

8—     Penyelesaian

1.   Basis induksi. Jika n = 2, maka 2 sendiri adalah bilangan prima dan di sini 2 dapat dinyatakan sebagai perkalian dari satu buah bilangan prima, yaitu dirinya sendiri.

2.    Langkah induksi. Misalkan pernyataan bahwa bilangan 2, 3, …, n dapat dinyatakan sebagai perkalian (satu atau lebih) bilangan prima adalah benar (hipotesis induksi). Kita perlu menunjukkan bahwa n + 1 juga dapat dinyatakan sebagai perkalian bilangan prima.

Ada dua kemungkinan nilai n + 1:

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

5— 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 yang dalam hal ini, 2 £ a £ b £ n. Menurut hipotesis induksi, a dan b dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima. Ini berarti, n + 1 jelas dapat dinyatakan sebagai perkalian bilangan prima, karena n + 1 = ab.

     

            Karena langkah 1 dan langkah 2 sudah ditunjukkan 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

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

t—   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₀) benar, yang dalam hal ini x₀ adalah elemen terkecil di dalam X, dan

2.      Untuk semua x > x₀ di dalam X, jika p(y) benar untuk semua y < x, maka p(x) juga benar.

Contoh

—  Tinjau barisan bilangan yang didefinisikan sebagai berikut:

—  Sebagai contoh,

            S_0,0  = 0                                    S_{1, 0} = S_0,0 + 1 = 0 + 1 = 1

            S_{0, 1} = S_0,0 + 1 = 1                    S_{1, 1} = S_1,0 + 1 = 1 + 1 = 2

            S_{2, 0} = S_1,0 + 1 = 2                    S_{2, 1} = S_2,0 + 1 = 3, …

—  Buktikanlah dengan induksi matematik bahwa untuk pasangan tidak negatif m dan n, S_{m, n} = m + n.

—  Penyelesaian

5—  Basis induksi. Karena (0, 0) adalah elemen terkecil di dalam X, maka S₀,₀ = 0 + 0 = 0. Ini benar dari definisi S_0,0.

5—   Langkah induksi. Buktikan untuk semua (m, n)  >  (0, 0) di dalam X bahwa jika S_m',n' = m' + n' benar untuk semua (m', n')  <  (m, n) maka S_{m, n} = m + n juga benar. Andaikan bahwa S_{m’, n’} = m’ + n’ benar untuk semua (m’, n’) < (m,n).  Ini adalah hipotesis induksi. Kita perlu menunjukkan bahwa S_m,n = m + n, baik untuk n = 0 atau n ¹ 0.

0—  Kasus 1: Jika n = 0, maka dari definisi S_m,n = S_m-1,n + 1.

Karena (m-1, n) < (m, n), maka dari hipotesis induksi,  

                           S_{m-1, n} = (m – 1) + n

sehingga S_m,n = S_m-1,n + 1 = (m – 1) + n + 1 = m + n.
0—  Kasus 2: Jika n ¹ 0, maka dari definisi S_m,n = S_m,n-1 + 1.

Karena (m, n-1) < (m, n), maka dari hipotesis induksi,

                                 S_{m, n-1} = m + (n – 1) 
                     sehingga S_m,  n = S_m, n-1 + 1 = m + (n – 1) + 1 = m + n.