Induksi Matematika

INDUKSI MATEMATIKA

Induksi matematika merupakan salah satu metode pembuktian dari banyak teorema dalam teori bilangan dalam matematika. Induksi matematika juga marupakan salah satu argumentasi pembuktian suatu teorema atau pernyataan matematika yang semesta pembicaraannya himpunaan bilangan bulat, lebih khusus himpunan bilangan asli. Misalkan pernyataan : “ p(n) adalah suatu proposisi yang berlaku untuk setiap bilangan asli n.” 

Pembuktian dari kebenaran dari pernyataan ini dengan menggunakan induksi matematika mengikuti langkah-langkah berikut:

Langkah1        : Ditunjukkan bahwa p(1), benar.

Langkah 2       : Diasumsikan bahwa p(k) benar untuk suatu bilangan asli k > 1 dan di tunjukkan bahwa p ( k + 1 ), benar. 

Apabila kedua langkah berhasil, maka kita dapat menyimpulkan bahwa p(n) benar untuk setiap bilangan asli n. Langkah 1 disebut basis ( dasar ) induk dan langkah 2 disebut langkah induksi. 

Contoh :

Buktikan bahwa untuk setiap bilangan asli n berlaku 2 + 4 + 6 + ... + 2n = n (n+1)

Bukti :

Misalkan p(n) menyatakan : 2 + 4 + 6 + ... + 2n = n ( n+1 )

a = 2

b = 2

Un = 2n

Sn = n(n +1) 
 a.  P(1)  => 2 = n (n+1)
                    2 = 1( 1+1)
                    2 = 1 (2) 
                    2 = 2
Jadi pembuktian P(1) benar.

            b. Diasumsikan kedalam P(k) bernilai benar.

     P(n) =>  2 + 4 + 6 + ... + 2n = n (n+1)

     P(k) => 2 + 4 + 6 + ... + 2k = k (k+1) 
 c.  Akan dibuktikan bahwa P (k+1) juga bernilai benar.

     P (k+1) => 2 + 4 + 6 + ... + 2k + 2 (k+1) = k+1 {(k+1) + 1}

                                            k(k+1) + 2(k+1) = (k+1) (k+2)

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

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

                                                   (k+1) (k+2) = (k+1) (k+2)

Jadi pembuktian P(k+1) terbukti benar.

      Jika 2 + 4 + 6 + ... + 2k + 2(k+1) = (k+1) (k+2) maka P(k+1) bernilai benar. Sehingga untuk setiap bilanggan asli n berlaku 2 + 4 + 6 + ... + 2n = n (n+1)

Latihan 
     1.  Buktikan bahwa untuk setiap bilangan asli n berlaku : 1 + 2 + 3 +...+ n = ½ n (n+1).

       Bukti :

a.       P(n)  => 1+2+3+...+ n = ½ n (n+1)

b.      P(1)  => 1 = ½ n (n+1)

              1 = ½ (1) (1+1)

              1 = ½ (2)

              1 = 1

c.       P(k) => 1+2+3+...+k = ½ k (k+1) akan dibuktikan bahwa P(k+1) bernilai benar.

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

                     k + ½ k (k+1) = ½ k (k+1)

              (k+1) + ½ k (k+1) = ½ (k+1) {(k+1) +1}

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

                 ½ k² + 3/2 k + 1 = ½ (k+1) (k+2)

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

                     ½ (k+1) (k+2) = ½ (k+1) (k+2)  =>  benar

        2.     Hitunglah 1 + 3 + 5 + ... + (2n-1) ?

Penyelesaian :

a = 1

b = 2

Un = 2n-1

Sn = ?

Sn = ½ n (a+Un)

     = ½ n (1+2n-1)

     = ½ n (2n)

     = n²

a.       P(n) => 1+3+5+...+(2n-1) = n²

b.      P(1) => 1 = n²

             1 = 1²

             1 = 1

c.       P(k) => 1+3+5+...+(2k-1) = k²

d.      P(k+1) => 1+3+5+...+{2(k+1)+1} = (k+1)²

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

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

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

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

       3.     Hitunglah 2 + 4 + 6 + ... + ... = ...

       Penyelesaian:

2 + 4 + 6 + ... + ... = ...

a = 2

b = 2

Un = a +(n-1).b

      = 2 + (n-1) .2

      = 2 + 2n-2

      = 2n

Sn = ½ n (n+Un)

     = ½ n (n+2n)

     = ½ n (2 +2n)

     = n + n²

a.       P(n) => 2 + 4 + 6 + ... + 2n = n + n²

