Soal dan Pembahasan – Induksi Matematika pada Keterbagian Bilangan

Induksi matematika (kadang juga disebut sebagai induksi matematis, atau dalam bahasa Inggris, mathematical induction) pada awalnya adalah salah satu metode pembuktian pernyataan matematika yang melibatkan bilangan asli dan proses pembuktiannya menggunakan dua langkah utama: langkah basis (basis step) dan langkah induktif (inductive step). 

Baca Juga: Soal dan Pembahasan – Notasi Sigma     

Teorema yang berlaku untuk setiap bilangan asli (atau hanya tidak berlaku untuk bilangan asli tertentu) memiliki kemungkinan untuk dapat dibuktikan kebenarannya dengan induksi matematika. Tidak terbatas pada itu, induksi matematika bahkan dapat diperluas untuk pembuktian yang melibatkan bilangan bulat. Namun, perlu diperhatikan bahwa penggunaan induksi matematika sebagai salah satu metode pembuktian tidak secara khusus untuk memproduksi pernyataan baru lainnya, melainkan untuk memverifikasi kebenaran dari suatu dugaan (konjektur) kita. 

Induksi matematika bekerja layaknya efek domino yang memiliki prinsip bahwa ketika satu domino jatuh, domino yang lain juga akan jatuh. Prinsip yang sama dengan efek domino juga terjadi pada mekanisme Rube Goldberg Machine. Ada dua langkah utama dalam proses membuktikan suatu proposisi dengan menggunakan induksi matematika.

Mekanisme Rube Goldberg Machine
Mekanisme Rube Goldberg Machine

Tahap I: Langkah Basis

Tunjukkan bahwa $P(n)$ benar untuk $n = n_0$ dengan $n_0$ adalah bilangan terkecil dari himpunan pembicaraan.

Tahap II: Langkah Induktif

Tunjukkan bahwa untuk sembarang $k,$  jika $P(k) $ benar, maka $P(k+1)$ juga benar. Secara matematis ditulis, $\forall k \, (P(k) \Rightarrow P(k+1)).$ 

Perhatikan bahwa kita dapat memodifikasi prinsip induksi matematika melalui perubahan langkah basis dan langkah induktif seperti beberapa contoh berikut.

$P(n)$ benar untuk semua bilangan genap positif $n.$

Langkah Basis:
Tunjukkan bahwa $P(2)$ benar.

Langkah Induktif:
Untuk sembarang bilangan genap positif $k,$ tunjukkan bahwa jika $P(k)$ benar, maka $P(k + 2)$ benar.

$P(n)$ benar untuk semua bilangan ganjil positif $n.$

Langkah Basis:
Tunjukkan bahwa $P(1)$ benar.

Langkah Induktif:
Untuk sembarang bilangan ganjil positif $k,$ tunjukkan bahwa jika $P(k)$ benar, maka $P(k + 2)$ benar.

$P(n)$ benar untuk $n = -7, -2, 3, 8,$ $13, 18, \cdots$

Langkah Basis:
Tunjukkan bahwa $P(-7)$ benar.

Langkah Induktif:
Untuk $k =  -7, -2, 3, 8, 13, 18, \cdots,$ tunjukkan bahwa jika $P(k)$ benar, maka $P(k + 5)$ benar.

$P(n)$ benar untuk semua bilangan bulat $n.$

Langkah Basis:
Tunjukkan bahwa $P_{0}$ benar  dan tunjukkan bahwa $P(-1)$ benar.

Langkah Induktif:
Untuk sembarang bilangan bulat nonnegatif $k,$ tunjukkan bahwa jika $P(k)$ benar, maka $P(k + 1)$ benar dan untuk setiap bilangan bulat negatif $k,$ tunjukkan bahwa jika $P(k)$ benar, maka $P(k-1)$ benar.

Baca Juga: Soal dan Pembahasan – Barisan dan Deret Aritmetika

Soal-soal berikut merupakan soal tentang induksi matematika yang berhubungan dengan keterbagian bilangan. Soal juga tersedia dalam PDF yang dapat diunduh melalui tautan berikut: Download (PDF, 87 KB)Untuk soal induksi yang berhubungan dengan deret dan ketaksamaan bilangan, silakan kunjungi tautan di bawah.

Baca: Soal dan Pembahasan – Induksi Matematika pada Deret dan Ketaksamaan

Quote by Confucius

Yang saya dengar, saya lupa.
Yang saya dengar dan lihat, saya ingat.
Yang saya dengar, lihat, tanyakan, dan kerjakan saya pahami.

Artikel ini ditulis berdasarkan beberapa sumber, termasuk sumber berbahasa Inggris. Salah satu sumber yang digunakan adalah buku “Discrete Mathematics and Its Applications” yang ditulis oleh Kenneth H. Rosen. Oleh karena itu, untuk meminimalisasi kesalahan penafsiran, padanan untuk beberapa kata/istilah diberikan dalam tabel berikut.

$$\begin{array}{ccc} \hline \text{No.} & \text{Bahasa Indonesia} & \text{Bahasa Inggris} \\ \hline 1. & \text{Induksi Matematika} & \text{Mathematical Induction} \\ 2. & \text{Langkah Basis} & \text{Basis Step} \\ 3. & \text{Langkah Induktif} & \text{Inductive Step} \\ 4. & \text{Barisan} & \text{Sequence} \\ 5. & \text{Deret} & \text{Series} \\ 6. & \text{Bilangan Asli} & \text{Natural Number} \\ 7. & \text{Bilangan Cacah} & \text{Whole Number} \\ 8. & \text{Bilangan Bulat Nonnegatif} & \text{Nonnegative Integer} \\ 9. & \text{Bilangan Bulat Positif} & \text{Positive Integer} \\ 10. & \text{Suku} & \text{Term} \\ 11. & \text{Ketaksamaan} & \text{Inequality} \\ \hline \end{array}$$


Soal Nomor 1

Buktikan $n^3 -n$ habis dibagi $6$ untuk setiap bilangan asli $n.$

Pembahasan

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n): n^3 -n$ habis dibagi $6.$
Langkah Basis:

Untuk $n = 1$, diperoleh
$P(1): 1^3 -1 = 0$ habis dibagi $6$.
Pernyataan $P(1)$ bernilai benar. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ $P(k): k^3 -k$ habis dibagi $6$ merupakan pernyataan yang diasumsikan benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan $P(k+1): (k+1)^3 -(k+1)$ habis dibagi $6$.
Ekspresi pada $P(k+1)$ dapat ditulis menjadi
$$\begin{aligned} (k+1)^3 -(k+1) & = k^3 + 3k^2 + 2k \\ & = (n^3 -n) + (3n^2 + 3n) \\ & = (n^3 -n) + 3n(n+1). \end{aligned}$$Ekspresi terakhir terdiri dari dua suku. Suku pertama adalah $(n^3 – n)$ yang habis dibagi $6$ berdasarkan asumsi sebelumnya. Suku kedua adalah $3n(n+1)$, juga habis dibagi $6$ karena mengandung faktor $3$ dan salah satu di antara $n$ atau $n+1$ merupakan bilangan genap sehingga mengandung faktor $2$. Jadi, $P(k+1)$ benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$
Catatan: Suatu bilangan habis dibagi $6$ jika dan hanya jika bilangan itu habis dibagi $2$ (genap) sekaligus habis dibagi $3$.

[collapse]

Soal Nomor 2

Untuk semua bilangan asli $n \geq 1$, buktikan bahwa $n^3 + 2n$ adalah kelipatan $3$.

Pembahasan

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n): 3~|~n^3 + 2n.$
Langkah Basis:
Untuk $n = 1$, diperoleh $P(1): 3~|~1^3 + 2(1).$
Pernyataan $P(1)$ bernilai benar. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku $P(k): 3~|~k^3+2k.$
Asumsikan pernyataan di atas bernilai benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1): 3~|~(k+1)^3+2(k+1).~~\bigstar$
Perhatikan bahwa
$$\begin{aligned} (k+1)^3+ 2(k+1) & = (k^3+3k^2+3k+1)+(2k+2) \\ & = (k^3+2k) + 3(k^2+k+1). \end{aligned}$$Karena $k^3+2k$ merupakan kelipatan $3$ (berdasarkan asumsi) dan $3(n^2+n+1)$ jelas habis dibagi $3$ (karena mengandung faktor $3$), maka $(k^3+2k) + 3(k^2+k+1)$ juga merupakan kelipatan $3$.
Jadi, $P(k+1)$ benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

[collapse]

Soal Nomor 3

Buktikan bahwa $7^n -2^n$ habis dibagi $5$ untuk setiap $n \in \mathbb{N}$.

