Induksi Matematika (Induksi Matematika Sederhana, Induksi Matematika Umum, Kepada Induksi Matematika Kuat) Lengkap Dengan Contoh Soal Kepada Pembahasan

Induksi Matematika, ada yg tau apa itu induksi matematika?, Oke gini deh, misal kita ingin menjumlahkan $n$ buah bilangan asli pertama, kemudian kita nyari formulanya dari berbagi sumber, dengan 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 dengan 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, yg perlu kita lakukan adalah menjatuhkan domino pertama. Begitu pula dalam induksi matematika, yg 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, kalau 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 kalau $P(k)$ benar, maka $P(k+1)$ juga harus benar. Dengan terbuktinya pernyataan ini, kita bisa menjamin bahwa pernyataan $P(n)$ selalu benar untuk setiap bilangan asli $n$.

Analogi seperti domino tadi, merupakan analogi pembuktian dengan induksi matematika sederhana. Sementara dengan blog ini kita hendak membahas lnduksi matematika yg lebih lengkap, meliputi induksi matematika sederhana, induksi matematika umum, dengan 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 hendak 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 hendak 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 hendak 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 hendak 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, kalau kita tidak menjatuhkan domino pertama, dengan langsung menjatuhkan domino bagian tengah maupun urutan kesekian, maka tidak semua domino hendak terjatuh. Hal tersebut menunjukkan bahwa kedua langkah tersebut penting untuk dilakukan. Sebagai contoh, sekarang kita hendak 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 kalau 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 yg hendak kita buktikan. Jika pernyataan yg hendak kita buktikan "berlaku untuk semua bilangan asli" maka ya, langkah dasar kita gunakan $n=1$. Namun adakalanya pernyataan yg hendak kita buktikan tidak berlaku untuk semua bilangan asli $n$, melainkan terdapat suatu nilai terkecil yg 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 hendak membuktikan bahwa $P(n)$ benar untuk setiap bilangan asli $n$ dengan $ n\geq 4$.

Langkah dasar:
kita hendak 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$             kalau 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 hendak 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$ dengan 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 dengan induksi dasar dengan 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$ , dengan kita juga harus membuktikan kebenaran $P(k+1)$.

gerah



langkah-langkah dalam induksi kuat:
gerah

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$ bisa dinyatakan sebagai perkalian dari satu maupun lebih bilangan prima.

Jawab:

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

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

1. Jika $k+1$ merupakan bilangan prima, maka $k+1$ bisa 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$ dengan $k+1$ itu sendiri, ada bilangan asli lain yg bisa membagi $k+1$, kita misalkan $a$ dengan 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$ dengan $b$ yg mungkin adalah $2, 3, 4, \cdots, k$. berdasarkan hipotesis, kita mengetahui bahwa bilangan-bilangan tersebut merupakan hasil kali satu maupun lebih bilangan prima. Maka $ab$ bisa pula dinyatakan sebagai hasil kali satu maupun lebih bilangan prima, dengan demikian $k+1$ juga bisa dinyatakan sebagai perkalian satu maupun 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 dengan 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 dengan saran.
semoga bermanfaat

$\blacksquare$ Denih Handayani, 26 Juli 2020

gerah