Prinsip Induksi Matematika

credit to : geralt/pixaby.com

Hai sobat matematika !

Matematika memberikan banyak persamaan ataupun ketaksamaan yang diberikan dalam bentuk sifat yang berlaku untuk semua bilangan bulat positif.

Misalkan saja untuk setiap bilangan bulat positif $n$ berlaku dua sifat berikut

1. $n! \leq n^{n}$
2. $n^{3}-n$ habis dibagi 3.
3. Himpunan dengan $n$ elemen mempunyai banyak subset $2^{n}$
4. Jumlah $n$ bilangan bulat positif pertama adalah $\frac{n(n-1)}{2}$

Membuktikan beberapa sifat di atas memerlukan alat pembuktian yang biasa disebut induksi matematika.

Pembuktian dengan induksi matematika mempunyai dua langkah.

Langkah pertama adalah membuktikan pernyataan benar untuk kasus pada bilangan 1.
Langkah kedua menunjukkan bahwa jika suatu pernyataan berlaku untuk suatu bilangan bulat positif maka pernyataan tersebut juga berlaku untuk bilangan bulat positif selanjutnya yang lebih besar.

Induksi matematika merupakan kunci penting untuk membuktikan banyak hal. Memahami bagaimana membaca dan menkontruksi induksi matematika adalah tujuan utama dalam mempelajari matematika diskrit

Pendahuluan

Untuk memahami konsep induksi matematika ini, saya akan mengajak Anda untuk berimajinasi.

Andaikan Anda mempunyai tangga dengan tak hingga anak tangga. Anda ingin tahu apakah Anda bisa meraih semua langkah pada tangga tersebut.

Andaikan dua hal ini merupakan fakta tentang Anda

Anda bisa mencapai anak tangga pertama.
Jika Anda dapat meraih suatu anak tangga maka Anda bisa meraih anak tangga selanjutnya

Pertanyaannya adalah apakah Anda bisa meraih setiap anak tangga dari tangga tak terhingga tersebut?

Berdasarkan point 1, kita tahu bahwa Anda bisa meraih anak tangga pertama. Selanjutnya, karena kita tahu kalau Anda bisa melangkah pada anak tangga pertama, berdasarkan point 2 maka Anda juga bisa meraih anak tangga kedua.

Karena Anda dapat meraih anak tangga kedua, dengan menggunakan point 2 lagi, maka Anda bisa melangkah di anak tangga ketiga. Jika cara seperti ini dilanjutkan, maka Anda bisa meraih anak tangga keempat, kelima dan seterusnya.

Sebagai contoh, setelah menggunakan point 2 sebanyak 1000 kali, maka dapat disimpulkan Anda dapat meraih anak tangga ke-1001.

Apakah kita bisa menyimpulkan kalau Anda bisa meraih setiap anak tangga dari tangga tak hingga tersebut?

Baca Juga : Kunang-kunang penyelamat perusahaan.

Jawabanya BISA. Pembuktian yang dipakai menggunakan teknik induksi matematika.

Yaitu kita bisa tunjukkan bahwa $P(n)$ adalah benar untuk setiap bilangan bulat $n$, dengan $P(n)$ adalah pernyataan bahwa Anda dapat meraih anak tangga ke-$n$.

Induksi Matematika

Secara umum, induksi matematika adalah pembuktian matematika yang digunakan untuk membuktikan pernyataan bahwa $P(n)$ benar untuk semua bilangan bulat positif $n$.

Pembuktian melalui induksi matematika menggunakan dua tahapan.

Langkah pertama dari induksi matematika adalah menunjukkan bahwa $P(1)$ adalah pernyataan benar.

Langkah kedua adalah induktif. Tahap ini menunjukkan bahwa untuk semua bilangan builat positif $k$ berlaku jika $P(k)$ adalah benar maka $P(k+1)$ juga benar.

PRINSIP INDUKSI MATEMATIKA
Untuk membuktikan bahwa $P(n)$ benar untuk semua bilangan bulat positif $n$ maka dilakukan dua langkah
LANGKAH DASAR; Buktikan bahwa $P(1)$ benar
LANGKAH INDUKTIF; Tunjukkan bahwa $P(k) \rightarrow P(k+1)$ adalah pernyataan benar untuk semua bilangan bulat positif $k$

Asumsi bahwa $P(k)$ benar pada langkah induktif disebut hipotesis induktif.

Contoh Pembuktian dengan Induksi Matematika