Pembahasan

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n): 7^n -2^n$ habis dibagi $5.$
Langkah Basis:
Untuk $n = 1$, diperoleh $P(1): 7^1 -2^1=5$, yang jelas habis dibagi $5.$
Pernyataan $P(1)$ bernilai benar. Langkah basis selesai. 

Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ $P(k): 7^k -2^k$ habis dibagi $5$ diasumsikan merupakan pernyataan yang benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan $P(k+1): 7^{k+1} -2^{k+1}$ habis dibagi $5.$
Bentuk pada $P(k+1)$ di atas dapat ditulis menjadi
$\begin{aligned} & 7^k \cdot 7 -2^k \cdot 2 \\ & = 7^k \cdot 7 -7 \cdot 2^k + 7 \cdot 2^k -2^k \cdot 2 \\ & = 7(7^k -2^k) + 2^k(7-2) \\ & = 7(7^k -2^k) + 2^k(5). \end{aligned}$
Ekspresi terakhir di atas terdiri dari $2$ suku. Suku pertama adalah $7(7^k -2^k)$ habis dibagi $5$ karena faktor $7^k -2^k$ habis dibagi $5$ berdasarkan asumsi sebelumnya. Suku kedua adalah $2^k(5)$ jelas habis dibagi $5$ karena mengandung faktor $5$. Dengan demikian, secara keseluruhan, 7^{k+1} -2^{k+1}$ habis dibagi $5$.
Jadi, $P(k+1)$ benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

[collapse]

Soal Nomor 4

Buktikan bahwa untuk semua bilangan asli $n$, $a^{2n-1} + b^{2n-1}$ habis dibagi oleh $a + b$ dengan menggunakan induksi matematika.

Pembahasan

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n): a^{2n-1} + b^{2n-1}$ habis dibagi oleh $a + b.$
Langkah Basis:
Untuk $n = 1,$ diperoleh $P(1): a + b$ habis dibagi oleh $a +b$ (dirinya sendiri),  jelas merupakan pernyataan yang benar. Pernyataan $P(1)$ bernilai benar. Langkah basis selesai.
Langkah Induktif:

Misalkan untuk sembarang bilangan asli $k,$ berlaku $P(k): a^{2k-1} + b^{2k-1}$ habis dibagi oleh $a + b$. Asumsikan pernyataan ini benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan $P(k+1): a^{2k+1} + b^{2k+1}$ habis dibagi oleh $a + b.$
Perhatikan bahwa
$$\begin{aligned} a^{2k+1} + b^{2k+1} & = a^{2k-1} \cdot a^2 + b^{2k-1} \cdot b^2 \\ & = (a^{2k-1} + b^{2k-1}) (a^2) -b^{2k-1}(a^2-b^2) \\ & = (a^{2k-1} + b^{2k-1}) (a^2) -b^{2k-1}(a+b) (a-b). \end{aligned}$$Ekspresi di atas terdiri dari dua suku. Suku pertama adalah $(a^{2k-1}+b^{2k-1})(a^2)$, habis dibagi oleh $a + b$ karena faktor pertamanya telah diasumsikan habis dibagi oleh $a + b,$ sedangkan suku keduanya, yaitu $-b^{2k-1}(a+b) (a-b)$ jelas habis dibagi $a + b$ karena mengandung faktor tersebut.

Jadi, $P(k+1)$ benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

[collapse]

Soal Nomor 5

Buktikan bahwa $n^3 + 5n$ habis dibagi $6$ untuk setiap bilangan asli $n.$ 

Pembahasan

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n): n^3 + 5n$ habis dibagi $6.$
Langkah Basis:
Untuk$n = 1$, diperoleh
$P(1): 1^3 + 5(1) = 6$ habis dibagi $6$.
Pernyataan $P(1)$ bernilai benar. Langkah basis selesai.

Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k): k^3 + 5k$ habis dibagi $6$.
Asumsikan pernyataan di atas benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1): (k+1)^3 + 5(k+1)$ habis dibagi $6$.
Ekspresi $P(k+1)$ di atas dapat ditulis menjadi$$(k+1)^3 + 5(k+1) = (k^3+ 5k) + 3(k^2 + k + 1)$$jika diuraikan pangkatnya.
Sekarang dua suku pada ekspresi terakhir akan kita tinjau sebagai berikut. Suku pertama yaitu $k^3 + 5k$ habis dibagi $6$ berdasarkan asumsi sebelumnya. Suku kedua yaitu $3(k^2 + k + 1)$ juga habis dibagi $6$ karena ekspresi ini habis dibagi $3$ (mengandung faktor $3$) serta habis dibagi $2$ sebab ($k^2 + k + 1$) merupakan bilangan genap untuk setiap $k \in \mathbb{N}$. Karena kedua sukunya habis dibagi $6$, ekspresi keseluruhan juga habis dibagi $6.$
Jadi, $P(k+1)$ benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

[collapse]

Soal Nomor 6

Buktikan bahwa $x^n -1$ habis dibagi oleh $x -1, x \neq 1$ untuk setiap bilangan asli $n.$

Pembahasan

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n): x^n -1$ habis dibagi oleh $x -1.$
Langkah Basis:
Untuk $n = 1$, diperoleh
$P(1): x -1$ habis dibagi oleh $x -1.$
Pernyataan $P(1)$ bernilai benar. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k): x^k -1$ habis dibagi oleh $x -1.$
Asumsikan $P(k)$ benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1): x^{k+1} -1$ habis dibagi oleh $x -1.$ 
Perhatikan bahwa
$\begin{aligned} x^{k+1} -1 & = x \cdot x^k -1 \\ & = x \cdot x^k -1 + (x -x) \\ & = \underbrace{x(x^k -1)}_{\text{habis dibagi}~(x+1)} + \color{blue}{(x -1)}. \end{aligned}$
Perhatikan ekspresi terakhir. Suku pertama (yang telah diberi keterangan) habis dibagi $x -1$ berdasarkan asumsi bahwa $P(k)$ benar, yaitu $x^k -1$ habis dibagi $x -1$, sedangkan suku kedua (yang diberi warna biru) jelas habis dibagi oleh $x- 1$ (dirinya sendiri). Untuk itu, keduanya habis dibagi oleh $x-1$ sehingga pernyataan $P(k+1)$ terbukti benar.
Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

[collapse]

Soal Nomor 7

Buktikan bahwa salah satu faktor dari $n^3+3n^2+2n$ adalah $3$ untuk setiap bilangan asli $n.$

Pembahasan

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n)$ : Salah satu faktor dari $n^3+3n^2+2n$ adalah $3.$
Langkah Basis:
Untuk $n = 1,$ diperoleh
$P(1)$: Salah satu faktor dari $1^3+3(1)^2+2(1) = 6$ adalah $3$. 
Pernyataan di atas benar (faktor dari $6$ adalah $1, 2, 3$, dan $6$). Dengan kata lain, $P(1)$ bernilai benar. Langkah basis selesai. 
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k)$: Salah satu faktor dari $k^3+3k^2+2k$ adalah $3$. 
Asumsikan $P(k)$ benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1)$: Salah satu faktor dari $(k+1)^3+3(k+1)^2+2(k+1)$ adalah $3.$
Sekarang kita akan mengubah (memanipulasi) bentuk $(k+1)^3+3(k+1)^2+2(k+1)$ sebagai berikut. 
$$\begin{aligned} (k+1)^3+3(k+1)^2 + 2(k+1) & = (k^3+3k^2+3k+1) + (3k^2 + 6k + 3) + (2k+2) \\ & = (k^3 + 3k^2 + 2k + k) + (3k^2 + 8k + 6) \\ & = (k^3 + 3k^2 + 2k) + (3k^2 + 9k + 6) \\ & = \underbrace{(k^3 + 3k^2 + 2k)}_{\text{memiliki faktor 3}} + \color{blue}{3(k^2 + 3k + 2)} \end{aligned}$$Dua suku pada ekspresi terakhir di atas memiliki $3$ sebagai salah satu faktornya. Untuk suku pertama (yang telah diberi keterangan), salah satu faktornya adalah $3$ berdasarkan asumsi bahwa $P(k)$ benar. Untuk suku kedua (yang diberi warna biru), salah satu faktornya juga $3$, jelas karena ditulis dalam bentuk pemfaktoran. 
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

[collapse]

Soal Nomor 8

Buktikan bahwa salah satu faktor dari $2^{2n-1} + 3^{2n-1}$ adalah $5$ untuk setiap bilangan asli $n.$

Pembahasan

