Induksi Matematika (Induksi Matematika Sederhana, Induksi Matematika Umum, dan Induksi Matematika Kuat) Lengkap dengan Contoh Soal dan Pembahasan

Induksi Matematika, ada yang tau apa itu induksi matematika?, Oke gini deh, misal kita ingin menjumlahkan $n$ buah bilangan asli pertama, kemudian kita nyari formulanya dari berbagi sumber, dan ternyata kita menemukan sebuah formula bahwa jumlah $n$ buah bilangan asli pertama bisa ditentukan dengan formula $S_n=\frac{1}{2} n (n+1)$, nah pertanyaannya, apakah kalian percaya/yakin bahwa formula itu benar dan berlaku untuk setiap bilangan asli $n$ ?  kita perlu sebuah tools untuk membuktikan kebenaran formula tersebut, ya salah satunya adalah dengan Induksi Matematika. Jadi kalau menurut bahasa buku bisa dibilang induksi matematika adalah cara membuktikan suatu pernyataan $P(n)$ selalu benar untuk setiap bilangan asli $n$.

Waktu masih kecil mungkin kalian pernah bermain domino dengan cara menyusunnya seperti gambar di atas. Nah, induksi matematika analoginya mirip seperti permainan tersebut. Analoginya seperti ini:

1. Dalam permainan domino, yang perlu kita lakukan adalah menjatuhkan domino pertama. Begitu pula dalam induksi matematika, yang pertama kita lakukan adalah membuktikan pernyataan $P(n)$ bernilai benar untuk $n=1$.
2. Jika domino pertama jatuh, maka domino kedua juga harus jatuh, Jika domino kedua jatuh, maka domino ketiga juga harus jatuh, demikian seterusnya. bisa kita simpulkan, jika domino ke-$k$ jatuh, maka domino ke-$(k+1)$ juga harus jatuh, dengan demikian kita bisa menjamin bahwa seluruh domino dalam deretan tersebut juga pasti jatuh. Demikian juga dalam induksi matematika, kita harus membuktikan jika $P(k)$ benar, maka $P(k+1)$ juga harus benar. Dengan terbuktinya pernyataan ini, kita dapat menjamin bahwa pernyataan $P(n)$ selalu benar untuk setiap bilangan asli $n$.

Analogi seperti domino tadi, merupakan analogi pembuktian dengan induksi matematika sederhana. Sementara pada blog ini kita akan membahas lnduksi matematika yang lebih lengkap, meliputi induksi matematika sederhana, induksi matematika umum, dan induksi matematika kuat.

Induksi Matematika Sederhana

berdasarkan analogi di atas, kita bisa menyimpulkan bahwa langkah-langkah pembuktian dengan induksi sederhana untuk membuktikan suatu pernyataan $P(n)$ adalah sebagai berikut:

1. Buktikan bahwa $P(1)$ benar.    (langkah dasar)
2. Misalkan $P(k)$ benar, gunakan hal ini untuk membuktikan bahwa $P(k+1)$ juga benar (langkah induksi)

Contoh 1

Buktikan bahwa untuk setiap setiap bilangan asli $n$ berlaku:
$$1+2+3+\cdots+n=\frac{1}{2} n(n+1)$$
Jawab:
Kita gunakan induksi matematika, dengan
$$P(n)\equiv 1+2+3+\cdots+n=\frac{1}{2} n(n+1)$$
Pertama, kita akan membuktikan kebenaran $P(1)$
$P(1)\equiv 1=\frac{1}{2}(1)(1+1)=1$  (benar)

Kedua, kita asumsikan $P(k)$ benar.
$P(k)\equiv 1+2+3+\cdots+k=\frac{1}{2}k(k+1)$

dengan menggunakan hal di atas, kita akan membuktikan $P(k+1)$, yaitu:
$P\left ( k+1 \right ) \equiv 1+2+3+...+k+\left ( k+1 \right )=\frac{1}{2}\left ( k+1 \right )\left ( \left ( k+1 \right )+1 \right )$

dari persamaan terakhir, maka:
Ruas Kiri
$\underset{\frac{1}{2}k(k+1)}{\underbrace{1+2+3+...k}}+\left ( k+1 \right )\\=\frac{1}{2}k\left ( k+1 \right )+\left ( k+1 \right )\\=\left ( k+1 \right )\left ( \frac{1}{2}k+1 \right )\\=\frac{1}{2}\left ( k+1 \right )\left ( k+2 \right )$

Ruas Kanan:
$\frac{1}{2}\left ( k+1 \right )\left ( \left (k+1  \right )+1 \right )\\=\frac{1}{2}\left ( k+1 \right )\left ( k+2 \right )$

karena ruas kiri $=$ ruas kanan, maka pernyataan tersebut benar untuk setiap bilangan asli $n$

Contoh 2

Buktikan bahwa "untuk semua bilangan asli $n$, jumlah $n$ bilangan ganjil berurutan, pertama sama dengan $n^2$"