Pembuktian Formula Penjumlahan
Penggunaan induksi matematika pada bagian ini adalah untuk membuktian beberapa sifat pada penjumlahan. Seperti yang diketahui, induksi matematika cocok dengan pembuktian untuk sifat demikian .

Akan tetapi tidak menutup kemungkinan pembuktian dengan cara yang selain induksi matematika seperti layaknya sebuah teorema yang memiliki banyak alternatif pilihan pembuktian.

Contoh Soal 1
Tunjukkan bahwa jika $n$ adalah bilangan bulat pertama maka$$1+2+\cdots+n=\frac{n(n+1)}{2}$$
Pembahasan Contoh Soal 1
Misalkan $P(n)$ adalah pernyataan bahwa jumlah $n$ bilangan bulat positif pertama adalah $\frac{n(n+1)}{2}$.

Untuk melakukan pembuktian ini, Anda harus menunjukkan bahwa $P(n)$ berlaku untuk $n=1, 2, 3, \cdots$.

Anda harus menunjukkan $P(1)$ benar dan pernyataan implikasi jika $P(k)$ maka $P(k+1)$ adalah benar untuk semua $k=1,2,3, \cdots$
LANGKAH DASAR; Karena $1=\frac{1(1+1)}{2}$ maka $P(1)$ benar.
LANGKAH INDUKTIF; Misalkan $P(k)$ benar untuk $k$ sebarang bilangan bulat positif. Yaitu Anda mengasumsikan bahwa$$1+2+\cdots+k=\frac{k(k+1)}{2}$$
Selanjutnya akan ditunjukkan $P(k+1)$ benar, yaitu$$1+2+3+\cdots+k+(k+1)=\frac{(k+1)\left[(k+1)+1\right]}{2}=\frac{(k+1)(k+2)}{2}$$
Berdasarkan asumsi $P(k)$ tadi, diperoleh$$
\begin{array}{lcl}
1+2+3+\cdots+k+(k+1) & = & \frac{k(k+1)}{2}+(k+1) \\
&=& \frac{k(k+1)+2(k+1)}{2}\\
&=& \frac{(k+1)(k+2)}{2}
\end{array}$$Persamaan terakhir melihatkan bahwa $P(k+1)$ adalah benar dengan asumsi $P(k)$ benar.

Berdasarkan langkah di atas, Anda sudah mnegerjakan pembuktian langkah dasar dan langkah induktif dari induksi matematika. Oleh karena itu, berdasarkan prinsip pembuktian induksi matematika terbukti pernyataan $P(n)$ benar untuk semua bilangan bulat positif $n$, yaitu $1+2+\cdots+n=\frac{n(n+1)}{2}$. $\blacksquare$

Sebagai informasi untuk Anda, induksi matematika bukan merupakan suatu alat untuk menemukan sifat, lemma ataupun teorema yang berlaku untuk semua bilangan bulat positif $n$.

Induksi matematika lebih cocok sebagai metode pembuktian suatu dugaan yang dihasilkan dari suatu fenomena atau percobaan.

Baca Juga : Petani dan Persamaan Kuadrat

Contoh berikut memberikan ilustrasi yang saya maksud

Contoh Soal 2
Beri dugaan untuk memberikan formula jumlahan $n$ bilangan bulat positif ganjil pertama. Kemudian buktikan dugaan Anda dengan induksi matematika.

Pembahasan Contoh Soal 2
Jumlahan $n$ bilangan bulat ganjil positif pertama untuk $n=1,2,3,4,5$ adalah

$
\begin{array}{lll}
1=1 & 1+3=4 & 1+3+5=9 \\
1+3+5+7=16 & 1+3+5+7+9=25 &
\end{array}
$

Hasil yang Anda peroleh pada jumlahan 5 bilangan bulat ganjil positif pertama di atas merupakan alasan yang logis jika dugaan formula yang dimaksud adalah $n_{2}$.

Anda perlu suatu metode untuk membuktikan dugaan Anda. Induksi matematika yang akan kita gunakan kali ini.

Misalkan $P(n)$ adalah pernyataan bahwa jumlahan $n$ bilangan bulat positif ganjil pertama adalah $n^{2}$. Jadi dugaan adalah $P(n)$ adalah benar untuk semua bilangan bulat positif.