Misalkan $n$ merupakan bilangan asli. Definisikan
$P(n)$: Salah satu faktor dari $2^{2n-1} + 3^{2n-1}$ adalah $5.$
Langkah Basis:
Untuk $n = 1,$ diperoleh
$P(1)$: Salah satu faktor dari $2^{2(1)-1} + 3^{2(1)-1} = 2^1 + 3^1 = 5$ adalah $5$. 
Pernyataan di atas benar (faktor dari $5$ adalah $1$ dan $5$). Dengan kata lain, $P(1)$ bernilai benar. Langkah basis selesai. 
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k)$: Salah satu faktor dari $2^{2k-1} + 3^{2k-1}$ adalah $5$. 
Asumsikan $P(k)$ benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1)$: Salah satu faktor dari $2^{2(k+1)-1} + 3^{2(k+1)-1} = 2^{2k+1} + 3^{2k+1}$ adalah $5$. 
Sekarang kita akan mengubah (memanipulasi) bentuk $2^{2k+1}+3^{2k+1}$ sebagai berikut. 
$$\begin{aligned} 2^{2k+1} + 3^{2k+1} & = 2^{2k-1+2} + 3^{2k-1+2} \\ & = 2^{2k-1} \cdot 2^2 + 3^{2k-1} \cdot 3^2 \\ & = 2^{2k-1} \cdot 4 + 3^{2k-1} \cdot 9 \\ & = 2^{2k-1}(5-1) + 3^{2k-1} \cdot (10-1) \\ & = 5 \cdot 2^{2k-1} -2^{2k-1} + 10 \cdot 3^{2k-1} – 3^{2k-1} \\ & = \color{blue}{5(2^{2k-1} + 3^{2k-1})}\underbrace{-(2^{2k-1} + 3^{2k-1})} _{\text{memiliki faktor 5}} \end{aligned}$$Dua suku pada ekspresi terakhir di atas memiliki $5$ sebagai salah satu faktornya. Untuk suku pertama (yang diberi warna biru), salah satu faktornya adalah $5$, jelas karena ditulis dalam bentuk pemfaktoran. Untuk suku kedua (yang telah diberi keterangan), salah satu faktornya juga $5$ berdasarkan asumsi bahwa $P(k)$ benar.
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$
 

[collapse]

Soal Nomor 9

Buktikan bahwa $41^n -14^n$ adalah kelipatan $27$ untuk setiap bilangan asli $n.$

Pembahasan

Misalkan $n$ merupakan bilangan asli. Definisikan
$P(n): 41^n -14^n$ adalah kelipatan $27.$
Langkah Basis:
Untuk $n = 1,$ diperoleh
$P(1): 41^1 -14^1 = 27$ adalah kelipatan $27.$ 
Pernyataan di atas jelas benar. Dengan kata lain, $P(1)$ bernilai benar. Langkah basis selesai. 
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k)$: $41^k -14^k$ adalah kelipatan $27.$
Asumsikan $P(k)$ benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1): 41^{k+1} -14^{k+1}$ adalah kelipatan $27.$ 
Sekarang kita akan mengubah (memanipulasi) bentuk $41^{k+1} -14^{k+1}$ sebagai berikut. 
$\begin{aligned} & 41^{k+1} -14^{k+1} \\ & = 41^k \cdot 41 -14^k \cdot 14 \\ & = 41^k(27+14) -14^k \cdot 14 \\ & = 27 \cdot 41^k + 14 \cdot 41^k -14 \cdot 14^k \\ & = \color{blue}{27 \cdot 41^k} + \underbrace{14(41^k -14^k)}_{\text{berkelipatan 27}} \end{aligned}$
Dua suku pada ekspresi terakhir di atas memiliki berkelipatan $27$. Untuk suku pertama (yang diberi warna biru), memiliki kelipatan $27$, jelas karena ditulis dalam bentuk pemfaktoran. Suku kedua (yang telah diberi keterangan) juga berkelipatan $27$ berdasarkan asumsi bahwa $P(k)$ benar.
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

[collapse]

Soal Nomor 10

Tunjukkan bahwa untuk setiap bilangan asli $n$, $2^{6n} + 3^{2n-2}$ habis dibagi $5.$

Pembahasan

Misalkan $n$ merupakan bilangan asli. Definisikan
$P(n): 2^{6n} + 3^{2n-2}$ habis dibagi $5.$
Langkah Basis:
Untuk $n = 1$, diperoleh
$P(1): 2^{6} + 3^{0} = 65$ habis dibagi $5.$
Pernyataan di atas jelas benar. Dengan kata lain, $P(1)$ bernilai benar. Langkah basis selesai. 
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k)$: $2^{6k} + 3^{2k-2}$ habis dibagi $5.$ 
Asumsikan $P(k)$ benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1)$: $2^{6k+6} + 3^{2k}$ habis dibagi $5.$
Sekarang kita akan mengubah (memanipulasi) bentuk $2^{6k+6} + 3^{2k}$ sebagai berikut. 
$$\begin{aligned} 2^{6k+6} + 3^{2k} & = 2^{6k} \cdot 2^6 + 3^{2k-2} \cdot 3^2 \\ & = 2^{6k} \cdot (55 + 9) + 3^{2k-2} \cdot 9 \\ & = 2^{6k} \cdot 55 + 2^{6k} \cdot 9 + 3^{2k-2} \cdot 9 \\ & = 2^{6k} \cdot \color{blue}{5} \cdot 11 + \underbrace{(2^{6k} + 3^{2k-2})}_{\text{habis dibagi 5}} \cdot 9 \end{aligned}$$Perhatikan bahwa suku pertama pada ekspresi terakhir habis dibagi $5$ karena memuat faktor $5,$ sedangkan suku kedua habis dibagi $5$ karena asumsi kita pada langkah induktif bahwa $P(k)$ benar. Dengan demikian, penjumlahan dua suku tersebut juga habis dibagi $5.$
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

[collapse]

Soal Nomor 11

Buktikan bahwa $4.007^n -1$ habis dibagi $2.003$ untuk setiap bilangan asli $n.$

Pembahasan

Misalkan $n$ merupakan bilangan asli. Definisikan
$P(n): 4.007^n -1$ habis dibagi $2.003.$
Langkah Basis:
Untuk $n = 1,$ diperoleh
$P(1)$: $4.007^1-1 = 4.006$ habis dibagi $2.003.$ 
Jadi, $P(1)$ bernilai benar. Langkah basis selesai. 
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k): 4.007^k -1$ habis dibagi $2.003.$
Asumsikan $P(k)$ benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1): 4.007^{k+1} -1$ habis dibagi $2003.$
Sekarang kita akan mengubah (memanipulasi) bentuk $4.007^{k+1}-1$ sebagai berikut. 
$$\begin{aligned} 4.007^{k+1}-1 & = 4.007^k \cdot 4.007 -1 \\ & = 4.007^k \cdot (2.003+2.004) -(2.004-2.003) \\ & = 2.003 \cdot 4.007^k + 2.004 \cdot 4.700^k – 2.004 + 2.003 \\ & = \underbrace{2.004(4.700^k -1)}_{\text{berkelipatan 2.003}} + \color{blue} {2.003(4.007^k + 1)} \end{aligned}$$Dua suku pada ekspresi terakhir di atas berkelipatan $2.003.$ Untuk suku pertama (yang telah diberi keterangan), memiliki kelipatan $2.003$ berdasarkan asumsi bahwa $P(k)$ benar. Untuk suku kedua (yang diberi warna biru), salah satu faktornya adalah $2.003$ sehingga jelas merupakan kelipatan $2003$. 
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

[collapse]

Soal Nomor 12

Buktikan dengan induksi matematika bahwa $2^{4n-1}$ habis dibagi $8$ untuk setiap bilangan asli $n.$

Pembahasan

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n): 2^{4n-1}$ habis dibagi $8.$
Langkah Basis:
Untuk $n = 1$, diperoleh
$P(1): 2^{4(1)-1} = 8$ habis dibagi $8$. Pernyataan ini benar. Untuk itu, $P(n)$ bernilai benar untuk $n = 1$. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k): 2^{4k-1}$ habis dibagi $8$.
Asumsikan pernyataan ini benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1): 2^{4(k+1)-1} = 2^{4k+3}$ habis dibagi $8$.
Perhatikan bahwa 
$\begin{aligned} 2^{4k + 3} & = 2^{4k -1 + 4} \\ & = 2^{4k -1} \times 2^{4} \\ & = 2^{4k -1} \times 16. \end{aligned}$
Karena $2^{4k-1}$ maupun $16$ habis dibagi $8$, $2^{4k+3}$ juga demikian.
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$

[collapse]

Soal Nomor 13

Buktikan dengan induksi matematika bahwa $5^{2x}+3x-1$ habis dibagi $9$ untuk setiap bilangan asli $x.$

Pembahasan

