Induksi Matematika

Induksi matematika adalah suatu metode pembuktian deduktif yang digunakan untuk membuktikan pernyataan matematika yang bergantung pada himpunan bilangan yang terurut rapi (well ordered set), seperti bilangan asli ataupun himpunan bagian tak kosong dari bilangan asli.

Perlu ditekankan bahwa induksi matematika hanya digunakan untuk membuktikan kebenaran dari suatu pernyataan atau rumus, bukan untuk menurunkan rumus. Atau lebih tegasnya induksi matematika tidak dapat digunakan untuk menurunkan atau menemukan rumus.

Berikut beberapa contoh pernyataan matematika yang dapat dibuktikan dengan induksi matematika :
P(n) :  2 + 4 + 6 + ... + 2n = n(n + 1), n bilangan asli
P(n) :  6n + 4 habis dibagi 5, untuk n bilangan asli.
P(n) :  4n < 2n, untuk setiap bilangan asli n ≥ 4

Cara yang paling mudah untuk memahami prinsip kerja induksi matematika adalah dengan mengamati efek domino. Kita dapat mulai dengan mengajukan pertanyaan "kapan semua domino akan jatuh".


Ada dua kondisi yang harus dipenuhi agar semua domino tersebut jatuh.
Pertama : domino 1 harus jatuh.
Kedua : benar bahwa setiap domino yang jatuh akan menjatuhkan tepat satu domino berikutnya. Artinya jika domino 1 jatuh maka domino 2 pasti jatuh, jika domino 2 jatuh maka domino 3 pasti jatuh dan seterusnya. Secara umum dapat kita katakan jika domino k jatuh maka domino (k + 1) juga jatuh dan implikasi ini berlaku untuk semua domino.

Jika kedua kondisi diatas telah terpenuhi, sudah dipastikan semua domino akan jatuh.


Prinsip Induksi Matematika

Misalkan P(n) adalah suatu pernyataan yang bergantung pada n. P(n) benar untuk setiap n bilangan asli jika memenuhi 2 kondisi berikut :
  1. P(1) benar, artinya untuk n = 1 maka P(n) bernilai benar.
  2. Untuk setiap bilangan asli k, jika P(k) benar maka P(k + 1) juga benar.
Prinsip diatas dapat diperluas untuk pernyataan yang bergantung pada himpunan bagian tak kosong dari bilangan asli.

Perluasan Prinsip Induksi Matematika
Misalkan P(n) adalah suatu pernyataan yang bergantung pada n. P(n) benar untuk setiap bilangan asli n ≥ m jika memenuhi 2 kondisi berikut :
  1. P(m) benar, artinya untuk n = m, maka P(n) bernilai benar
  2. Untuk setiap bilangan asli k ≥ m, jika P(k) benar maka P(k + 1) juga benar.

Untuk menunjukkan P(1) benar, kita cukup mensubstitusikan n = 1 pada P(n). Jika P(n) disajikan dalam bentuk persamaan, berarti ruas kiri harus sama dengan ruas kanan pada saat n = 1, barulah kita simpulkan P(1) benar. Cara yang sama dapat kita terapkan untuk menunjukkan P(m) benar.

Kembali lagi pada kasus domino diatas, agar domino (k + 1) jatuh, terlebih dahulu domino k harus jatuh, barulah implikasi "jika domino k jatuh maka domino (k + 1) jatuh" dapat terjadi.

Jadi, untuk menunjukkan implikasi "jika P(k) benar maka P(k + 1) benar", terlebih dulu kita harus menganggap atau mengasumsikan bahwa P(k) benar. Kemudian berdasarkan asumsi tersebut kita tunjukkan P(k + 1) juga benar. Proses asumsi P(k) benar ini disebut dengan hipotesis induksi.

Untuk menunjukkan P(k + 1) benar, dapat kita mulai dari hipotesis, yaitu dari asumsi P(k) benar ataupun dari kesimpulan, yaitu dari P(k + 1) itu sendiri.

Langkah-Langkah Pembuktian Induksi Matematika

Dari uraian-uraian diatas, langkah-langkah pembuktian induksi matematika dapat kita urutkan sebagai berikut :
  1. Langkah dasar : Tunjukkan P(1) benar.
  2. Langkah induksi : Asumsikan P(k) benar untuk sebarang k bilangan asli, kemudian tunjukkan P(k+ 1) juga benar berdasarkan asumsi tersebut. 
  3. Kesimpulan : P(n) benar untuk setiap bilangan asli n.

Pembuktian Deret

Sebelum masuk pada pembuktian deret, ada beberapa hal yang perlu dipahami dengan baik menyangkut deret.