Langkah pembuktian induksi matematika untuk $P(n)$ sebagai berikut
LANGKAH DASAR; $P(1)$ menyatakan bahwa jumlah bilangan bulat positif ganjil pertama adalah $1^{2}$. Hal ini benar karena jumlahan bilangan bulat positif pertama adalah 1.
LANGKAH INDUKTIF; Langkah induksi matematika pada bagian ini adalah menunjukkan proposisi $P(k)\rightarrow P(k+1)$ benar untuk setiap bilangan bulat positif $k$.
Langkah pertama adalah mengasumsikan bahwa $P(k)$ benar yaitu untuk setiap bilangan bulat positif $k$ berlaku$$
1+3+5+\cdot+(2k-1)=k^{2}
$$Rumusan di atas menunjukkan bahwa bilangan bulat positif ganjil ke-$k$ adalah $(2k-1)$.
Akan ditunjukkan bahwa $P(k+1)$ benar, yaitu$$1+3+5+\cdots+(2k-1)+(2k+1)=(k+1)^{2}$$Jadi jika diasumsikan $P(k)$ benar maka diperoleh$$
\begin{array}{lll}
1+3+5+\cdots+(2k-1)+(2k+1) & = & \left[1+3+\cdots+(2k-1)\right]+(2k+1) \\
& = & k^{2}+(2k+1)\\
&=& k^{2}+2k+1\\
&=& (k+1)^{2}
\end{array}$$Berdasarkan prinsip induksi matematika, pembuktian $P(n)$ benar untuk semua bilangan bulat positif. Yaitu $1+3+\cdots+(2n-1)=n^{2}$ untuk bilangan bulat positif $n$. $\blacksquare$

Seringkali, Anda akan dihadapkan masalah untuk membuktikan $P(n)$ benar untuk $n=b,b+1,b+2, \cdots$ dengan $b$ adalah bilangan bulat selain 1.

Anda tetap dapat melakukan pembuktian tersebut dengan induksi matematika selama Anda merubah langkah dasar $P(1)$ diganti dengan $P(b)$.

Dengan kata lain, Induksi matematika untuk membuktikan $P(n)$ benar untuk $n=b,b+1,b+2, \cdots$ untuk $b \neq 1$ adalah membuktikan $P(b)$ pada langkah dasar. Selanjutnya langkah induktif membuktikan pernyataan $P(k) \rightarrow P(k+1)$ benar untuk $k=b, b+1, b+2, \cdots$.

Ilustrasi dari masalah di atas dapat dilihat pada contoh berikut

Contoh Soal 3
Tunjukkan dengan induksi matematika bahwa $$1+2+2^{2}+\cdots+2^{n}=2^{n+1}-1$$untuk semua bilangan bulat tak-negatif.

Pembahasan Contoh Soal 3
Misalkan $P(n)$ adalah proposisi bahwa $1+2+2^{2}+\cdots+2^{n}=2^{n+1}-1$ untuk semua bilangan bulat $n$.
LANGKAH DASAR; $P(0)$ adalah benar karena $2^{0}=1=2^{1}-1$.
LANGKAH INDUKTIF; Untuk hipotesis induksi, kita asumsikan bahwa $P(k)$ benar untuk sebarang bilangan bulat taknegatif yaitu$$1+2+2^{2}+\cdots+2^{k}=2^{k+1}-1$$Selanjutnya akan dibuktikan bahwa $P(k+1)$ benar, yaitu$$1+2+2^{2}+\cdots+2^{k}+2^{k+1}=2^{k+2}-1$$Dengan mengasumsikan bahwaa $P(k)$ benar maka diperoleh
$
\begin{array}{lll}
1+2+2^{2}+\cdots+2^{k}+2^{k+1} & = & \left(1+2+2^{2}+\cdots+2^{k}\right)+2^{k+1} \\
& = & \left(2^{k+1}-1\right) +2^{k+1}\\
&=& 2\cdot 2^{k+1} -1 \\
&=& 2^{k+2} -1
\end{array}
$
Berdasarkan prinsip induksi matematika maka benar pernyataan $P(n)$ yaitu $1+2+2^{2}+\cdots+2^{n}=2^{n+1}-1$ untuk semua bilangan bulat tak-negatif.$\blacksquare$

Contoh soal 3 merupakan kasus khusus pada deret geometri dengan rasio $r=2$. Sedangkan untuk rumus jumlahan deret geometri dapat dilihat pada contoh soal 4 di bawah