Misalkan $x$ merupakan bilangan asli. Definisikan $P(x): 5^{2x}+3x-1$ habis dibagi $9.$
Langkah Basis:
Untuk $x = 1$, diperoleh
$P(1): 5^2+3(1)-1 = 27$ habis dibagi $9.$ Pernyataan ini benar. Untuk itu, $P(x)$ bernilai benar untuk $x = 1$. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$P(k): 5^{2k}+3k-1$ habis dibagi $9$.
Asumsikan pernyataan ini benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$P(k+1): 5^{2(k+1)}+3(k+1)-1$ habis dibagi $9$.
Perhatikan bahwa 
$$\begin{aligned} 5^{2(k+1)}+3(k+1)-1 & = 5^{2k + 2} + 3k + 3-1 \\ & = \color{red}{25 \cdot 5^{2k}} + \color{blue}{3k} + \color{green}{2} \\ & = \color{red}{(18 \cdot 5^{2k} + 7 \cdot 5^{2k})} + \color{blue}{(21k-18k)} + \color{green}{(-7+9)} \\ & = (7 \cdot 5^{2k} + 21k-7) + (18 \cdot 5^{2k}-18k + 9) \\ & = 7\underbrace{(5^{2k} + 3k-1)}_{\text{habis dibagi}~9} + \underbrace{9(2 \cdot 5^{2k}-2k + 1)}_{\text{habis dibagi}~9}. \end{aligned}$$Karena suku pertama habis dibagi $9$ berdasarkan asumsi $P(k)$ benar dan suku kedua habis dibagi $9$ karena memuat faktor $9$, maka $7(5^{2k} + 3k-1) + 9(2 \cdot 5^{2k}-2k + 1)$ habis dibagi $9$ sehingga $P(k+1)$ terbukti benar.
Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(x)$ benar untuk setiap $x \in \mathbb{N}.$ $\blacksquare$  

[collapse]

Soal Nomor 14

Periksa apakah $2.002^{n+2} + 2.003^{2n+1}$ habis dibagi $4.005$ untuk setiap bilangan asli $n.$

Pembahasan

Misalkan $n$ merupakan bilangan asli. Definisikan
$P(n): 2.002^{n+2} + 2.003^{2n+1}$ habis dibagi $4.005.$
Langkah Basis:
Untuk $n = 1$, diperoleh
$P(1): 2.002^3 + 2.003^3 = 16.060.078.035$ habis dibagi $4.005.$
Pernyataan di atas benar. Terkadang dalam membuktikan suatu pernyataan/rumus baru, kita perlu melakukan langkah basis untuk “beberapa” nilai $n$ pertama karena mungkin saja untuk $n$ tertentu, pernyataan yang diduga benar ternyata salah. Sekarang coba ambil $n = 2.$ 
$P_2: 2.002^3 + 2.003^5$ habis dibagi $4.005.$
Pernyataan di atas salah. Cara memeriksanya dengan cepat alias tanpa menghitung adalah mengamati nilai satuannya: $2^3 + 3^5 \Rightarrow 8 + 3 \rightarrow 1$, sedangkan $4.005$ memiliki satuan $5$, artinya bilangan yang dibagi harus memiliki satuan $5$). Jadi, langkah basis berakhir. Langkah induktif tidak dapat dilakukan dan kita simpulkan bahwa konjektur di atas bernilai salah. 
Catatan: Tidak semua proposisi terbukti benar dengan melakukan induksi. Bedakan istilah proposisi dan konjektur sebagai berikut. Suatu pernyataan yang kebenarannya masih diragukan disebut konjektur. Jika pernyataan itu terbukti benar ATAU salah, maka pernyataan itu disebut proposisi
Soal ini meminta kita untuk “memeriksa” (menyelidiki) sehingga langkah basis dapat dilakukan sampai beberapa nilai $n$ pertama (tujuannya untuk memastikan saja). Lagipula, jika soal ini diteruskan sampai langkah induktif, kita tidak dapat menemukan kesimpulan yang semestinya. Lebih lanjut, apabila soal berbunyi “buktikan/tunjukkan…. “, tetapi langkah basis berakhir setelah ditemukan pernyataan yang salah untuk $n$ tertentu, maka soal itu diasumsikan tidak valid.

[collapse]

Soal Induksi Matematika Tipe Lain

Soal Nomor 1

Buktikan dengan induksi matematika bahwa banyaknya himpunan bagian dari himpunan dengan $n$ anggota adalah $2^n$ untuk setiap bilangan bulat $n \ge 0.$

Pembahasan

Ide utamanya adalah ketika kita memiliki satu anggota tambahan, katakanlah $x$, pada sembarang himpunan dengan $n$ anggota, banyaknya himpunan bagian menjadi dua kali dari semula, yaitu himpunan bagian dari himpunan semula (tanpa memuat $x$) ditambah dengan himpunan bagian dari himpunan semula yang memuat $x.$
Dengan berlandaskan pada ide ini, kita akan membuktikan secara formal dengan menggunakan induksi matematika.
Misalkan $n$ merupakan bilangan bulat $n \ge 0.$ Misalkan juga
$P(n)$ menyatakan banyaknya himpunan bagian dari himpunan dengan $n$ anggota adalah $2^n.$
Langkah Basis:
$P(0)$ benar karena himpunan kosong memiliki $2^0 = 1$ himpunan bagian, yaitu dirinya sendiri. Langkah basis selesai.
Langkah Induktif:
Misalkan $P(k)$ menyatakan banyaknya himpunan bagian dari himpunan dengan $k$ anggota adalah $2^k$ untuk sembarang bilangan bulat $k \ge 0.$ Akan ditunjukkan bahwa $P(k+1)$ benar, artinya banyaknya himpunan bagian dari himpunan dengan $(k+1)$ anggota adalah $2^{k+1}.$
Misalkan terdapat sembarang himpunan $A$ dengan $(k+1)$ anggota dan terdapat $a_1 \in A.$ Notasi $\mathcal{S}(A)$ menyatakan himpunan kuasa (power set) dari $A.$
Karena himpunan bagian dari $A$ yang tidak memuat $a_1$ ada sebanyak $2^k$ (hipotesis induksi) dan himpunan bagian dari $A$ yang memuat $a_1$ juga sebanyak $2^k$, yaitu dengan menggabungkan $\{a_1\}$ pada masing-masing himpunan bagian semula, kita peroleh

$$|\mathcal{S}(A)| = 2^k + 2^k = 2^{k+1}.$$Jadi, $P(k+1)$ terbukti benar. Karena $P(0)$ benar dan untuk sembarang bilangan bulat $k \ge 0,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan bulat $n \ge 0.$ $\blacksquare$

[collapse]

Soal Nomor 2

Buktikan bahwa untuk setiap bilangan asli $n > 1,$ bilangan $2^n$ selalu dapat dituliskan sebagai penjumlahan dua bilangan ganjil berurutan.

Pembahasan

Untuk suatu bilangan asli $n > 1,$ misalkan $P(n)$ menyatakan bilangan $2^n$ dapat dituliskan sebagai penjumlahan dua bilangan ganjil berurutan.
Langkah Basis:
Untuk $n = 2,$ $P(2)$ benar karena $2^2 = 1 + 3$ sehingga $2^2$ dapat ditulis sebagai penjumlahan dua bilangan ganjil berurutan.
Langkah Induktif:
Ambil sembarang bilangan asli $k > 1.$ Asumsikan $P(k)$ benar, yaitu bilangan $2^k$ dapat dituliskan sebagai penjumlahan dua bilangan ganjil berurutan. Akan ditunjukkan bahwa $P(k+1)$ benar, yaitu bilangan $2^{k+1}$ dapat dituliskan sebagai penjumlahan dua bilangan ganjil berurutan.
Karena $P(k)$ benar, kita dapat tuliskan $2^k = m + (m+2) = 2m + 2$ untuk suatu bilangan ganjil $m.$ Perhatikan bahwa
$$\begin{aligned} 2^{k+1} & = 2^k \cdot 2 \\ & = (2m + 2) \cdot 2 && (\text{Hipotesis induksi}) \\ & = (2m + 2) + (2m + 2)  \\ & = (2m + 1) + (2m + 3). \end{aligned}$$Karena $2m$ genap, maka $(2m+1)$ dan $(2m+3)$ merupakan bilangan ganjil, dan berurutan.
Jadi, $P(k+1)$ terbukti benar. Karena $P(2)$ benar dan untuk sembarang bilangan asli $k > 1,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan asli $n > 1.$ $\blacksquare$ 

[collapse]

Soal Nomor 3

Buktikan bahwa untuk setiap bilangan asli $n$, bilangan $3^n$ selalu dapat dituliskan sebagai penjumlahan tiga bilangan bulat berurutan.

Pembahasan