b.      P(1) =>  2 = n + n²

              2 = 1 + 1²

              2 = 1 +1

              2 = 2

c.       P(k) = 2 + 4 + 6 +...+ 2k = k + k²

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

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

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

                      k² + 3k +2 = k+1+ k² + k + k +1

                     k² + 3k + 2 = k² + 3k +2

NOTASI SIGMA ( ∑ )

Notasi sigma adalah penjumlahan untuk bilangan-bilangan yang teratur dapat ditulis dengan singkat dengan menggunakan notasi sigma.

Contoh :

1.   Buktikan bahwa 7ⁿ -2ⁿ terbagi habis oleh 5 untuk setiap bilangan asli n.

Bukti :

a.       P(n) => 7ⁿ – 2ⁿ terbagi habis oleh 5.

b.      P(1) => 7¹ – 2¹ terbagi habis oleh 5, benar karena 5 terbagi habis oleh 5.

c.     P(k) => diasumsikan benar 7^k – 2^k terbagi habis oleh 5. Akan dibuktikan bahwa P(k+1) yaitu : 7^k+1 – 2^k+1 juga benar.

7^k+1 – 2^k+1 = 7^k . 7¹ – k^k . 2¹

                   = 7^k . 7¹ – 2^k . 7 + 2^k . 7 – 2^k . 2¹

                   = 7 (7^k – 2^k) + 2^k (7 - 2)

                   = 7 (7^k – 2^k) + 2^k (5)

Karena 7^k – 2^k terbagi habis oleh 5, maka 7(7^k – 2^k) juga terbagi habis oleh 5.  2^k . 5 jelas terbagi habis oleh 5, sebab memiliki faktor 5. Sehingga 7(7^k – 2^k) . 2^k . 5 terbagi oleh 5. Selanjutnya dari langkah tersebut dapat disimpulkan 7^k – 2^k terbagi habis oleh 5.

Latihan 
1.      Buktikan bahwa 11ⁿ – 4ⁿ terbagi habis oleh 7 untuk setiap bilangan asli n.

Bukti :

a.       P(n) => 11ⁿ – 4ⁿ , terbagi habis oleh 7.

b.      P(1) => 11¹ – 4¹ =7, terbagi habis oleh 7.

c.       P(k) => diasumsikan benar 11^k – 4^k terbagi habis oleh 7 dan akan dibuktikan bahwa P(k+1) yaitu 11^k+1 – 4^k+1 juga benar.

d.      P(k+1) => 11^k+1 – 4^k+1 = 11^k . 11¹ – 4^k . 4¹

                                      = 11^k . 11¹ – 4^k . 11 + 4^k . 11 – 4^k . 4

                                      = 11 (11^k – 4^k ) + 4^k . 7

Karena 11^k – 4^k terbagi habis oleh 7, maka 11(11^k . 4^k) juga terbagi habis oleh 7. Dan 4^k . 7 juga terbagi habis oleh 7, sebab memiliki faktor 7. Sehingga 11(11^k  - 4^k) . 4^k . 7 terbagi habil oleh 7. Selanjutnya dari langkah – langkah tersebut dapat disimpulkan 11^k – 4^k terbagi oleh 7.

2.      Buktikan bahwa n³ – 4n + 6 terbagi habis oleh 3.

Bukti :

a.       P(n) => n³ – 4n +6 terbagi habis oleh 3.

b.      P(1) = 1² – 4 . 1 + 6

        = 1 – 4 + 6

        = 3 terbagi habis oleh 3.

c.       P(k) diasumsikan benar k³ – 4k +6 terbagi habis oleh 3. Akan dibuktikan bahwa P(k+1) yaitu (k+1)³ – 4(k+1) + 6 jiga benar.

                             (k+1)³ – 4 (k+1) + 6 = (k+1) (k+1) (k+1) -4 (k+1) +6

                                = (k³ + 2k +1) (k+1) – 4 (k+1) +6

                                = k³ + k² +2k² +2k + k +1) – 4 (k+1) +6

                                = k³ + 3k² +3k +1 – 4k – 4k – 4 +6

                                = (k³- 4k +6 ) +3k² +3k +1 – 4

                                = ( k³ – 4k + 6) +3k² +3k -3

                                = k³ – 4k + 6 + 3(k²+ k -1)

                                = 3 (k²+k – 1) + (k³ + 4k +6 )

Karena k³ – 4k +6 terbagi habis oleh 3 maka k³ – 4k +6 juga terbagi habis oleh 3. Dan 3 (k²+k – 1) jelas terbagi oleh 3.