Contoh Soal 4.
Buktikan bahwa rumusan untuk deret geometri berikut$$\sum_{j=0}^{n}ar^{j}=a+ar+ar^{2}+\cdots+ar^{n}=\frac{ar^{n+1}-a}{r-1}$$ketika $r\neq 1$ dengan $n$ adalah bilangan bulat tak negatif.

Pembahasan Contoh Soal 4.
Untuk membuktikan formula tersebut dengan menggunakan induksi matematika, dimisalkan $P(n)$ adalah pernyataan bahwa jumlahan suku $n+1$ pertama dari deret geometri adalah benar.

LANGKAH DASAR; $P(0)$ benar karena$$\frac{ar^{0+1}-a}{r-1}=\frac{ar-a}{r-1}=\frac{a(r-1)}{r-1}=a$$LANGKAH INDUKTIF; Hipotesis induksi adalah pernyataan $P(k)$ benar dengan $k$ sebarang bilangn bulat tak negatif. Yaitu, pernyataan $P(k)$ adalah$$a+ar+ar^{2}+\cdots+ar^{k}=\frac{ar^{k+1}-a}{r-1}$$untuk membuktikan $P(k+1)$ benar yaitu$$a+ar+ar^{2}+\cdots+ar^{k}+ar^{k+1}=\frac{ar^{k+2}-a}{r-1}$$Berdasarkan hipotesis induksi $P(k)$ didapatkan $$a+ar+ar^{2}+\cdots+ar^{k}+ar^{k+1}=\frac{ar^{k+1}-a}{r-1}+ar^{k+1}$$Jika dilihat kembali ruas kanan pada persamaan di atas
$
\begin{array}{lll}
\frac{ar^{k+1}-a}{r-1}+ar^{k+1} & = & \frac{ar^{k+1}-a}{r-1}+\frac{ar^{k+2}-ar^{k+1}}{r-1} \\
& = & \frac{ar^{k+2}-a}{r-1}
\end{array}
$
Jadi dengan menggabungkan dua persamaan di atas diperoleh$$a+ar+ar^{2}+\cdots+ar^{k}+ar^{k+1}=\frac{ar^{k+1}-a}{r-1}+ar^{k+1}$$Hal ini menunjukkan bahwa $P(k)$ benar maka $P(k+1)$ juga benar. Oleh karena itu rumusan jumlahan deret geometri di atas adalah benar. $\blacksquare$

Pembuktian Ketaksamaan
Induksi Matematika juga bisa digunakan untuk membuktikan ketaksamaan yang berlaku di semua bilangan bulat positif yang leih besar dari suatu bilangan bulat khusus.

Contoh 5 sampai contoh 7 mengilustasikan penggunaan induksi matematika untuk pertidaksamaan di matematika

Contoh soal 5.
Gunakan induksi matematika untuk membuktikan $$n<2^{n}$$untuk semua bilangan bulat positif $n$

Pembahasan Contoh Soal 5.
Misalkan $P(n)$ adalah pernyataan untuk $n<2^{n}$
LANGKAH DASAR; Karena $1<2^{1}=2$ maka $P(1)$ benar.
LANGKAH INDUKTIF; Misalkan $P(k)$ benar untuk sebarang bilangan bulat positif $k$ yaitu $$k<2^{k}$$ adalah pernyataan benar.

Karena $P(k)$ benar maka persamaan di atas ditambah dengan 1 kedua ruas dan fakta bahwa $1 \leq 2^{k}$ sehingga
\[
\begin{array}{lll}
k+1 & < &2^{k}+1 \\
& \leq & 2^{k}+2^{k} \\
&=& 2\cdot 2^{k} \\
&=& 2^{k+1}
\end{array}
\]
Hal ini menunjukkan bahwa $P(k+1)$, yaitu $k+1<2^{k+1}$ sehingga pembuktian secara induksi matematika sudah selesai.$\blacksquare$

Contoh Soal 6.
Buktikan dengan emakai induksi matematika bahwa$$2^{n}<n!$$untuk setiap bilangan bulat $n$ dengan $n \geq 4$

