Induksi Matematika : Materi, Contoh Soal dan Pembahasan

         Induksi matematika merupakan sebuah metode pembuktian deduktif yang dipakai guna membuktikan pernyataan matematika yang berkaitan dengan himpunan bilangan yang terurut rapi (well ordered set). Dalam induksi matematika ini, variabel dari suatu perumusan dibuktikan sebagai anggota dari himpunan bilangan asli.

Prinsip Induksi Matematika

Sebagai contoh P(n) merupakan sebuah pernyataan yang bergantung dengan n. P(n) benar untuk masing-masing n bilangan asli apabila dapat memenuhi 2 kondisi di bawaih ini:

1. P(1) benar, yang berarti untuk n = 1 maka P(n) nilainya benar.
2. Untuk masing-masing bilangan asli k, jika P(k) benar maka P(k + 1) juga benar.

Prinsip di atas bisa kita perluas lagi untuk pernyataan yang berkaitan dengan himpunan bagian tak kosong dari bilangan asli.

Perluasan Prinsip Induksi Matematika

Sebagai contoh  P(n) merupakan sebuah pernyataan yang bergantung dengan n. P(n) benar untuk masing-masing bilangan asli n ≥ m jika bisa memenuhi 2 keadaan di bawah ini:

1. P(m) benar, yang berarti untuk n = m, maka P(n) nilainya benar
2. Untuk masing-masing bilangan asli k ≥ m, jika P(k) benar maka P(k + 1) juga benar 

Tahapan Pembuktian Induksi Matematika

1. Langkah awal: Menunjukan P(1) benar.
2. Langkah induksi: Ibaratkan P(k) benar untuk sebarang k bilangan asli, lalu menunjukan P(k+ 1) juga benar berdasarkan dengan asumsi tersebut.
3. Kesimpulan: P(n) benar untuk masing-masing bilangan asli n

 Pembuktian Deret

    Jika
    P(n) :  u₁ + u₂ + u₃ + … + u_n = S_n , maka
    P(1) :  u₁ = S₁
    P(k) :  u₁ + u₂ + u₃ + … + u_k = S_k
    P(k + 1) :  u₁ + u₂ + u₃ + … + u_k + u_k+1 = S_k+1

Pembuktian Keterbagian

     Pernyataan “a habis dibagi b” yang bersinonim dengan:

• a kelipatan b
• b faktor dari a
• b membagi a

    Apabila p habis dibagi a serta q habis dibagi a, sehingga (p + q) juga akan habis dibagi a.

   Bilangan bulat a akan habis dibagi bilangan bulat b apabila dijumpai bilangan bulat m  

   sehingga akan berlaku a = bm.

Pembuktian Pertidaksamaan

    Berikut merupakan beberapa sifat pertidaksamaan yang sering dipakai, antara lain:
       1.  Sifat transitif
             a > b > c  ⇒  a > c  atau
             a < b < c  ⇒  a < c
       2.  a < b dan c > 0  ⇒  ac < bc  atau
            a > b dan c > 0  ⇒  ac > bc
       3.  a < b  ⇒  a + c < b + c  atau
            a > b  ⇒  a + c > b + c
    Sebelum kita masuk ke dalam contoh soal, ada baiknya apabila kita latihan terlebih dahulu dengan  memakai sifat-sifat di atas guna menunjukkan implikasi “apabila P(k) benar maka P(k + 1) juga benar”.

Contoh Soal dan Pembahasan