Jawab:
kalimat di atas bisa kita tulis:
$$1+3+5+\cdots +(2n-1)=n^2$$

Pertama, kita akan membuktikan kebenaran $P(1)$
$P(1)\equiv(2\times 1 - 1)=1^2=1$    (benar)

Kedua, kita asumsikan $P(k)$ benar.
$ P(k)\equiv 1+3+5+\cdots+(2k-1)=k^2 $

Dengan menggunakan hal ini, kita akan membuktikan $P(k+1)$:

$P(k+1) \equiv 1+3+5+\cdots +(2k-1)+(2(k+1-1))=(k+1)^2$

dari persamaan terakhir, maka:
Ruas Kiri
$\underset{k^2}{\underbrace{1+3+5+...+\left ( 2k-1 \right )}}+\left ( 2\left ( k+1 \right )-1 \right )\\=k^2+2k+1\\=\left ( k+1 \right )^2$


Ruas Kanan
$(k+1)^2$

karena ruas kiri $=$ ruas kanan, maka pernyataan tersebut benar untuk setiap bilangan asli $n$

Kesalahan dalam Pembuktian Induksi Matematika
Perlu diperhatikan, kedua langkah dalam pembuktian menggunakan induksi matematika yaitu langkah dasar dan langkah induksi, kedua langkah tersebut harus dilakukan. Seperti halnya analogi jatuhnya domino tadi, jika kita tidak menjatuhkan domino pertama, dan langsung menjatuhkan domino bagian tengah atau urutan kesekian, maka tidak semua domino akan terjatuh. Hal tersebut menunjukkan bahwa kedua langkah tersebut penting untuk dilakukan. Sebagai contoh, sekarang kita akan membuktikan suatu pernyataan dengan induksi matematika tanpa langkah dasar:

Buktikan bahwa untuk setiap bilangan asli $n$ berlaku:
$$1+2+3+...+n=\frac{1}{8}(2n+1)^2$$

Jawab:
Kita gunakan induksi matematika:
$$P(n)=1+2+3+\cdots +n=\frac{1}{8}\left ( 2n+1 \right )^2$$

Langkah Dasar : (untuk bagian ini langkah dasar kita coba lewati)

Langkah Induksi:
Misalkan $P(k)$ benar.
$P(k) \equiv 1+2+3+\cdots +k=\frac{1}{8}\left ( 2k+1 \right )^{2}$

Persamaan di atas kita gunakan untuk membuktikan $P(k+1)$:
$P(k+1)\equiv 1+2+3+\cdots+k+(k+1)=\frac{1}{8}\left ( 2k+3 \right )^2$

Ruas Kiri:
$\underset{\frac{1}{8}\left ( 2k+1 \right )^2}{\underbrace{1+2+3+\cdots+k}}+\left ( k+1 \right )\\=\frac{1}{8}\left ( 2k+1 \right )^2+\left ( k+1 \right )\\=\frac{1}{8}\left ( 4k^2+4k+1+8k+8 \right )\\=\frac{1}{8}\left ( 4x^2+12x+9 \right )\\=\frac{1}{8}\left ( 2x+3 \right )^2$

dengan jelas kita lihat bahwa hasil ruas kiri sama dengan ruas kanan, seolah-olah pernyataan tersebut terbukti benar, namun jika kita substitusikan $n=1$ maka kita peroleh

$P(1)\equiv 1=\frac{1}{8}(2\times 1+1)^2\Leftrightarrow 1=\frac{9}{8}$ (salah)


dengan demikian, kedua langkah induksi harus kita lakukan untuk memastikan kebenaran suatu pernyataan.



Induksi Matematika Umum/dirapatkan
Sekarang timbul pertanyaan, apakah untuk langkah dasar harus selalu menggunakan $n=1$? jawabannya tergantung pernyataan yang akan kita buktikan. Jika pernyataan yang akan kita buktikan "berlaku untuk semua bilangan asli" maka ya, langkah dasar kita gunakan $n=1$. Namun adakalanya pernyataan yang akan kita buktikan tidak berlaku untuk semua bilangan asli $n$, melainkan terdapat suatu nilai terkecil yang menjadi batas bawah dimana pernyataan tersebut berlaku. Misalnya nilai terkecil tersebut kita misalkan sebagai $n_0$ dengan $n_0$ bilangan bulat, maka langkah dasar kita ganti dengan membuktikan kebenaran $P(n_0)$. Secara umum langkah-langkahnya bisa kita tulis sebagai berikut:

1. Buktikan bahwa $P(n_0)$ benar.    (langkah dasar)
2. Misalkan $P(k)$ benar untuk $k > n_0$, gunakan hal ini untuk membuktikan bahwa $P(k+1)$ juga benar (langkah induksi)

langkah-langkah di atas, disebut sebagai langkah-langkah pembuktian induksi matematika umum.

Contoh 3

Buktikan bahwa
$$n^2 \geq 2n+7$$
untuk setiap bilangan asli $n\geq 4$