Pembahasan Contoh Soal 6.
Misalkan $P(n)$ adaah pernyataan untuk $2^{n}<n!$
LANGKAH DASAR; langkah induksi matematika pada tahap ini terbukti karena $2^{4}=16 < 24 = 4 !$ sehingga $P(4)$ benar.
LANGKAH INDUKTIF; Dimisalkan $P(k)$ benar, yaitu $2^{k}<k!$ untuk sebarang bilangan bulat $k \geq 4$. Akan ditunjukkan bahwa $P(k+1)$ juga benar, yaitu $2^{k+1}< (k+1)!$ benar untuk $k \geq 4$.
Anda tahu bahwa
\[
\begin{array}{lll}
2^{k+1} & = & 2\cdot 2^{k} \\
& < & 2 \cdot k!\\
&<& (k+1)k! \\
&=& (k+1)!
\end{array}
\]
yang menunjukkan bahwa pernyataan $P(k+1)$ adalah benar. Oleh karena itu pembuktian secara induksi matematika untuk sifat $2^{n}<n!$ untuk $n \geq 4$ terbukti. $\blacksquare$.

Contoh Soal 7. Ketaksamaan Bilangan Harmonik
Bilangan harmonik $H_{j}$, $j=1,2,3,\cdots$ didefinisikan dengan$$H_{j}:=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{j}$$Gunakan induksi metmatika untuk membuktikan bahwa$$H_{2^{n}} \geq 1+\frac{n}{2}$$dengan $n$ adalah bilangan bulat tak negatif.

Pembahasan Contoh Soal 7.
Untuk membuktikan dengan induki matematika, dimisalkan terlebih dahulu $P(n)$ adalah pernyataan bahwa $H_{2^{n}} \geq 1+\frac{n}{2}$.
LANGKA DASAR; $P(0)$ benar karena $H_{2^{0}}=H_{1}=1 \geq 1+\frac{0}{2}$.
LANGKAH INDUKTIF; Misalkan $P(k)$ benar, yaitu $H_{2^{k}} \geq 1+\frac{k}{2}$ dengan $k$ sebarang bilangan bulat tak negatif. Akan ditunjukkan bahwa $P(k+1)$ benar, yaitu $$H_{2^{k+1}} \geq 1+\frac{k+1}{2}$$.Berdasarkan definisi bilangan harmonik bisa dilihat bahwa
\[
\begin{array}{lll}
H_{2^{k+1}} & = & 1+\frac{1}{2}+\frac{1}{3}\cdots+\frac{1}{2^{k}}+\frac{1}{2^{k}+1}+\cdots+\frac{1}{2^{k+1}} \\
& = & H_{2^{k}}+\frac{1}{2^{k}+1}+\cdots+\frac{1}{2^{k+1}}\\
&\geq& \left(1+\frac{k}{2}\right)+2^{k}\cdot\frac{1}{2^{k+1}}\\
&\geq& \left(1+\frac{k}{2}\right)+\frac{1}{2}\\
&=& 1 + \frac{k+1}{2}
\end{array}
\]
Jadi pembuktian secara induksi matematika sudah lengkap untuk membuktikan $H_{2^{n}} \geq 1+\frac{n}{2}$ $\blacksquare$

Jangan Lewatkan : Pembahasan Ujian Akhir Analisis Riil

LATIHAN

Untuk nomor 1 - 6 gunakan pembuktian dengan menggunakan induksi matematika.

1. Tunjukkan bahwa$$1^{2}+2^{2}+2^{2}+\cdots+n^{2}=\frac{n(n+1)(2n+1)}{6}$$untuk sebarang bilangan bulat positif $n$!

2. Tunjukkan bahwa$$1^{3}+2^{3}+3^{3}+\cdots+n^{3}=\left(\frac{n(n+1)}{2}\right)^{2}$$untuk sebarang bilangan bulat positif $n$!

3. Tunjukkan bahwa$$1^{2}+3^{2}+5^{2}\cdots+(2n+1)^{2}=\frac{(n+1)(2n+1)(2n+3)}{3}$$untuk sebarang bilangan bulat positif $n$!

4. Tunjukkan bahwa$$1\cdot1!+2\cdot2!+\cdots +n\cdot n!=(n+1)!-1$$untuk sebarang bilangan bulat positif $n$!

5. Tunjukkan bahwa$$1+\frac{1}{4}+\frac{1}{9}+\cdots+\frac{1}{n^{2}}< 2 - \frac{1}{n}$$untuk sebarang bilangan bulat $n > 1$!

6. Tunjukkan bahwa $3^{n}<n!$ untuk sebarang bilangan bulat $n > 6$!

Induksi Matematika Kuat

Metode induksi matematika yang sudah dipelajari menunjukkan banyak kegunaan dalam pembuktian.

Terdapat metode lain dari induksi matematika, yaitu Induksi Matematika Kuat.