Untuk suatu bilangan asli $n,$ misalkan $P(n)$ menyatakan bilangan $3^n$ dapat dituliskan sebagai penjumlahan tiga bilangan bulat berurutan.
Langkah Basis:
Untuk $n = 1,$ $P(1)$ benar karena $3^1 = 3 = 0 + 1 + 2$ sehingga $3^1$ dapat ditulis sebagai penjumlahan tiga bilangan bulat berurutan.
Langkah Induktif:
Ambil sembarang bilangan asli $k.$ Asumsikan $P(k)$ benar, yaitu bilangan $3^k$ dapat dituliskan sebagai penjumlahan tiga bilangan bulat berurutan. Akan ditunjukkan bahwa $P(k+1)$ benar, yaitu bilangan $3^{k+1}$ dapat dituliskan sebagai penjumlahan tiga bilangan bulat berurutan.
Karena $P(k)$ benar, kita dapat tuliskan $3^k = (m-1) + m + (m+1) = 3m$ untuk suatu bilangan bulat $m.$ Perhatikan bahwa
$$\begin{aligned} 3^{k + 1} & = 3^k \cdot 3 \\ & = (3m) \cdot 3 && (\text{Hipotesis induksi}) \\ & = 3m + 3m + 3m \\ & = (3m-1) + 3m + (3m+1). \end{aligned}$$Karena $m$ bulat, $3m$ juga bulat.
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap $n \in \mathbb{N}.$ $\blacksquare$
 

[collapse]

Soal Nomor 4

Buktikan bahwa papan berpetak dengan ukuran $6 \times 2^n$ untuk setiap bilangan bulat positif $n$ dapat ditutupi oleh ubin tiga petak berbentuk huruf L.

Pembahasan

Misalkan $n$ merupakan bilangan asli. Misalkan juga $P(n)$ menyatakan papan berpetak dengan ukuran $6 \times 2^n$ dapat ditutupi oleh ubin tiga petak berbentuk huruf L.
Langkah Basis:
$P(1)$ benar karena papan berpetak dengan ukuran $6 \times 2$ dapat ditutupi oleh ubin tiga petak berbentuk huruf L seperti yang tampak pada gambar berikut.
Langkah Induktif:

Misalkan $P(k)$ benar untuk sembarang $k \in \mathbb{N}.$ Akan ditunjukkan bahwa $P(k+1)$ benar, artinya papan berpetak dengan ukuran $6 \times 2^{k+1}$ dapat ditutupi oleh ubin tiga petak berbentuk huruf L untuk $k \in \mathbb{N}.$
Perhatikan bahwa papan berpetak dengan ukuran $6 \times 2^{k+1}$ dapat dipandang sebagai gabungan dua papan berukuran $6 \times 2^k.$ Berdasarkan hipotesis induksi, papan berukuran $6 \times 2^k$ dapat ditutupi oleh ubin tiga petak berbentuk huruf L.
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan bulat positif $n.$ $\blacksquare$ 
 

[collapse]

Soal Nomor 5

Misalkan $n$ adalah suatu bilangan bulat positif. Tunjukkan bahwa setiap papan berpetak dengan ukuran $2^n \times 2^n$ yang satu petak sembarangnya dihilangkan dapat selalu ditutupi oleh potongan tiga petak berbentuk huruf L.

Pembahasan

Misalkan $n$ merupakan bilangan asli. Misalkan juga $P(n)$ menyatakan setiap papan berpetak dengan ukuran $2^n \times 2^n$ yang satu petak sembarangnya dihilangkan dapat selalu ditutupi oleh potongan tiga petak berbentuk huruf L.
Langkah Basis:
$P(1)$ benar seperti yang ditunjukkan pada gambar berikut. Petak putih merepresentasikan petak yang dihilangkan.
Langkah Induktif:
Misalkan $P(k)$ menyatakan setiap papan berpetak dengan ukuran $2^k \times 2^k$ yang satu petak sembarangnya dihilangkan dapat selalu ditutupi oleh potongan tiga petak berbentuk huruf L untuk sembarang $k \in \mathbb{N}.$ Asumsikan $P(k)$ benar. Akan ditunjukkan bahwa $P(k+1)$ benar, artinya papan berpetak dengan ukuran $2^{k+1} \times 2^{k+1}$ dapat diperlakukan serupa.
Perhatikan bahwa $2^{k+1} \times 2^{k+1}$ dapat ditulis sebagai $4 \times (2^k \times 2^k).$ Dengan kata lain, papan tersebut dapat dibagi menjadi $4$ papan yang lebih kecil dengan ukuran $2^k \times 2^k.$ Satu petak yang hilang pasti terletak pada salah satu papan kecil itu. Jadi, kita bisa meletakkan potongan tiga petak berbentuk huruf L sedemikian sehingga satu petak masing-masing termuat pada tiga papan kecil lain yang tidak dihilangkan petaknya. Perhatikan gambar ilustrasi berikut agar lebih jelas.
Akibatnya, $4$ papan berukuran $2^k \times 2^k$ memiliki satu petak yang dihilangkan. Berdasarkan hipotesis induksi, kita bisa menutupi setiap papan seperti itu dengan potongan tiga petak berbentuk huruf L.
Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan bulat positif $n.$ $\blacksquare$ 

[collapse]

Soal Nomor 6

Sejumlah ganjil orang berdiri di suatu lapangan dengan jarak antar dua orang berbeda. Pada waktu yang bersamaan, setiap orang melempar kue pada orang yang terdekat dengan mereka dan pasti mengenai orang tersebut. Gunakan induksi matematika untuk membuktikan bahwa ada paling sedikit satu orang yang tidak terkena lemparan kue.
Catatan: Hal ini tidak berlaku jika terdapat sejumlah genap orang.

Pembahasan

Misalkan $n$ merupakan bilangan cacah. Misalkan juga $P(n)$ menyatakan ada setidaknya satu orang yang tidak terlempar kue ketika terdapat $m = 2n + 1$ orang.
Langkah Basis:
$P(0)$ benar karena hanya ada $m = 2(0) + 1 = 1$ orang sehingga tidak ada lemparan kue yang terjadi. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$  $P(k)$ benar. Akan ditunjukkan bahwa $P(k+1)$ benar, artinya ada setidaknya satu orang yang tidak terlempar kue ketika terdapat $m = 2(k+1) + 1 = 2k + 3$ orang untuk bilangan cacah $k.$
Misalkan $d(X, Y)$ menyatakan jarak dua orang, $X$ dan $Y.$ Dari $2k+3$ orang, cari dua orang yang memiliki jarak terdekat, katakanlah $A$ dan $B$ sehingga $d(A, B) < d(X, Y)$ untuk sembarang orang $X$ dan $Y$ dengan $(A, B) \neq (X, Y).$ $A$ dan $B$ tentu akan saling melempar kue. Pandang orang tersisa selain $A$ dan $B$, yaitu sebanyak $2k+1$ orang. Berdasarkan hipotesis induksi bahwa $P(k)$ benar, ada setidaknya satu orang dari $2k+1$ orang tersebut yang tidak terlempar kue.
Jadi, $P(k+1)$ terbukti benar. Karena $P(0)$ benar dan untuk sembarang bilangan cacah $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan cacah $n.$ $\blacksquare$ 

[collapse]

Soal Nomor 7

Buktikan bahwa jika $a > -1$, maka $(1 + a)^n \ge 1 + an$ untuk setiap bilangan asli $n.$
Catatan: Ketaksamaan tersebut dikenal sebagai ketaksamaan Bernoulli (Bernoulli’s inequality).

Pembahasan

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n) : (1 + a)^n \ge 1 + an.$
Langkah Basis:
$P(1)$ benar karena jelas bahwa $(1 + a)^1 \ge 1 + a(1).$ Langkah basis selesai.
Langkah Induktif:
Misalkan $P(k)$ menyatakan $(1 + a)^k \ge 1 + ak$ untuk sembarang bilangan asli $k.$ Asumsikan $P(k)$ benar. Akan dibuktikan bahwa $P(k+1)$ benar yang menyatakan bahwa $(1 + a)^{k+1} \ge 1 + a(k+1)$ untuk setiap bilangan asli $k.$
Perhatikan bahwa
$$\begin{aligned} (1 + a)^{k+1} & = (1+a)^k \cdot (1+a) \\ & \ge (1+ak)(1+a) && (\text{Hipotesis induksi}) \\ & = 1 + a + ak + a^2k \\ & = 1 + a(k+1) + a^2k \\ & \ge 1 + a(k+1). && (a^2k \ge 0) \\ \end{aligned}$$Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan bulat positif $n.$ $\blacksquare$

[collapse]

Soal Nomor 8

Diketahui bahwa $A = \begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix}.$ Buktikan dengan induksi matematika bahwa $A^n = \begin{pmatrix} a^n & 0 \\ 0 & b^n \end{pmatrix}$ untuk setiap bilangan asli $n.$

Pembahasan

Misalkan $n$ merupakan bilangan asli. Definisikan $P(n) : A^n = \begin{pmatrix} a^n & 0 \\ 0 & b^n \end{pmatrix}.$
Langkah Basis:

Untuk $n = 1,$ diperoleh
$$P(1): A^1 = \begin{pmatrix} a^1 & 0 \\ 0 & b^1 \end{pmatrix} = \begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix}.$$Pernyataan ini jelas benar. Untuk itu, $P(n)$ bernilai benar untuk $n = 1$. Langkah basis selesai.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ berlaku
$$P(k): A^k = \begin{pmatrix} a^k & 0 \\ 0 & b^k \end{pmatrix}.$$Asumsikan pernyataan ini benar. Akan ditunjukkan bahwa $P(k+1)$ juga benar dengan
$$P(k+1): A^{k+1} = \begin{pmatrix} a^{k+1} & 0 \\ 0 & b^{k+1} \end{pmatrix}.$$Perhatikan bahwa menurut aturan perpangkatan dan perkalian matriks, kita peroleh
$$\begin{aligned} A^{k+1} & = A^k \cdot A \\ & = \begin{pmatrix} a^k & 0 \\ 0 & b^k \end{pmatrix} \begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix} \\ & = \begin{pmatrix} a^k \cdot a + 0 \cdot 0 & a^k \cdot 0 + 0 \cdot b \\ 0 \cdot a + b^k \cdot 0 & 0 \cdot 0 + b^k \cdot b \end{pmatrix} \\ & = \begin{pmatrix} a^{k+1} & 0 \\ 0 & b^{k+1} \end{pmatrix}. \end{aligned}$$Jadi, pernyataan $P(k+1)$ terbukti benar. Ini berarti kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1)$. Berdasarkan prinsip induksi matematika, $P(n)$ benar untuk setiap $n \in \mathbb{N}$. $\blacksquare$

[collapse]

Soal Nomor 9

Diketahui suatu barisan yang didefinisikan secara rekursif sebagai berikut.
$$S_{m,~n} = \begin{cases} 0 & \text{jika}~m = 0~\text{dan}~n = 0 \\ S_{m-1,~n} + 1& \text{jika}~n = 0 \\ S_{m,~n-1} + 1 & \text{jika}~n \neq 0 \end{cases}$$untuk setiap $(m, n) \in \mathbb{N_0} \times \mathbb{N_0}.$ Notasi $\mathbb{N_0}$ menyatakan himpunan bilangan cacah $\{0, 1, 2, 3, \cdots\}.$ Buktikan bahwa barisan di atas dapat dinyatakan secara eksplisit sebagai $S_{m,~n} = m + n.$
(Sumber: Munir, 2016)

Pembahasan

Perhatikan bahwa kita dapat mendefinisikan urutan pada $\mathbb{N_0} \times \mathbb{N_0}$ dengan mengatakan bahwa $(x_1, y_1) < (x_2, y_2)$ jika $x_1 < x_2$ atau ($x_1 = x_2$ dan $y_1 < y_2$) yang selanjutnya sebagai pengurutan leksikografik (lexicographic ordering).


Kita bisa membuktikan $S_{m,~n} = m + n$ dengan menggunakan induksi matematika yang dirampatkan (generalized mathematical induction). Langkah basisnya adalah menunjukkan bahwa rumus yang diberikan berlaku untuk $(m, n) = (0, 0).$ Langkah induktifnya adalah menunjukkan bahwa jika rumus itu berlaku untuk setiap pasangan yang lebih kecil dari $(m, n)$ menurut pengurutan leksikografik dari $\mathbb{N_0} \times \mathbb{N_0},$ maka rumus itu juga berlaku untuk $(m, n).$
Langkah Basis:
Misalkan $(m, n) = (0, 0).$ Nilai awal barisan yang didefinisikan secara rekursif tersebut adalah $S_{0, 0} = 0.$ Lebih lanjut, dari rumus yang diberikan, kita peroleh
$$S_{m, ~n} = m + n \rightarrow S_{0, 0} = 0 + 0 = 0.$$Langkah basis selesai.
Langkah Induktif:
Misalkan $S_{m^\prime,~n^\prime} = m^\prime + n^\prime$ berlaku kapan pun selama $(m^\prime, n^\prime) < (m, n)$ menurut pengurutan leksikografik dari $\mathbb{N_0} \times \mathbb{N_0}.$


Kasus 1: $n = 0$
Jika $n = 0,$ barisan didefinisikan secara rekursif sebagai $$S_{m,~n} = {\color{red}{S_{m-1,~n}}} + 1.~\color{blue}{\bigstar}$$ Karena $(m-1, n) < (m, n)$, hipotesis induksi memberlakukan rumus itu ketika $(m-1, n)$, yaitu $S_{m-1,~n} = (m-1) + n.$ Dari $\color{blue}{\bigstar}$, kita peroleh
$$\begin{aligned} S_{m, ~n} & = {\color{red}{(m-1)} + n} + 1 \\ & = m + n. \end{aligned}$$Jadi, rumus itu juga terbukti berlaku untuk $(m, n).$


Kasus 2: $n \neq 0$
Jika $n \neq 0,$ barisan didefinisikan secara rekursif sebagai $$S_{m,~n} = \color{red}{S_{m,~n-1}} + 1.~\color{purple}{\bigstar}$$ Karena $(m, n-1) < (m, n)$, hipotesis induksi memberlakukan rumus itu ketika $(m, n-1)$, yaitu $S_{m,~n-1} = m + (n-1).$ Dari $\color{purple}{\bigstar}$, kita peroleh
$$\begin{aligned} S_{m, ~n} & = \color{red}{m + (n-1)} + 1 \\ & = m + n. \end{aligned}$$Jadi, rumus itu juga terbukti berlaku untuk $(m, n).$
Langkah induktif selesai.


Berdasarkan prinsip induksi matematika, terbukti bahwa barisan tersebut dapat dinyatakan secara eksplisit sebagai $S_{m, ~n} = m + n.$ $\blacksquare$

[collapse]

Soal Nomor 10

Tinjau runtunan nilai yang didefinisikan sebagai $S_{1, 1} = 5.$
Untuk semua pasangan bilangan bulat positif $(m, n),$ kecuali $(1, 1),$ didefinisikan
$$S_{m,~n} = \begin{cases} S_{m-1,~n} + 2& \text{jika}~n = 1 \\ S_{m,~n-1} + 2 & \text{jika}~n \neq 1 \end{cases}$$Buktikan bahwa barisan di atas dapat dinyatakan secara eksplisit sebagai $S_{m,~n} = 2(m+n)+1.$
(Sumber: Munir, 2016)

Pembahasan

Perhatikan bahwa kita dapat mendefinisikan urutan pada $\mathbb{N} \times \mathbb{N}$ dengan mengatakan bahwa $(x_1, y_1) < (x_2, y_2)$ jika $x_1 < x_2$ atau ($x_1 = x_2$ dan $y_1 < y_2$) yang selanjutnya sebagai pengurutan leksikografik (lexicographic ordering).

Kita bisa membuktikan $S_{m,~n} = 2(m+n)+1$ dengan menggunakan induksi matematika yang dirampatkan (generalized mathematical induction). Langkah basisnya adalah menunjukkan bahwa rumus yang diberikan berlaku untuk $(m, n) = (1, 1).$ Langkah induktifnya adalah menunjukkan bahwa jika rumus itu berlaku untuk setiap pasangan yang lebih kecil dari $(m, n)$ menurut pengurutan leksikografik dari $\mathbb{N} \times \mathbb{N},$ maka rumus itu juga berlaku untuk $(m, n).$
Langkah Basis:
Misalkan $(m, n) = (1, 1).$ Nilai awal barisan yang didefinisikan secara rekursif tersebut adalah $S_{1, 1} = 5.$ Lebih lanjut, dari rumus yang diberikan, kita peroleh
$$S_{m,~ n} = 2(m+n)+1 \rightarrow S_{1, 1} = 2(1+1)+1=5.$$Langkah basis selesai.
Langkah Induktif:
Misalkan $S_{m^\prime,~n^\prime} = 2(m^\prime + n^\prime) + 1$ berlaku kapan pun selama $(m^\prime, n^\prime) < (m, n)$ menurut pengurutan leksikografik dari $\mathbb{N} \times \mathbb{N}.$


Kasus 1: $n = 1$
Jika $n = 1,$ barisan didefinisikan secara rekursif sebagai $$S_{m,~n} = {\color{red}{S_{m-1,~n}}} + 2.~\color{blue}{\bigstar}$$ Karena $(m-1, n) < (m, n)$, hipotesis induksi memberlakukan rumus itu ketika $(m-1, n)$, yaitu $S_{m-1,~n} = 2((m-1)+n)+1.$ Dari $\color{blue}{\bigstar}$, kita peroleh
$$\begin{aligned} S_{m, ~n} & = \color{red}{(2((m-1)+n)+1)} + 2  \\ & = 2(m+n) + 1. \end{aligned}$$Jadi, rumus itu juga terbukti berlaku untuk $(m, n).$