Jika P(n) :  u1 + u2 + u3 + ... + un = Sn , maka
P(1) :  u1 = S1
P(k) :  u1 + u2 + u3 + ... + uk = Sk
P(k + 1) :  u1 + u2 + u3 + ... + uk + uk+1 = Sk+1

Contoh 1
Buktikan 2 + 4 + 6 + ... + 2n = n(n + 1), untuk setiap n bilangan asli.

Jawab :
P(n) :  2 + 4 + 6 + ... + 2n = n(n + 1)
Akan dibuktikan P(n) benar untuk setiap n ∈ N

Langkah Dasar :
Akan ditunjukkan P(1) benar
2 = 1(1 + 1)
Jadi, P(1) benar

Langkah Induksi :
Asumsikan P(k) benar yaitu
2 + 4 + 6 + ... + 2k = k(k + 1),    ∈ N

Akan ditunjukkan P(k + 1) juga benar, yaitu
2 + 4 + 6 + ... + 2k + 2(k + 1) = (k + 1)(k + 1 + 1)

Dari asumsi :
2 + 4 + 6 + ... + 2k = k(k + 1)
Tambahkan kedua ruas dengan uk+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)
Jadi, P(k + 1) benar

Berdasarkan prinsip induksi matematika, terbukti bahwa P(n) benar untuk setiap n bilangan asli.


Contoh 2
Buktikan 1 + 3 + 5 + ... + (2n − 1) = n2 benar, untuk setiap n bilangan asli

Jawab :
P(n) :  1 + 3 + 5 + ... + (2n − 1) = n2
Akan ditunjukkan P(n) benar untuk setiap n ∈ N

Langkah Dasar :
Akan ditunjukkan P(1) benar
1 = 12
Jadi, P(1) benar

Langkah Induksi :
Asumsikan P(k) benar, yaitu
1 + 3 + 5 + ... + (2k − 1) = k2,    k ∈ N

Akan ditunjukkan P(k + 1) juga benar, yaitu
1 + 3 + 5 + ... + (2k − 1) + (2(k + 1) − 1) = (k + 1)2

Dari asumsi :
1 + 3 + 5 + ... + (2k − 1) = k2
Tambahkan kedua ruas dengan uk+1 :
1 + 3 + 5 + ... + (2k − 1) + (2(k + 1) − 1) = k2 + (2(k + 1) − 1)
1 + 3 + 5 + ... + (2k − 1) + (2(k + 1) − 1) = k2 + 2k + 1
1 + 3 + 5 + ... + (2k − 1) + (2(k + 1) − 1) = (k + 1)2
Jadi, P(k + 1) juga benar

Berdasarkan prinsip induksi matematika, terbukti bahwa P(n) benar untuk setiap n bilangan asli.


Pembuktian Keterbagian