Perbedaan dengan induksi matematika terletak pada langkah induktif.

Langkah induktif pada induksi matematika mempunyai ciri \textit{hipotesis induktifnya} berlaku untuk bilangan bulat tidak lebih dari $k$.

PRINSIP INDUKSI MATEMATIKA KUAT
Pembuktian pernyataan $P(n)$ benar untuk semua bilangan bulat $n$ melalui dua tahap
LANGKAH DASAR: Menunjukkan bahwa $P(1)$ benar.
LANGKAH INDUKTIF: Membuktikan bahwa pernyataan \[\left[ P(1)\wedge P(2) \wedge \cdots \wedge P(k)\right] \rightarrow P(k+1) \]adalah benar untuk semua bilangan bulat $k$.

Contoh Soal 8.
Tunjukkan bahwa setiap bilangan bulat $n$ yang lebih dari 1 bisa dinyatakan dalam perkalian bilangan prima.

Pembahasan Cintih Soal 8.

Misalkan $P(n)$ menyatakan bahwa $n$ bisa ditulis dalam perkalian bilangan prima.

LANGKAH DASAR : $P(2)$ benar karena 2 sendiri adalah bilangan prima.

LANGKAH INDUKTIF : Andaikan $P(j)$ benar untuk semua bilangan bulat $2 \leq j \leq k$, yaitu $j$ bisa dituliskan dalam perkalian bilangan bulat ketika $j$ adalah bilangan bulat yang lebih dari 1 namun tidak lebih dari $k$. Akan ditunjukkan $P(k+1)$ benar.

Terdapat dua kasus, $(k+1)$ bilangan prima dan $(k+1)$ bilangan komposit.

Pada kasus, $(k+1)$ prima, maka dapat dilihat bahwa $P(k+1)$ benar.

Pada kasus kedua, ketika $(k+1)$ bilangan komposit. Bilangan bulat dapat dinyatakan perkalian dua bilangan bulat positif $a$ dan $b$ dengan $2 \leq a \leq b <k+1$.

Karena $a$ dan $b$ lebih dari 2 dan tidak lebih dari $k$ maka dapat dinyatakan sebagai perkalian bilangan prima berdasarkan hipotesis induktif.

Jadi jika $k+1$ komposit maka dapat ditulis perkalian bilangan prima, yaitu faktor prima dari $a$ dan $b$. $\blacksquare$

Contoh Soal 9.
Sebuah permainan melibatkan dua pemain bergantian melepas sejumlah bilangan bulat korek api di dua tumpukan korek api. Pemain yang melepaskan korek api terkahir adalah pemenang.
Tunjukkan bahwa jika dua tumpukan memuat jumlah yang sama maka pemain kedua selalu menjadi pemenang!

Pembahasan Contoh Soal 9.
Misalkan $n$ adalah banyak korek api di setiap tumpukan.

$P(n)$ merupakan pernyataan bahwa pemain kedua menang ketika banyak korek api di setiap tumpukan adalah $n$.

LANGKAH DASAR : Ketika $n=1$, Pemain pertama memiliki dua pilihan, sedangkan pemain kedua pilihan tinggal satu korek api di satu tumpukan yang menjadikan pemain kedua pemenang.

LANGKAH INDUKTIF : Andaikan $P(j)$ benar untuk $1 \leq j \leq k$, yaitu pemain kedua menang ketika setiap tumpukan berisi $j$ korek api dengan $1 \leq j \leq k$.
Akan ditunjukkan bahwa $P(k+1)$ benar.

Andaikan terdapat $k+1$ korek api di setiap tumpukan dan pemain pertama melepaskan $r$ kork api $\left(1\leq r \leq k\right)$ dari salah satu tumpukan menyisahkan $k+1 - r$ korek api di tumpukan ini.

Pemain kedua melepaskan korek api dengan cara yang sama di tumpukan yang lain sehingga terdapat $\left(1\leq r \leq k\right)$ di kedua tumpukan.

Karena $\left(1\leq k+1-r \leq k\right)$, maka berdasarkan hipotesis induktif pemain kedua selalu dapat menang.

Jika pemain pertama melepaskan $k+1$ korek api, maka pemain kedua akan menang dengan melepaskan korek api sejumlah $k+1$. $\blacksquare$

Prinsip Induksi Matematika

4/ 5

Oleh Mohammad Mahfuzh Shiddiq

Mohammad Mahfuzh Shiddiq November 15, 2018 Komentar