Kasus 2: $n \neq 1$
Jika $n \neq 1,$ barisan didefinisikan secara rekursif sebagai $$S_{m,~n} = \color{red}{S_{m,~n-1}} + 2.~\color{purple}{\bigstar}$$ Karena $(m, n-1) < (m, n)$, hipotesis induksi memberlakukan rumus itu ketika $(m, n-1)$, yaitu $S_{m,~n-1} = 2(m+(n-1))+1.$ Dari $\color{purple}{\bigstar}$, kita peroleh
$$\begin{aligned} S_{m, ~n} & = \color{red}{(2(m+(n-1))+1)} + 2 \\ & = 2(m+n)+1. \end{aligned}$$Jadi, rumus itu juga terbukti berlaku untuk $(m, n).$
Langkah induktif selesai.


Berdasarkan prinsip induksi matematika, terbukti bahwa barisan tersebut dapat dinyatakan secara eksplisit sebagai $S_{m, ~n} = 2(m+n)+1.$ $\blacksquare$

[collapse]

Soal Nomor 11

Diketahui suatu barisan yang didefinisikan secara rekursif sebagai berikut.
$$a_{0, 0} = 0$$ $$a_{m, n} = \begin{cases} a_{m-1,~n} + 1 & \text{jika}~n = 0~\text{dan}~m > 0 \\ a_{m,~n-1} + n & \text{jika}~n > 0 \end{cases}$$untuk setiap $(m, n) \in \mathbb{N_0} \times \mathbb{N_0}.$ Notasi $\mathbb{N_0}$ menyatakan himpunan bilangan cacah $\{0, 1, 2, 3, \cdots\}.$
Buktikan bahwa barisan di atas dapat dinyatakan secara eksplisit sebagai $a_{m, ~n} = m + \dfrac{n(n+1)}{2}.$
(Sumber: Rosen, 2012)

Pembahasan

Perhatikan bahwa kita dapat mendefinisikan urutan pada $\mathbb{N_0} \times \mathbb{N_0}$ dengan mengatakan bahwa $(x_1, y_1) < (x_2, y_2)$ jika $x_1 < x_2$ atau ($x_1 = x_2$ dan $y_1 < y_2$) yang selanjutnya sebagai pengurutan leksikografik (lexicographic ordering).


Kita bisa membuktikan $a_{m, n} = m + \dfrac{n(n+1)}{2}$ dengan menggunakan induksi matematika yang dirampatkan (generalized mathematical induction). Langkah basisnya adalah menunjukkan bahwa rumus yang diberikan berlaku untuk $(m, n) = (0, 0).$ Langkah induktifnya adalah menunjukkan bahwa jika rumus itu berlaku untuk setiap pasangan yang lebih kecil dari $(m, n)$ menurut pengurutan leksikografik dari $\mathbb{N_0} \times \mathbb{N_0},$ maka rumus itu juga berlaku untuk $(m, n).$
Langkah Basis:
Misalkan $(m, n) = (0, 0).$ Nilai awal barisan yang didefinisikan secara rekursif tersebut adalah $a_{0, 0} = 0.$ Lebih lanjut, dari rumus yang diberikan, kita peroleh
$$a_{m, ~n} = m + \dfrac{n(n+1)}{2} \rightarrow a_{0, 0} = 0 + \dfrac{0(0+1)}{2} = 0.$$Langkah basis selesai.
Langkah Induktif:
Misalkan $a_{m^\prime,~n^\prime} = m^\prime + \dfrac{n^\prime(n^\prime+1)}{2}$ berlaku kapan pun selama $(m^\prime, n^\prime) < (m, n)$ menurut pengurutan leksikografik dari $\mathbb{N_0} \times \mathbb{N_0}.$


Kasus 1: $n = 0$
Jika $n = 0,$ barisan didefinisikan secara rekursif sebagai $$a_{m,~n} = \color{red}{a_{m-1,~n}} + 1.~\color{blue}{\bigstar}$$ Karena $(m-1, n) < (m, n)$, hipotesis induksi memberlakukan rumus itu ketika $(m-1, n)$, yaitu $a_{m-1,~n} = (m-1) + \dfrac{n(n+1)}{2}.$ Dari $\color{blue}{\bigstar}$, kita peroleh
$$\begin{aligned} a_{m, ~n} & = \color{red}{(m-1) + \dfrac{n(n+1)}{2}} + 1 \\ & = m + \dfrac{n(n+1)}{2}. \end{aligned}$$Jadi, rumus itu juga terbukti berlaku untuk $(m, n).$