Pernyataan "a habis dibagi b" bersinonim dengan :
  • a kelipatan b
  • b faktor dari a
  • b membagi a
    Jika p habis dibagi a dan q habis dibagi a, maka (p + q) juga habis dibagi a.
    Sebagai contoh, 4 habis dibagi 2 dan 6 habis dibagi 2, maka (4 + 6) juga habis dibagi 2

    Contoh 3
    Buktikan 6n + 4 habis dibagi 5, untuk setiap n bilangan asli.

    Jawab :
    P(n) :  6n + 4 habis dibagi 5
    Akan dibuktikan P(n) benar untuk setiap n ∈ N.

    Langkah Dasar :
    Akan ditunjukkan P(1) benar
    61 + 4 = 10 habis dibagi 5
    Jadi, P(1) benar

    Langkah Induksi :
    Asumsikan P(k) benar, yaitu
    6k + 4 habis dibagi 5,    k ∈ N

    Akan ditunjukkan P(k + 1) juga benar, yaitu
    6k+1 + 4 habis dibagi 5.

    6k+1 + 4 = 6(6k)+ 4
    6k+1 + 4 = 5(6k) + 6k + 4

    Karena 5(6k) habis dibagi 5 dan 6k + 4 habis dibagi 5, akibatnya 5(6k) + 6k + 4 juga habis dibagi 5.
    Jadi, P(k + 1) benar.

    Berdasarkan prinsip induksi matematika, terbukti bahwa 6n + 4 habis dibagi 5, untuk setiap n bilangan asli.


    Bilangan bulat a habis dibagi bilangan bulat b jika terdapat bilangan bulat m sehingga berlaku a = bm.
    Sebagai contoh, "10 habis dibagi 5" benar karena terdapat bilangan bulat m = 2 sehingga 10 = 5.2. Jadi, pernyataan "10 habis dibagi 5" dapat kita tulis menjadi "10 = 5m, untuk m bilangan bulat"
    Berdasarkan konsep diatas, pembuktian keterbagian dapat pula diselesaikan dengan cara sebagai berikut.

    Contoh 4
    Buktikan n3 + 2n habis dibagi 3, untuk setiap n bilangan asli

    Jawab :
    P(n) :  n3 + 2n = 3m, dengan m ∈ \(\mathbb{Z}\)
    Akan dibuktikan P(n) benar untuk setiap n ∈ \(\mathbb{N}\)

    Langkah Dasar :
    Akan ditunjukkan P(1) benar
    13 + 2.1 = 3 = 3.1
    Jadi, P(1) benar

    Langkah Induksi :
    Asumsikan P(k) benar, yaitu
    k3 + 2k = 3m,    k ∈ \(\mathbb{N}\)

    Akan ditunjukkan P(k + 1) juga benar, yaitu
    (k + 1)3 + 2(k + 1) = 3p,     p ∈ \(\mathbb{Z}\)

    (k + 1)3 + 2(k + 1) = (k3 + 3k2 + 3k + 1) + (2k + 2)
    (k + 1)3 + 2(k + 1) = (k3 + 2k) + (3k2 + 3k + 3)
    (k + 1)3 + 2(k + 1) = 3m + 3(k2 + k + 1)
    (k + 1)3 + 2(k + 1) = 3(m + k2 + k + 1)

    Karena m bilangan bulat dan k bilangan asli, maka (m + k2 + k + 1) adalah bilangan bulat.
    Misalkan p = (m + k2 + k + 1), maka
    (k + 1)3 + 2(k + 1) = 3p, dengan p ∈ \(\mathbb{Z}\)
    Jadi, P(k + 1) benar

    Berdasarkan prinsip induksi matematika, terbukti bahwa n3 + 2n habis dibagi 3,  untuk setiap n bilangan asli.

    Pembuktian Pertidaksamaan

    Berikut sifat-sifat pertidaksamaan yang sering digunakan
    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 masuk pada contoh soal, ada baiknya kita latihan menggunakan sifat-sifat diatas untuk menunjukkan implikasi "jika P(k) benar maka P(k + 1) juga benar".

    Misalkan
    P(k) :  4k < 2k
    P(k + 1) :  4(k + 1) < 2k+1
    Jika diasumsikan P(k) benar untuk k ≥ 5, tunjukkan P(k + 1) juga benar !

    Ingat bahwa target kita adalah menunjukkan
    4(k + 1) < 2k+1 = 2(2k) = 2k + 2k  (TARGET)

    Kita dapat mulai dari ruas kiri pertaksamaan diatas
    4(k + 1) = 4k + 4
    4(k + 1) < 2k + 4        (karena 4k < 2k)
    4(k + 1) < 2k + 2k      (karena 4 < 4k < 2k)
    4(k + 1) = 2(2k)
    4(k + 1) = 2k+1

    Berdasarkan sifat transitif kita simpulkan
    4(k + 1) < 2k+1

    Mengapa 4k dapat berubah menjadi 2k ?
    Berdasarkan sifat 3, kita diperbolehkan menambahkan kedua ruas suatu pertaksamaan dengan bilangan yang sama, karena tidak akan merubah nilai kebenaran pertaksamaan tersebut. Karena 4k < 2k benar, akibatnya 4k + 4 < 2k + 4 juga benar.

    Darimana kita tahu, 4 harus diubah menjadi 2k ?
    Perhatikan target. Hasil sementara kita adalah 2k + 4 sedangkan target kita adalah 2k + 2k.
    Untuk k ≥ 5, maka 4 < 4k dan 4k < 2k adalah benar, sehingga 4 < 2k juga benar (sifat transitif). Akibatnya 2k + 4 < 2k + 2k  benar (sifat 3).


    Contoh 5
    Buktikan untuk setiap bilangan asli n ≥ 4 berlaku
    3n < 2n

    Jawab :
    P(n) :  3n < 2n
    Akan dibuktikan P(n) berlaku untuk n ≥ 4, n ∈ \(\mathbb{N}\)

    Langkah Dasar :
    Akan ditunjukkan P(4) benar
    3.4 = 12 < 24 = 16
    Jadi, P(4) benar

    Langkah Induksi :
    Asumsikan P(k) benar, yaitu
    3k < 2k,    k ≥ 4

    Akan ditunjukkan P(k + 1) juga benar, yaitu
    3(k + 1) < 2k+1

    3(k + 1) = 3k + 3
    3(k + 1) < 2k + 3               (karena 3k < 2k)
    3(k + 1) < 2k + 2k             (karena 3 < 3k < 2k)
    3(k + 1) = 2(2k)
    3(k + 1) = 2k+1

    Jadi, P(k + 1) juga benar

    Berdasarkan prinsip induksi matematika, terbukti bahwa P(n) berlaku untuk setiap bilangan asli n ≥ 4.


    Contoh 6
    Buktikan untuk setiap bilangan asli n ≥ 2 berlaku
     3n > 1 + 2n

    Jawab :
    P(n) :  3n > 1 + 2n
    Akan dibuktikan P(n) berlaku untuk n ≥ 2, n ∈ \(\mathbb{N}\)

    Langkah Dasar :
    Akan ditunjukkan P(2) benar
    32 = 9 > 1 + 2.2 = 5
    Jadi, P(1) benar

    Langkah Induksi :
    Asumsikan P(k) benar, yaitu
    3k > 1 + 2k,    k ≥ 2

    Akan ditunjukkan P(k + 1) juga benar, yaitu
    3k+1 > 1 + 2(k + 1)

    3k+1 = 3(3k)
    3k+1 > 3(1 + 2k)               (karena 3k > 1 + 2k)
    3k+1 = 3 + 6k
    3k+1 > 3 + 2k                    (karena 6k > 2k)
    3k+1 = 1 + 2k + 2
    3k+1 = 1 + 2(k + 1)

    Jadi, P(k + 1) juga benar

    Berdasarkan prinsip induksi matematika, terbukti bahwa P(n) berlaku untuk setiap bilangan asli n ≥ 2.


    Contoh 7
    Buktikan untuk setiap bilangan asli n ≥ 5 berlaku
     2n − 3 < 2n-2

    Jawab :
    P(n) :  2n − 3 < 2n-2
    Akan dibuktikan P(n) berlaku untuk n ≥ 5, n ∈ \(\mathbb{N}\)

    Langkah Dasar :
    Akan ditunjukkan P(5) benar
     2.5 − 3 = 7 < 25-2 = 8
    Jadi, P(1) benar

    Langkah Induksi :
    Asumsikan P(k) benar, yaitu
    2k − 3 < 2k-2 ,    k ≥ 5

    Akan ditunjukkan P(k + 1) juga benar, yaitu
    2(k + 1) − 3 < 2k+1-2

    2(k + 1) − 3 = 2k + 2 − 3
    2(k + 1) − 3 = 2k − 3 + 2
    2(k + 1) − 3 < 2k-2 + 2         (karena 2k − 3 < 2k-2)
    2(k + 1) − 3 < 2k-2 + 2k-2     (karena 2 < 2k − 3 < 2k-2)
    2(k + 1) − 3 = 2(2k-2)
    2(k + 1) − 3 = 2k+1-2

    Jadi, P(k + 1) juga benar

    Berdasarkan prinsip induksi matematika, terbukti bahwa P(n) berlaku untuk setiap bilangan asli n ≥ 5.


    Contoh 8
    Buktikan untuk setiap bilangan asli n ≥ 4 berlaku
    (n + 1)! > 3n

    Jawab :
    P(n) :  (n + 1)! > 3n
    Akan dibuktikan P(n) berlaku untuk n ≥ 4, n ∈ \(\mathbb{N}\)

    Langkah Dasar :
    Akan ditunjukkan P(4) benar
    (4 + 1)! > 34
    ruas kiri : 5! = 5.4.3.2.1 = 120
    ruas kanan : 34 = 81
    Jadi, P(1) benar

    Langkah Induksi :
    Asumsikan P(k) benar, yaitu
    (k + 1)! > 3k ,   k ≥ 4

    Akan ditunjukkan P(k + 1) juga benar, yaitu
    (k + 1 + 1)! > 3k+1

    (k + 1 + 1)! = (k + 2)!
    (k + 1 + 1)! = (k + 2)(k + 1)!
    (k + 1 + 1)! > (k + 2)(3k)            (karena (k + 1)! > 3k)
    (k + 1 + 1)! > 3(3k)                     (karena k + 2 > 3)
    (k + 1 + 1)! = 3k+1

    Jadi, P(k + 1) juga benar

    Berdasarkan prinsip induksi matematika, terbukti bahwa P(n) berlaku untuk setiap bilangan asli n ≥ 4.


    0 Response to "Induksi Matematika"

    Post a Comment

    Iklan Atas Artikel

    Iklan Tengah Artikel 1

    Iklan Tengah Artikel 2

    Iklan Bawah Artikel