Induksi Matematika (Induksi Matematika Sederhana, Induksi Matematika Umum, Dan Induksi Matematika Kuat) Lengkap Dengan Teladan Soal Dan Pembahasan

Induksi Matematika, ada yang tau apa itu induksi matematika?, Oke gini deh, misal kita ingin menjumlahkan $n$ buah bilangan orisinil pertama, kemudian kita nyari formulanya dari membuatkan sumber, dan ternyata kita menemukan sebuah formula bahwa jumlah $n$ buah bilangan orisinil pertama sanggup 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 orisinil $n$ ?  kita perlu sebuah tools untuk menunjukan kebenaran formula tersebut, ya salah satunya ialah dengan Induksi Matematika. Jadi kalau berdasarkan bahasa buku sanggup dibilang induksi matematika ialah cara menunjukan suatu pernyataan $P(n)$ selalu benar untuk setiap bilangan orisinil $n$.

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

1. Dalam permainan domino, yang perlu kita lakukan ialah menjatuhkan domino pertama. Begitu pula dalam induksi matematika, yang pertama kita lakukan ialah menunjukan 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. sanggup kita simpulkan, bila domino ke-$k$ jatuh, maka domino ke-$(k+1)$ juga harus jatuh, dengan demikian kita sanggup menjamin bahwa seluruh domino dalam formasi tersebut juga niscaya jatuh. Demikian juga dalam induksi matematika, kita harus menunjukan bila $P(k)$ benar, maka $P(k+1)$ juga harus benar. Dengan terbuktinya pernyataan ini, kita sanggup menjamin bahwa pernyataan $P(n)$ selalu benar untuk setiap bilangan orisinil $n$.

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

Induksi Matematika Sederhana

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

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

Contoh 1

Buktikan bahwa untuk setiap setiap bilangan orisinil $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 menunjukan 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 memakai hal di atas, kita akan menunjukan $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 orisinil $n$

Contoh 2

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

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

Pertama, kita akan menunjukan 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 memakai hal ini, kita akan menunjukan $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 orisinil $n$

Kesalahan dalam Pembuktian Induksi Matematika
Perlu diperhatikan, kedua langkah dalam pembuktian memakai induksi matematika yaitu langkah dasar dan langkah induksi, kedua langkah tersebut harus dilakukan. Seperti halnya analogi jatuhnya domino tadi, bila kita tidak menjatuhkan domino pertama, dan eksklusif menjatuhkan domino bab tengah atau urutan kesekian, maka tidak semua domino akan terjatuh. Hal tersebut mengatakan bahwa kedua langkah tersebut penting untuk dilakukan. Sebagai contoh, kini kita akan menunjukan suatu pernyataan dengan induksi matematika tanpa langkah dasar:

Buktikan bahwa untuk setiap bilangan orisinil $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 bab 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 menunjukan $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 terperinci kita lihat bahwa hasil ruas kiri sama dengan ruas kanan, seolah-olah pernyataan tersebut terbukti benar, namun bila 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 memakai $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 orisinil $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 menunjukan kebenaran $P(n_0)$. Secara umum langkah-langkahnya sanggup 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 menunjukan 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 orisinil $n\geq 4$

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

Langkah dasar:
kita akan menunjukan 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$             bila 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)$ alasannya $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 memakai hal di atas, kita akan menunjukan $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 orisinil  $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 hingga dengan $k$ , dan kita juga harus menunjukan 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 menunjukan bahwa $P(k+1)$ juga benar (langkah induksi)

Contoh 4

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

Jawab:

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

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

1. Jika $k+1$ merupakan bilangan prima, maka $k+1$ sanggup dinyatakan sebagai hasil kali bilangan prima, yaitu $k+1$ itu sendiri.
2. Jika $k+1$ bukan bilangan prima, maka $k+1$ mempunyai pembagi selain $1$ dan $k+1$ itu sendiri, ada bilangan orisinil lain yang sanggup 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 ialah $2, 3, 4, \cdots, k$. berdasarkan hipotesis, kita mengetahui bahwa bilangan-bilangan tersebut merupakan hasil kali satu atau lebih bilangan prima. Maka $ab$ sanggup pula dinyatakan sebagai hasil kali satu atau lebih bilangan prima, dengan demikian $k+1$ juga sanggup dinyatakan sebagai perkalian satu atau lebih bilangan prima.

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

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

Soal Terbaru Youtube Channel: 

Soal Terbaru Facebook Fans Page:

Soal Terbaru Telegram Channel:

@banksoalmatematika

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

$\blacksquare$ Denih Handayani, 26 Juli 2017

Share this post