1. Buktikan 2 + 4 + 6 + … + 2n = n(n + 1), untuk masing-masing n bilangan asli.
    Penyelesaian :
       P(n) :  2 + 4 + 6 + … + 2n = n(n + 1)
       buktikan dengan P(n) benar untuk masing-masing n ∈ N
    Langkah awal:
        Tunjukkan P(1) benar
        2 = 1(1 + 1)
        Sehingga, P(1) benar
    Langkah induksi:
       Misalkan P(k) benar 
       2 + 4 + 6 + … + 2k = k(k + 1),    k ∈ N
       Tunjukkan P(k + 1) juga benar
       2 + 4 + 6 + … + 2k + 2(k + 1) = (k + 1)(k + 1 + 1)
       Dari asumsi di atas maka:
        2 + 4 + 6 + … + 2k = k(k + 1)
       Tambahkan kedua ruas dengan u_k+1 :
        2 + 4 + 6 + … + 2k + 2(k + 1) = k(k + 1) + 2(k + 1)
        2 + 4 + 6 + … + 2k + 2(k + 1) = (k + 1)(k + 2)
        2 + 4 + 6 + … + 2k + 2(k + 1) = (k + 1)(k + 1 + 1)
       Sehingga, P(k + 1) benar

2. Buktikan 1 + 3 + 5 + … + (2n − 1) = n² itu benar, untuk masing-masing n bilangan asli.
    Penyelesaian :
           P(n) :  1 + 3 + 5 + … + (2n − 1) = n²
           Tunjukkan P(n) benar untuk masing-masing n ∈ N
    Langkah awal:
           Tunjukkan P(1) benar
           1 = 1²
           Sehingga, P(1) benar
     Langkah induksi:
           Misalkan P(k) benar
           1 + 3 + 5 + … + (2k − 1) = k²,    k ∈ N
           Tunjukkan P(k + 1) juga benar
           1 + 3 + 5 + … + (2k − 1) + (2(k + 1) − 1) = (k + 1)²
           Dari asumsi di atas maka:
           1 + 3 + 5 + … + (2k − 1) = k²
           Tambahkan kedua ruas dengan u_k+1 :
           1 + 3 + 5 + … + (2k − 1) + (2(k + 1) − 1) = k² + (2(k + 1) − 1)
           1 + 3 + 5 + … + (2k − 1) + (2(k + 1) − 1) = k² + 2k + 1
           1 + 3 + 5 + … + (2k − 1) + (2(k + 1) − 1) = (k + 1)²
           Sehingga, P(k + 1) juga benar

3. Buktikan 6ⁿ + 4 habis dibagi 5, untuk masing-masing n bilangan asli.
    Penyelesaian :
             P(n) :  6ⁿ + 4 habis dibagi 5
             buktikan dengan P(n) benar pada masing-masing n ∈ N.
    Langkah awal:
             Tunjukkan P(1) benar
             6¹ + 4 = 10 habis dibagi 5
             Sehingga, P(1) benar
    Langkah induksi:
             Misalkan P(k) benar
             6^k + 4 habis dibagi 5,    k ∈ N
             Tunjukkan P(k + 1) juga benar
              6^k+1 + 4 habis dibagi 5.
              6^k+1 + 4 = 6(6^k)+ 4
              6^k+1 + 4 = 5(6^k) + 6^k + 4
    Sebab 5(6^k) habis dibagi 5 dan 6^k + 4 habis dibagi 5, maka 5(6^k) + 6^k + 4 juga akan habis dibagi 5.
    Sehingga, P(k + 1) benar.

 

4. Buktikan n³ + 2n akan habis dibagi 3, untuk masing-masing n bilangan asli
    Penyelesaian :
           P(n) :  n³ + 2n = 3m, dengan m ∈ $Z$
           buktikan dengan P(n) benar untuk masing-masing n ∈ $N$
    Langkah awal:
          Tunjukkan P(1) benar
          1³ + 2.1 = 3 = 3.1
          Sehingga, P(1) benar
    Langkah induksi:
          Misalkan, P(k) benar
          k³ + 2k = 3m,    k ∈ $N$
         Tunjukkan P(k + 1) juga benar
         (k + 1)³ + 2(k + 1) = 3p,     p ∈ $Z$
         (k + 1)³ + 2(k + 1) = (k³ + 3k² + 3k + 1) + (2k + 2)
         (k + 1)³ + 2(k + 1) = (k³ + 2k) + (3k² + 3k + 3)
         (k + 1)³ + 2(k + 1) = 3m + 3(k² + k + 1)
         (k + 1)³ + 2(k + 1) = 3(m + k² + k + 1)
          Sebab m bilangan bulat serta k adalah bilangan asli, maka (m + k² + k + 1) merupakan 
          bilangan bulat.
          p = (m + k² + k + 1), sehingga:
         (k + 1)³ + 2(k + 1) = 3p, dengan p ∈ $Z$
          Jadi, P(k + 1) adalah benar