Kasus 2: $n > 0$
Jika $n > 0,$ barisan didefinisikan secara rekursif sebagai $$a_{m,~n} = \color{red}{a_{m,~n-1}} + n.~\color{purple}{\bigstar}$$ Karena $(m, n-1) < (m, n)$, hipotesis induksi memberlakukan rumus itu ketika $(m, n-1)$, yaitu $a_{m,~n-1} = m + \dfrac{(n-1)(n)}{2}.$ Dari $\color{purple}{\bigstar}$, kita peroleh
$$\begin{aligned} a_{m, ~n} & = \color{red}{m + \dfrac{(n-1)(n)}{2}} + n \\ & = m + \dfrac{(n-1)(n) + 2n}{2} \\ & = m + \dfrac{(n(n+1)}{2}. \end{aligned}$$Jadi, rumus itu juga terbukti berlaku untuk $(m, n).$
Langkah induktif selesai.


Berdasarkan prinsip induksi matematika, terbukti bahwa barisan tersebut dapat dinyatakan secara eksplisit sebagai $a_{m,~n} = m + \dfrac{n(n+1)}{2}.$ $\blacksquare$

[collapse]

Soal Nomor 12

Jika $A_1, A_2, \cdots, A_n$ masing-masing adalah himpunan dengan $n \in \mathbb{N}, n \ge 2$, buktikan dengan induksi matematika bahwa generalisasi hukum De Morgan berikut benar.
$$\overline{A_1 \cap A_2 \cap \cdots \cap A_n} = \overline{A_1} \cup \overline{A_2} \cup \cdots \cup \overline{A_n}$$Catatan: Notasi $\overline{A_1}$ menyatakan komplemen dari himpunan $A_1.$

Pembahasan

Misalkan $n \ge 2$ merupakan bilangan asli. Misalkan juga $P(n)$ menyatakan bahwa jika $A_1, A_2, \cdots, A_n$ masing-masing adalah himpunan, maka berlaku $$\overline{A_1 \cap A_2 \cap \cdots \cap A_n} = \overline{A_1} \cup \overline{A_2} \cup \cdots \cup \overline{A_n}.$$Langkah Basis:
$P(2)$ benar karena untuk $n = 2,$
$$\overline{A_1 \cap A_2} = \overline{A_1} \cup \overline{A_2}$$sesuai dengan hukum De Morgan untuk dua himpunan.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k \ge 2,$ $P(k)$ benar, yaitu proposisi bahwa jika $A_1, A_2, \cdots, A_k$ masing-masing adalah himpunan, maka berlaku $$\overline{A_1 \cap A_2 \cap \cdots \cap A_k} = \overline{A_1} \cup \overline{A_2} \cup \cdots \cup \overline{A_k}.$$Akan ditunjukkan bahwa $P(k+1)$ benar, yaitu proposisi bahwa jika $A_1, A_2, \cdots, A_k, A_{k+1}$ masing-masing adalah himpunan, maka berlaku $$\overline{A_1 \cap A_2 \cap \cdots \cap A_k \cap A_{k+1}} = \overline{A_1} \cup \overline{A_2} \cup \cdots \cup \overline{A_k} \cup \overline{A_{k+1}}.$$Perhatikan bahwa
$$\begin{aligned} \overline{A_1 \cap A_2 \cap \cdots \cap A_k \cap A_{k+1}} & = \overline{(A_1 \cap A_2 \cap \cdots \cap A_k) \cap A_{k+1}} && (\text{Hukum Asosiatif}) \\ & = \overline{A_1 \cap A_2 \cap \cdots \cap A_k} \cup \overline{A_{k+1}} && (\text{Hukum De Morgan 2 Himpunan}) \\ & = (\overline{A_1} \cup \overline{A_2} \cup \cdots \cup \overline{A_k}) \cup \overline{A_{k+1}} && (\text{Hipotesis Induksi}) \\ & = \overline{A_1} \cup \overline{A_2} \cup \cdots \cup \overline{A_k} \cup \overline{A_{k+1}}. && (\text{Hukum Asosiatif}) \end{aligned}$$Jadi, terbukti bahwa $P(k+1)$ benar.
Berdasarkan prinsip induksi matematika, terbukti bahwa $P(n)$ benar untuk setiap bilangan asli $n \ge 2.$

[collapse]

Soal Nomor 13

Jika $A, B_1, B_2, \cdots, B_n$ masing-masing adalah himpunan dengan $n \in \mathbb{N}, n \ge 2,$ buktikan dengan induksi matematika bahwa generalisasi hukum distributif berikut benar.
$$A \cap (B_1 \cup B_2 \cup \cdots \cup B_n) = (A \cap B_1) \cup (A \cap B_2) \cup \cdots \cup (A \cap B_n)$$

Pembahasan

Misalkan $n \ge 2$ merupakan bilangan asli. Misalkan juga $P(n)$ menyatakan bahwa jika $A, B_1, B_2, \cdots, B_n$ masing-masing adalah himpunan, maka
$$A \cap (B_1 \cup B_2 \cup \cdots \cup B_n) = (A \cap B_1) \cup (A \cap B_2) \cup \cdots \cup (A \cap B_n).$$Langkah Basis:
$P(2)$ benar karena untuk $n = 2,$
$$A \cap (B_1 \cup B_2) = (A \cap B_1) \cup (A \cap B_2)$$sesuai dengan hukum distributif untuk dua himpunan.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k \ge 2,$ $P(k)$ benar, yaitu proposisi bahwa jika $A, B_1, B_2, \cdots, B_k$ masing-masing adalah himpunan, maka
$$A \cap (B_1 \cup B_2 \cup \cdots \cup B_k) = (A \cap B_1) \cup (A \cap B_2) \cup \cdots \cup (A \cap B_k).$$Akan ditunjukkan bahwa $P(k+1)$ benar, yaitu proposisi bahwa jika $A, B_1, B_2, \cdots, B_k, B_{k+1}$ masing-masing adalah himpunan, maka
$$A \cap (B_1 \cup B_2 \cup \cdots \cup B_k \cup B_{k+1}) = (A \cap B_1) \cup (A \cap B_2) \cup \cdots \cup (A \cap B_k) \cup (A \cap B_{k+1}).$$Perhatikan bahwa
$$\begin{aligned} A \cap (B_1 \cup B_2 \cup \cdots \cup B_k \cup B_{k+1}) & = A \cap ((B_1 \cup B_2 \cup \cdots \cup B_k) \cup B_{k+1}) && (\text{Hukum Asosiatif}) \\ & = (A \cap (B_1 \cup B_2 \cup \cdots \cup B_k)) \cup (A \cap B_{k+1}) && (\text{Hukum Distributif 2 Himpunan}) \\ & = (A \cap B_1) \cup (A \cap B_2) \cup \cdots \cup (A \cap B_k) \cup (A \cap B_{k+1}). && (\text{Hipotesis Induksi}) \end{aligned}$$Jadi, $P(k+1)$ terbukti benar. Karena $P(2)$ benar dan untuk sembarang bilangan asli $k \ge 2,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan asli $n \ge 2.$ $\blacksquare$ 

[collapse]

Soal Nomor 14

Untaian (string) bit memiliki panjang $n$ bit. Banyak untaian bit yang memuat bit $1$ sebanyak genap adalah $2^{n-1}.$ Buktikan pernyataan tersebut untuk $n \in \mathbb{N}.$
Contoh ilustrasi: Misalkan kita memiliki untaian bit dengan panjang $3$ bit. untaian bit yang memuat bit $1$ sebanyak genap adalah 000, 110, 101, dan 011 (ada $2^{3-1} = 4$).

Pembahasan

Misalkan $n$ merupakan bilangan asli. Misalkan juga $P(n)$ menyatakan banyak untaian bit dengan panjang $n$ bit yang memuat bit $1$ sebanyak genap adalah $2^{n-1}.$
Langkah Basis:
$P(1)$ benar karena untaian bit dengan panjang $1$ bit yang memuat bit $1$ sebanyak genap hanya $0$ (bit $1$-nya tidak ada, alias 0, dan $0$ adalah bilangan genap). Hal ini sesuai dengan rumus $2^{n-1} = 2^{1-1} = 1.$
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ $P(k)$ benar, yaitu banyak untaian bit dengan panjang $k$ bit yang memuat bit $1$ sebanyak genap adalah $2^{k-1}.$ Akan ditunjukkan bahwa $P(k+1)$ benar, yaitu banyak untaian bit dengan panjang $k+1$ bit yang memuat bit $1$ sebanyak genap adalah $2^{k}.$
Perhatikan bahwa untuk untaian bit dengan panjang $k$ bit, terdapat $2^k$ untaian bit berbeda yang dapat dibuat. Jika bit ke-$(k+1)$ diikutkan, akan ada $2^{k+1} = \color{red}{2} \cdot 2^k$ untaian bit berbeda yang dapat dibuat. Menurut hipotesis induksi, banyak untaian bit dengan panjang $k$ bit yang mempunyai bit $1$ sebanyak genap adalah $2^{k-1}.$ Ini berarti banyak untaian bit dengan panjang $k+1$ bit yang mempunyai bit $1$ sebanyak genap adalah $\color{red}{2}$ kali lipatnya, yaitu $2 \cdot 2^{k-1} = 2^k.$ Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan asli $n.$ $\blacksquare$

[collapse]

Soal Nomor 15

Di dalam sebuah pesta, setiap tamu berjabat tangan dengan tamu lainnya tepat sekali. Buktikan dengan induksi matematika bahwa jika ada $n$ orang tamu, maka banyak jabat tangan yang terjadi adalah $\dfrac{n(n-1)}{2}.$

Pembahasan

Misalkan $n$ merupakan bilangan asli. Misalkan juga $P(n)$ menyatakan bahwa jika ada $n$ orang tamu, maka banyak jabat tangan yang terjadi adalah $\dfrac{n(n-1)}{2}.$
Langkah Basis:
$P(1)$ benar karena untuk $n=1$ orang tamu, tidak ada jabat tangan yang terjadi, atau $\dfrac{1(1-1)}{2} = 0$ kali.
Langkah Induktif:
Misalkan untuk sembarang bilangan asli $k,$ $P(k)$ benar, yaitu jika ada $k$ orang tamu, maka banyak jabat tangan yang terjadi adalah $\dfrac{k(k-1)}{2}.$ Akan ditunjukkan bahwa $P(k+1)$ benar, yaitu jika ada $k+1$ orang tamu, maka banyak jabat tangan yang terjadi adalah $\dfrac{(k+1)k}{2}.$
Perhatikan bahwa untuk $k+1$ orang tamu, banyak jabat yang terjadi sama dengan banyak jabat tangan pada $k$ orang tamu ditambah dengan banyak jabat tangan yang dilakukan oleh tamu ke-$(k+1).$ Menurut hipotesis induksi, $k$ orang tamu ini akan melakukan jabat tangan sebanyak $\dfrac{k(k-1)}{2}.$ Tamu ke-$(k+1)$ ini akan berjabat tangan sebanyak $k$ kali dengan masing-masing $k$ orang tamu lainnya (masing-masing sekali) sehingga banyak jabat tangan keseluruhan adalah
$$\begin{aligned} \dfrac{k(k-1)}{2} + k & = \dfrac{k(k-1}{2} + \dfrac{2k}{2} \\ & = \dfrac{k^2+k}{2} \\ & = \dfrac{(k+1)k}{2}. \end{aligned}$$Jadi, $P(k+1)$ terbukti benar. Karena $P(1)$ benar dan untuk sembarang bilangan asli $k,$ kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1),$ berdasarkan prinsip induksi matematika, disimpulkan bahwa pernyataan $P(n)$ benar untuk setiap bilangan asli $n.$ $\blacksquare$

[collapse]

Soal Nomor 16

Temukan kesalahan dalam pembuktian berikut.


Kita ingin membuktikan bahwa $a^n = 1$ untuk semua bilangan bulat nonnegatif $n$ dan $a$ adalah bilangan real taknol dengan menggunakan induksi kuat.
Langkah Basis:
Untuk $n = 0$, jelas bahwa $a^0 = 1$ benar sesuai definisi $a^0.$
Langkah Induktif:
Misalkan pernyataan tersebut benar untuk $0, 1, 2, \cdots, n,$ yaitu $a^0 = 1, a^1 = 1,$ $a^2 = 1,$ $\cdots$, $a^n = 1.$ Kita ingin memperlihatkan bahwa $a^{n+1} = 1.$ Perhatikan bahwa
$$\begin{aligned} a^{n+1} & = \dfrac{a^n \cdot a^n}{a^{n-1}} \\ & = \dfrac{1 \cdot 1}{1} && (\text{Hipotesis Induksi}) \\ & = 1. \end{aligned}$$Jadi, terbukti bahwa $a^{n+1} = 1.$


Pembahasan

Kesalahan pembuktian dengan menggunakan induksi kuat di atas terjadi pada langkah induktif. Perhatikan bahwa ekspresi $a^{n-1}$ dimunculkan, padahal untuk $n = 0,$ kita dapatkan $a^{-1}$ yang nilainya tidak diasumsikan pada hipotesis induksi. Akibatnya, pembuktian menjadi cacat dan kita peroleh kesimpulan yang kurang tepat.

[collapse]