Jawab:
Kita gunakan induksi matematika umum, dengan:
$P(n)\equiv n^2 \geq 2n+7$
Kita akan membuktikan bahwa $P(n)$ benar untuk setiap bilangan asli $n$ dengan $ n\geq 4$.

Langkah dasar:
kita akan membuktikan kebenaran $P(4)$
$P(4)\equiv 4^2\geq 2(4)+7\Leftrightarrow 16\geq 15$ (Benar)

Langkah Induksi:
kita misalkan $P(k)$ benar untuk $k \geq 4$
$P(k)\equiv k^2 \geq 2k+7$ untuk $ k \geq 4$ (hipotesis)

dari hipotesis kita peroleh:
$k^2 \geq 2k+7$             jika kedua ruas kita tambah $2k+1$, maka:
$k^2+2k+1 \geq 4k+8$
$(k+1)^2 \geq 4k+8$
$(k+1)^2 \geq 2(k+1)+2(k+3)$ karena $k \geq 4$ maka $k+3 \geq 7$
$(k+1)^2 \geq 2(k+1)+2(7)$
$(k+1)^2 \geq 2(k+1)+14$

dengan menggunakan hal di atas, kita akan membuktikan $P(k+1)$, yitu:
$$P(k+1) \equiv (k+1)^2 \geq 2(k+1)+7$$
karena $(k+1)^2 \geq 2(k+1)+14$ pada hipotesis kita misalkan benar, maka $(k+1)^2 \geq 2(k+1)+7$ benar (karena 14 > 7)
dengan demikian pernyataan tersebut benar untuk setiap bilangan asli  $n\geq 4$

Induksi Kuat
Jika pada induksi dasar dan induksi umum hipotesis induksi hanya terdiri atas anggapan kebenaran satu pernyataan, yaitu $P(k)$, beda halnya dengan induksi kuat. Pada induksi kuat, dalam hipotesis kita menganggap semua pernyataan benar.
$$P(n_0), P(n_0+1), P(n_0+2), \cdots, P(k)$$
yaitu, semua pernyataan untuk nilai $n$ dari batas bawah sampai dengan $k$ , dan kita juga harus membuktikan kebenaran $P(k+1)$.





langkah-langkah dalam induksi kuat:

1. Buktikan bahwa $P(n_0)$ benar.    (langkah dasar)
2. misalkan $P(n_0), P(n_0+1), P(n_0+2), \cdots, P(k)$ benar untuk $k\geq n_0$ gunakan hal ini untuk membuktikan bahwa $P(k+1)$ juga benar (langkah induksi)

Contoh 4

Buktikan bahwa setiap bilangan bulat positif $n\geq 2$ dapat dinyatakan sebagai perkalian dari satu atau lebih bilangan prima.

Jawab:

Langkah dasar:
Jika $n=2$, dan $2$ sendiri merupakan bilangan prima, maka jelas pernyataan ini benar.

Langkah induksi:
misalkan pernyataan bahwa $2, 3, 4, \cdots, k$ dapat dinyatakan sebagai perkalian dari satu atau lebih bilangan prima, akan dibuktikan bahwa $k+1$ dapat dinyatakan sebagai hasil kali satu atau lebih bilangan prima. Ada dua kemungkinan nilai $k+1$ bisa prima, atau komposit (bukan prima):

1. Jika $k+1$ merupakan bilangan prima, maka $k+1$ dapat dinyatakan sebagai hasil kali bilangan prima, yaitu $k+1$ itu sendiri.
2. Jika $k+1$ bukan bilangan prima, maka $k+1$ memiliki pembagi selain $1$ dan $k+1$ itu sendiri, ada bilangan asli lain yang dapat membagi $k+1$, kita misalkan $a$ dan hasil baginya kita misalkan $b$, dapt kita tulis:$$\frac{k+1}{a}=b\Leftrightarrow k+1=ab$$Karena $2\leq a,b\leq k$, maka nilai $a$ dan $b$ yang mungkin adalah $2, 3, 4, \cdots, k$. berdasarkan hipotesis, kita mengetahui bahwa bilangan-bilangan tersebut merupakan hasil kali satu atau lebih bilangan prima. Maka $ab$ dapat pula dinyatakan sebagai hasil kali satu atau lebih bilangan prima, dengan demikian $k+1$ juga dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima.

Jadi, terbukti bahwa $P(k+1)$ benar, maka pernyataan tersebut benar untuk setiap bilangan asli $n \geq 2$.

Silakan gabung di Fans Page Facebook, Channel Telegram untuk memperoleh update terbaru, dan Subscribe Channel YouTube m4th-lab untuk memperoleh video pembelajaran matematika secara gratis, untuk mengikuti tautan klik pada tombol di bawah ini:

m4th-lab Youtube Channel: 

m4th-lab Facebook Fans Page:

m4th-lab Telegram Channel:

@banksoalmatematika

Jika ada kekeliruan, silahkan isi komentar dengan senang hati saya menerima kritik dan saran.
semoga bermanfaat

$\blacksquare$ Denih Handayani, 26 Juli 2017