5. Buktikan untuk masing-masing bilangan asli n ≥ 4 dan berlaku 3n < 2ⁿ
    Penyelesaian :
          P(n) :  3n < 2ⁿ
          buktikan P(n) berlaku untuk n ≥ 4, n ∈ $N$
    Langkah awal:
           Tunjukkan bahwa P(4) benar
            3.4 = 12 < 2⁴ = 16
            Sehingga, P(4) bernilai benar
    Langkah induksi
             Misalkan P(k) benar
             3k < 2^k,    k ≥ 4
             Tunjukkan bahwa P(k + 1) juga benar
              3(k + 1) < 2^k+1
              3(k + 1) = 3k + 3
              3(k + 1) < 2^k + 3               (karena 3k < 2^k)
              3(k + 1) < 2^k + 2^k             (karena 3 < 3k < 2^k)
              3(k + 1) = 2(2^k)
              3(k + 1) = 2^k+1
           Sehingga, P(k + 1) juga bernilai benar.
     Berdasarkan konsep dari induksi matematika, terbukti bahwa P(n) berlaku untuk masing-masing 
     bilangan asli n ≥ 4.

6. Buktikan untuk masing-masing bilangan asli n ≥ 2 dan berlaku 3ⁿ > 1 + 2n
    Penyelesaian :
         P(n) :  3ⁿ > 1 + 2n
         buktikan P(n) berlaku untuk n ≥ 2, n ∈ $N$
    Langkah awal:
         Tunjukkan bahwa P(2) bernilai benar
         3² = 9 > 1 + 2.2 = 5
         Sehingga, P(1) bernilai benar
     Langkah induksi:
          Misalkan, P(k) benar
          3^k > 1 + 2k,    k ≥ 2
          Tunjukkan bahwa P(k + 1) juga benar
          3^k+1 > 1 + 2(k + 1)
          3^k+1 = 3(3^k)
          3^k+1 > 3(1 + 2k)               (karena 3^k > 1 + 2k)
          3^k+1 = 3 + 6k
          3^k+1 > 3 + 2k                    (karena 6k > 2k)
          3^k+1 = 1 + 2k + 2
          3^k+1 = 1 + 2(k + 1)
          Sehingga, P(k + 1) juga bernilai benar
        Berdasarkan konsep dari induksi matematika, terbukti bahwa P(n) berlaku untuk masing-
    masing bilangan asli n ≥ 2.

7. Buktikan untuk masing-masing bilangan asli n ≥ 5 akan berlaku 2n − 3 < 2^n-2
    Penyelesaian :
          P(n) :  2n − 3 < 2^n-2
          buktikan dengan P(n) berlaku untuk n ≥ 5, n ∈ $N$
    Langkah awal:
          Tunjukkan P(5) bernilai benar
           2.5 − 3 = 7 < 2^5-2 = 8
           Sehingga, P(1) bernilai benar
     Langkah induksi:
           Misalkan P(k) bernilai benar
           2k − 3 < 2^k-2 ,    k ≥ 5
           Tunjukkan P(k + 1) juga bernilai benar
           2(k + 1) − 3 < 2^k+1-2
           2(k + 1) − 3 = 2k + 2 − 3
           2(k + 1) − 3 = 2k − 3 + 2
           2(k + 1) − 3 < 2^k-2 + 2         (sebab 2k − 3 < 2^k-2)
           2(k + 1) − 3 < 2^k-2 + 2^k-2    (sebab 2 < 2k − 3 < 2^k-2)
           2(k + 1) − 3 = 2(2^k-2)
           2(k + 1) − 3 = 2^k+1-2
           Sehingga, P(k + 1) juga bernilai benar
        Berdasarkan konsep dari induksi matematika, terbukti bahwa P(n) berlaku untuk masing-
    masing bilangan asli n ≥ 5.

8. Buktikan untuk masing-masing bilangan asli n ≥ 4 dan berlaku (n + 1)! > 3ⁿ
    Penyelesaian :
          P(n) :  (n + 1)! > 3ⁿ
          buktikan bahwa P(n) berlaku untuk n ≥ 4, n ∈ $N$
    Langkah awal:
          Tunjukkan P(4) bernilai benar
           (4 + 1)! > 3⁴
           ruas kiri : 5! = 5.4.3.2.1 = 120
           ruas kanan : 3⁴ = 81
           Sehingga, P(1) benar
     Langkah induksi:
           Misalkan P(k) bernilai benar
           (k + 1)! > 3^k ,   k ≥ 4
           Tunjukkan P(k + 1) juga benar
           (k + 1 + 1)! > 3^k+1
           (k + 1 + 1)! = (k + 2)!
           (k + 1 + 1)! = (k + 2)(k + 1)!
           (k + 1 + 1)! > (k + 2)(3^k)           (sebab (k + 1)! > 3^k)
           (k + 1 + 1)! > 3(3^k)                     (sebab k + 2 > 3)
           (k + 1 + 1)! = 3^k+1
           Sehingga, P(k + 1) juga bernilai benar.
       Berdasarkan konsep dari induksi matematika, terbukti bahwa P(n) berlaku untuk masing-masing
    bilangan asli n ≥ 4.

9. Buktikan bahwa .
    Penyelesaian :

• Langkah 1

          

               (terbukti)

• Langkah 2 (n = k)

         

• Langkah 3 (n = k + 1)

.

   

                                                                                                                  (kedua ruas ditambah .

 

 

 

 

      {terbukti).

 

 10. Buktikan bahwa :

 

     Penyelesaian :

• Langkah 1

          

                 (terbukti)

• Langkah 2 (n = k)

          

• Langkah 3 (n = k + 1)

                   Dibuktikan dengan:

      (kedua ruas dikali )

                        (2^k dimodifikasi menjadi 2^k+1)

                 

                 

                         (terbukti)

11. Buktikan bahwa habis dibagi 5.
      Penyelesaian :

• Langkah 1

               habis dibagi 5 (terbukti)

• Langkah 2 (n = k)

           

• Langkah 3 (n = k + 1)

         

                                       (dalam kurung dibuat sama dengan bentuk soal)

                                          ( dibuat 10 dan dibuat 5, agar  

                                                                        bisa dibagi 5)

                                                Didapatkan :

• habis dibagi 5
• habis dibagi 5
• sama dengan langkah 2, habis dibagi 5

12. Tentukan pernyataan P(k + 1) untuk masing-masing pernyataan P(k) berikut.

1. P(k): S_k = [k²(k + 1)²]/4
2. P(k): S_k = 1 + 5 + 9 + … + [4(k – 1) – 3] + (4k – 3)
3. P(k): k + 3 < 5k²
4. P(k): 3^k ≥ 2k + 1

      Penyelesaian :

1. Kita substitusi k + 1 ke k dalam pernyataan P(k).
   
2. Untuk mendapatkan pernyataan P(k + 1), kita ganti k pada pernyataan P(k) dengan k + 1.
   
3. Kita substitusi k dengan k + 1, dan kita peroleh
   
4. Serupa dengan soal-soal sebelumnya, kita substitusi k pada pernyataan P(k) dengan k + 1 untuk mendapatkan pernyataan P(k + 1).
   

13. Buktikan bahwa

       untuk semua bilangan bulat positif n.
       Penyelesaian :
       Misalkan P(n) adalah pernyataan 1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 + … + n(n + 1) = [n(n + 1)(n + 2)]/3.

1. Kita akan tunjukkan bahwa P(1) bernilai benar. Berdasarkan rumus di atas, P(1) menyatakan
   
   yang bernilai benar.
2. Anggap bahwa P(k) benar dan kita memperoleh hipotesis induksi sebagai berikut.
   
   Hipotesis ini akan kita gunakan untuk membuktikan bahwa P(k + 1) benar. Pernyataan P(k + 1) menyatakan
   
   Kita mulai dari bentuk yang berada di ruas kiri, kemudian kita gunakan hipotesis induksi untuk mendapatkan bentuk pada ruas kanan.
   
   Sehingga kita telah menunjukkan bahwa P(k + 1) mengikuti P(k). Sehingga kita telah membuktikan langkah induksi. 

14. Buktikan bahwa

       untuk semua bilangan bulat positif n ≥ 2.
       Penyelesaian : 
       Misalkan P(n) merupakan notasi dari pernyataan 1/√1 + 1/√2 + 1/√3 + … + 1/√n > √n.

1. Kita tunjukkan bahwa P(2) benar, yaitu
   
   Karena 1/√1 + 1/√2 ≈ 1,707 dan √2 ≈ 1,414 maka P(2) bernilai benar.
2. Anggap bahwa P(k) benar maka kita memperoleh hipotesis induksi seperti berikut.
   
   Selanjutnya, kita tunjukkan bahwa P(k + 1) juga bernilai benar dengan menggunakan hipotesis tersebut. P(k + 1) menyatakan bahwa
   
   Dengan menggunakan hipotesis induksi, kita ubah bentuk ruas kiri di atas menjadi bentuk yang ada di ruas kanan. Untuk k ≥ 2,
   
   Sehingga kita telah menunjukkan bahwa jika P(k) benar maka P(k + 1) benar. Jadi dengan menggunakan Prinsip Induksi Matematika kita dapat menyimpulkan bahwa P(n) benar untuk semua bilangan bulat n ≥ 2.

15. Buktikan bahwa untuk semua bilangan bulat positif n, salah satu faktor dari 2^{2n + 1} + 1 adalah 3.
      Penyelesaian :

1. Untuk n = 1 bentuk di atas menjadi
   
   Sehingga, benar bahwa 3 merupakan salah satu faktor dari 9.
2. Kita anggap bahwa untuk sebarang bilangan bulat positif k, Salah satu faktor 2^{2k + 1} + 1 adalah 3. Sekarang kita akan menunjukkan bahwa 3 merupakan salah satu faktor 2^{2(k + 1) + 1} + 1.
   
   Karena 3 merupakan salah satu faktor dari bentuk-bentuk 3 ∙ 2^{2k + 1} dan 2^{2k + 1} + 1 maka 3 adalah faktor dari 2^{2(k + 1) + 1} + 1. Jadi kita dapat menyimpulkan dengan menggunakan induksi matematika bahwa salah satu faktor dari 2^{2n + 1} + 1 adalah 3.

 16. Temukan rumus untuk penjumlahan berhingga berikut kemudian buktikan rumus tersebut 
       dengan induksi matematika.

        Penyelesaian :
        Kita mulai dengan menuliskan beberapa penjumlahan pertama.

         Dari barisan ini, tampak bahwa rumus penjumlahan k suku pertama adalah

       Untuk membuktikan kebenaran hipotesis ini, kita gunakan induksi matematika. Perhatikan   
       bahwa kita telah menguji rumus ini untuk n = 1, sehingga kita mulai dengan menganggap bahwa
       rumus tersebut benar untuk n = k dan mencoba untuk menunjukkan bahwa rumus tersebut juga
       benar untuk n = k + 1.

         Jadi, berdasarkan induksi matematika hipotesis tersebut benar.

17. Misalkan b₀, b₁, b₂, … adalah barisan yang didefinisikan sebagai berikut.

        untuk semua bilangan bulat k ≥ 2. Buktikan bahwa b_n = 3 ∙ 2ⁿ + 2 ∙ 5ⁿ untuk semua bilangan
        bulat n ≥ 0.
       Penyelesaian : 
       Misalkan P(n) adalah pernyataan yang menyatakan bahwa

       Akan kita tunjukkan bahwa P(n) bernilai benar untuk semua bilangan bulat n ≥ 0.

1. Pertama, akan kita tunjukkan bahwa P(0) dan P(1) benar, yaitu
   
   Sesuai definisi, b₀ = 5 dan b₁ = 16. Sedangkan 3 ∙ 2⁰ + 2 ∙ 5⁰ = 3 + 2 = 5 dan 3 ∙ 2¹ + 2 ∙ 5¹ = 6 + 10 = 16. Sehingga nilai-nilai b0 dan b1 sama dengan nilai-nilai yang diperoleh dari rumus yang diberikan. Oleh karena itu, P(0) dan P(1) benar.
2. Untuk sebarang bilangan bulat k ≥ 1, misalkan P(i) benar untuk 0 ≤ i ≤ k. Sehingga hipotesis induksi kita adalah
   
   untuk semua bilangan bulat 0 ≤ i ≤ k. Selanjutnya kita akan menunjukkan bahwa P(k + 1) benar, yaitu
   
   Karena k ≥ 1 maka k + 1 ≥ 2, dan kita dapat menuliskan
   Sehingga kita telah membuktikan bahwa jika P(i) benar maka P(k + 1) benar. Jadi dengan menggunakan induksi matematika kuat, kita dapat menyimpulkan bahwa P(n) benar untuk semua bilangan bulat n ≥ 0.

 18. Gunakan induksi matematika untuk menunjukkan bahwa 5ⁿ – 1 habis dibagi 4 untuk semua
        bilangan bulat positif n.
         Penyelesaian :

1. Untuk n = 1,
   
   yang sangat jelas habis dibagi 4.
2. Kita anggap 5^k – 1 habis dibagi 4 untuk sebarang bilangan bulat positif k. Akan kita tunjukkan 5^{k + 1} – 1 juga habis dibagi 4.
   
   Karena 4 ∙ 5^k dan 5^k – 1 habis dibagi 4 maka 5^{k + 1} – 1 habis dibagi 4. Jadi, kita dapat menyimpulkan bahwa 5ⁿ – 1 habis dibagi 4 untuk semua bilangan bulat positif n.

19. Buktikan bahwa n² – n + 41 merupakan bilangan ganjil untuk semua bilangan bulat positif n.
      Penyelesaian :

1. Untuk n = 1,
   
   merupakan bilangan ganjil.
2. Kita anggap untuk sebarang bilangan bulat positif k, k² – k + 41 merupakan bilangan ganjil. Selanjutnya kita harus menunjukkan bahwa (k + 1)² – (k + 1) + 41 adalah bilangan ganjil.
   
   Karena k² – k + 41 adalah bilangan ganjil dan 2k adalah bilangan genap, maka jumlah kedua bilangan tersebut, yaitu (k + 1)² – (k + 1) + 41 merupakan bilangan ganjil. Jadi, dengan menggunakan Prinsip Induksi Matematika kita dapat meyimpulkan bahwa n² – n + 41 merupakan bilangan ganjil untuk semua bilangan bulat positif n.

20. Buktikan bahwa

       untuk semua bilangan bulat positif n ≥ 3.
       Penyelesaian : 
       Misalkan P(n) menyatakan (n + 1)² < 2n².

1. Pernyataan P(3), yaitu
   
   dengan jelas bernilai benar.
2. Anggap P(k): (k + 1)² < 2k² bernilai benar, kita harus menunjukkan bahwa P(k + 1) juga bernilai benar, yaitu [(k+1) + 1]² < 2(k + 1)². Untuk k ≥3, kita memperoleh
   
   Sehingga kita telah menunjukkan kebenaran pernyataan jika P(k) benar maka P(k + 1). Oleh karena itu, berdasarkan Langkah 1 dan 2, dengan induksi matematika kita dapat menyimpulkan bahwa P(n) benar untuk semua bilangan bulat positif n ≥ 3.