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 induksi (induction 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. Langkah-langkah dalam membuktikannya secara induksi adalah sebagai berikut.

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.

Mekanisme Rube Goldberg Machine
Mekanisme Rube Goldberg Machine

Tahap I: Langkah Basis

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

Tahap II: Langkah Induksi

Tunjukkan bahwa untuk setiap $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 induksi seperti beberapa contoh berikut.

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

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

Langkah Induksi:
Untuk setiap 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 Induksi:
Untuk setiap 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 Induksi:
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 Induksi:
Untuk setiap 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.

Soal Nomor 1

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

Pembahasan

Misalkan
$P(n): n^3 -n$ habis dibagi $6$ untuk $n \in \mathbb{N}.$
Langkah Basis:

Untuk $n = 1$, diperoleh
$P(1): 1^3 -1 = 0$ habis dibagi $6$.
Pernyataan $P(1)$ bernilai benar. Basis induksi selesai.
Langkah Induksi:
Misalkan $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$. Oleh karenanya, $P(k+1)$ benar.
Jadi, dapat disimpulkan kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1)$ sehingga berdasarkan prinsip induksi matematika, pernyataan $P(n)$ benar untuk $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

Perhatikan bahwa $n^3 + 2n$ merupakan kelipatan 3 atau dengan kata lain, $n^3 + 2n$ habis dibagi $3$.
Misalkan $P(n): 3~|~n^3 + 2n$ untuk $n \in \mathbb{N}.$
Langkah Basis:
Untuk $n = 1$, diperoleh
$P(1): 3~|~1^3 + 2(1).$
Pernyataan $P(1)$ bernilai benar. Basis induksi selesai.
Langkah Induksi:
Misalkan
$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$.
Dari sini, disimpulkan bahwa kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1)$ sehingga berdasarkan prinsip induksi matematika, pernyataan $P(n)$ benar untuk $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 $P(n): 7^n -2^n$ habis dibagi $5$ untuk $n \in \mathbb{N}.$
Langkah Basis:
Untuk $n = 1$, diperoleh
$P(1): 7^1 -2^1=5$, yang jelas habis dibagi $5.$
Pernyataan $P(1)$ bernilai benar. Basis induksi selesai. 

Langkah Induksi:
Misalkan $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 $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$. Jadi, $P(k+1)$ dapat dibagi $5$.
Dari sini, disimpulkan bahwa kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1)$ sehingga berdasarkan prinsip induksi matematika, pernyataan $P(n)$ benar untuk $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 $P(n): a^{2n-1} + b^{2n-1}$ habis dibagi oleh $a + b$ untuk $n \in \mathbb{N}.$
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. Basis induksi selesai.
Langkah Induksi:

Misalkan $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)$ bernilai benar.

Dari sini, disimpulkan bahwa kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1)$ sehingga berdasarkan prinsip induksi matematika, pernyataan $P(n)$ benar untuk $n \in \mathbb{N}$. $\blacksquare$

[collapse]

Soal Nomor 5

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

Pembahasan

Misalkan $P(n): n^3 + 5n$ habis dibagi $6$ untuk $n \in \mathbb{N}.$
Langkah Basis:
Untuk$n = 1$, diperoleh
$P(1): 1^3 + 5(1) = 6$ habis dibagi $6$.
Pernyataan $P(1)$ bernilai benar. Basis induksi selesai.

Langkah Induksi:
Misalkan
$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$, $P(k+1)$ telah terbukti kebenarannya.
Dari sini, disimpulkan bahwa kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1)$ sehingga berdasarkan prinsip induksi matematika, pernyataan $P(n)$ benar untuk $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 proposisi di atas dinyatakan sebagai 
$P(n): x^n -1$ habis dibagi oleh $x -1$ untuk $n \in \mathbb{N}.$
Langkah Basis:
Untuk $n = 1$, diperoleh
$P(1): x -1$ habis dibagi oleh $x -1.$
Pernyataan $P(1)$ bernilai benar. Basis induksi selesai.
Langkah Induksi:
Misalkan $n = k$, berarti proposisi di atas dapat ditulis sebagai
$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.
Ini berarti kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1)$. Berdasarkan prinsip induksi matematika, $P(n)$ benar untuk bilangan asli $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 proposisi di atas dinyatakan sebagai
$P(n)$: Salah satu faktor dari $n^3+3n^2+2n$ adalah $3$ untuk $n \in \mathbb{N}.$
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. Basis induksi selesai. 
Langkah Induksi:
Misalkan $n = k$, berarti proposisi di atas dinyatakan kembali sebagai
$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. 
Ternyata kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1)$. Berdasarkan prinsip induksi matematika, proposisi $P(n)$ di atas benar untuk bilangan asli $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 proposisi di atas dinyatakan sebagai
$P(n)$: Salah satu faktor dari $2^{2n-1} + 3^{2n-1}$ adalah $5$ untuk $n \in \mathbb{N}.$
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. Basis induksi selesai. 
Langkah Induksi:
Misalkan $n = k$, berarti proposisi di atas dinyatakan kembali sebagai
$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. 
Ternyata kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1)$. Berdasarkan prinsip induksi matematika, proposisi $P(n)$ di atas benar untuk bilangan asli $n.$ $\blacksquare$

[collapse]

Soal Nomor 9

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

Pembahasan

Misalkan proposisi di atas dinyatakan sebagai
$P(n): 41^n -14^n$ adalah kelipatan $27$ untuk $n \in \mathbb{N}.$
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. Basis induksi selesai. 
Langkah Induksi:
Misalkan $n = k$, berarti proposisi di atas dinyatakan kembali sebagai
$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. 
Ternyata kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1)$. Berdasarkan prinsip induksi matematika, proposisi $P(n)$ di atas benar untuk bilangan asli $n.$ $\blacksquare$

[collapse]

Soal Nomor 10

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

Pembahasan

Misalkan proposisi di atas dinyatakan sebagai
$P(n): 2^{6n} + 3^{2n-2}$ habis dibagi $5$ untuk $n \in \mathbb{N}.$
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. Basis induksi selesai. 
Langkah Induksi:
Misalkan $n = k$, berarti proposisi di atas dinyatakan kembali sebagai
$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 induksi bahwa $P(k)$ benar. Dengan demikian, penjumlahan dua suku tersebut juga habis dibagi $5.$ Jadi, $P(k+1)$ terbukti benar. 
Ternyata kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1)$. Berdasarkan prinsip induksi matematika, proposisi $P(n)$ di atas benar untuk bilangan asli $n.$ $\blacksquare$

[collapse]

Soal Nomor 11

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

Pembahasan

Misalkan proposisi di atas dinyatakan sebagai
$P(n): 4.007^n -1$ habis dibagi $2.003$ untuk $n \in \mathbb{N}.$
Langkah Basis:
Untuk $n = 1,$ diperoleh
$P(1)$: $4.007^1-1 = 4.006$ habis dibagi $2.003.$ 
Jadi, $P(1)$ bernilai benar. Basis induksi selesai. 
Langkah Induksi:
Misalkan $n = k$, berarti proposisi di atas dinyatakan kembali sebagai
$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. 
Ternyata kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1)$. Berdasarkan prinsip induksi matematika, proposisi $P(n)$ di atas benar untuk bilangan asli $n.$ $\blacksquare$

[collapse]

Soal Nomor 12

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

Pembahasan

Misalkan $P(n): 2^{4n-1}$ habis dibagi $8$ untuk $n \in \mathbb{N}.$
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$. Basis induksi selesai.
Langkah Induksi:
Misalkan $n = k$, berarti
$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}$ atau $16$ habis dibagi $8$, 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 13

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

Pembahasan

Misalkan $P(x): 5^{2x}+3x-1$ habis dibagi $9$ untuk $x \in \mathbb{N}.$
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$. Basis induksi selesai.
Langkah Induksi:
Misalkan $x = k$, berarti
$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. Ini berarti kebenaran $P(k)$ mengimplikasikan kebenaran $P(k+1)$. Berdasarkan prinsip induksi matematika, $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 konjektur di atas dinyatakan sebagai
$P(n): 2.002^{n+2} + 2.003^{2n+1}$ habis dibagi $4.005$ untuk $n \in \mathbb{N}.$
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 basis induksi 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, basis induksi berakhir. Langkah induksi 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 basis induksi dapat dilakukan sampai beberapa nilai $n$ pertama (tujuannya untuk memastikan saja). Lagipula, jika soal ini diteruskan sampai langkah induksi, kita tidak dapat menemukan kesimpulan yang semestinya. Lebih lanjut, apabila soal berbunyi “buktikan/tunjukkan…. “, tetapi basis induksi 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 $P(n)$ menyatakan banyaknya himpunan bagian dari himpunan dengan $n$ anggota adalah $2^n$ untuk setiap bilangan bulat $n \ge 0.$
Basis Induksi:
$P(0)$ benar karena himpunan kosong memiliki $2^0 = 1$ himpunan bagian, yaitu dirinya sendiri. Basis induksi selesai.
Langkah Induksi:
Misalkan $P(k)$ menyatakan banyaknya himpunan bagian dari himpunan dengan $k$ anggota adalah $2^k$ untuk setiap 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 $(n+1)$ anggota dan terdapat $a_1 \in A.$ Notasi $\mathcal{S}(A)$ menyatakan himpunan bagian dari $A.$
$$|\mathcal{S}(A)| = 2|\mathcal{S}(A \setminus \{a_1\})|$$Karena $A \setminus \{a_1\}$ memuat $k$ anggota, nilai dari $|\mathcal{S}(A \setminus \{a_1\})| = 2^k$ sesuai dengan hipotesis induksi. Akibatnya, diperoleh
$$|\mathcal{S}(A)| = 2 \cdot 2^k = 2^{k+1}.$$Jadi, terbukti bahwa $P(k+1)$ benar. Berdasarkan prinsip induksi matematika, terbukti bahwa $P(n)$ benar untuk setiap bilangan bulat $n \ge 0.$

[collapse]

Soal Nomor 2

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 $P(n)$ menyatakan papan berpetak dengan ukuran $6 \times 2^n$ dapat ditutupi oleh ubin tiga petak berbentuk huruf L untuk $n \in \mathbb{N}.$
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 Induksi:
Misalkan $P(k)$ benar untuk $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.
Berdasarkan prinsip induksi matematika, terbukti bahwa $P(n)$ benar untuk setiap bilangan asli $n.$

[collapse]

Soal Nomor 3

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 $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 dengan $n \in \mathbb{N}.$
Basis Induksi:
$P(1)$ benar seperti yang ditunjukkan pada gambar berikut. Petak putih merepresentasikan petak yang dihilangkan.
Langkah Induksi:
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 dengan $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)$ benar.
Berdasarkan prinsip induksi matematika, terbukti bahwa $P(n)$ benar untuk setiap bilangan bulat positif $n.$

[collapse]

Soal Nomor 4

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 $P(n)$ menyatakan ada setidaknya satu orang yang tidak terlempar kue ketika terdapat $m = 2n + 1$ orang untuk bilangan cacah $n.$
Langkah Basis:
$P(0)$ benar karena hanya ada $m = 2(0) + 1 = 1$ orang sehingga tidak ada lemparan kue yang terjadi. Basis induksi selesai.
Langkah Induksi:
Asumsikan $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.
Berdasarkan prinsip induksi matematika, terbukti bahwa $P(n)$ benar untuk setiap bilangan cacah $n.$

[collapse]

Soal Nomor 5

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 $P(n)$ menyatakan $(1 + a)^n \ge 1 + an$ untuk setiap bilangan asli $n.$
Basis Induksi:
$P(1)$ benar karena jelas bahwa $(1 + a)^1 \ge 1 + a(1).$ Basis induksi selesai.
Langkah Induksi:
Misalkan $P(k)$ menyatakan $(1 + a)^k \ge 1 + ak$ untuk setiap 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.
Berdasarkan prinsip induksi matematika, terbukti bahwa $P(n)$ benar untuk setiap bilangan asli $n.$

[collapse]

Soal Nomor 6

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 $P(n): A^n = \begin{pmatrix} a^n & 0 \\ 0 & b^n \end{pmatrix}$ untuk $n \in \mathbb{N}.$
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$. Basis induksi selesai.
Langkah Induksi:
Misalkan $n = k$, berarti
$$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 7

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 induksinya 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).$
Basis Induksi:
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.$$Basis induksi selesai.
Langkah Induksi:
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 induksi selesai.


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

[collapse]

Soal Nomor 8

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 induksinya 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).$
Basis Induksi:
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.$$Basis induksi selesai.
Langkah Induksi:
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 induksi 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 9

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 induksinya 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).$
Basis Induksi:
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.$$Basis induksi selesai.
Langkah Induksi:
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 induksi 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 10

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 $P(n)$ adalah proposisi 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}.$$Basis Induksi:
$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 Induksi:
Misalkan $P(k)$ benar (hipotesis induksi), 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 11

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 $P(n)$ adalah proposisi 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).$$Basis Induksi:
$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 Induksi:
Misalkan $P(k)$ benar (hipotesis induksi), 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.
Berdasarkan prinsip induksi matematika, terbukti bahwa $P(n)$ benar untuk setiap bilangan asli $n \ge 2.$

[collapse]

Soal Nomor 12

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

Pembahasan

Misalkan $P(n)$ menyatakan banyak untaian biner dengan panjang $n$ bit yang memuat bit $1$ sebanyak genap adalah $2^{n-1}$ untuk $n \in \mathbb{N}.$
Basis Induksi:
$P(1)$ benar karena untaian biner 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 Induksi:
Misalkan $P(k)$ benar (hipotesis induksi), yaitu banyak untaian biner dengan panjang $k$ bit yang memuat bit $1$ sebanyak genap adalah $2^{k-1}.$ Akan ditunjukkan bahwa $P(k+1)$ benar, yaitu banyak untaian biner dengan panjang $k+1$ bit yang memuat bit $1$ sebanyak genap adalah $2^{k}.$
Perhatikan bahwa untuk untaian biner dengan panjang $k$ bit, terdapat $2^k$ untaian biner berbeda yang dapat dibuat. Jika bit ke-$(k+1)$ diikutkan, akan ada $2^{k+1} = \color{red}{2} \cdot 2^k$ untaian biner berbeda yang dapat dibuat. Menurut hipotesis induksi, banyak untaian biner dengan panjang $k$ bit yang mempunyai bit $1$ sebanyak genap adalah $2^{k-1}.$ Ini berarti banyak untaian biner 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)$ benar.
Berdasarkan prinsip induksi matematika, terbukti bahwa $P(n)$ benar untuk setiap bilangan asli $n.$

[collapse]

Soal Nomor 13

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

Nilai $n$ paling kecil adalah $1.$ Misalkan $P(n)$ menyatakan bahwa jika ada $n$ orang tamu, maka banyak jabat tangan yang terjadi adalah $\dfrac{n(n-1)}{2}.$
Basis Induksi:
$P(1)$ benar karena untuk $n=1$ orang tamu, tidak ada jabat tangan yang terjadi, atau $\dfrac{1(1-1)}{2} = 0$ kali.
Langkah Induksi:
Misalkan $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. Berdasarkan prinsip induksi matematika, terbukti bahwa $P(n)$ benar untuk setiap bilangan asli $n.$

[collapse]

Soal Nomor 14

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.
Basis Induksi:
Untuk $n = 0$, jelas bahwa $a^0 = 1$ benar sesuai definisi $a^0.$
Langkah Induksi:
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 induksi. 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]

 

4.2 5 votes
Article Rating

Silakan beri tanggapan dan saran, tidak perlu sungkan. Mohon juga diinformasikan melalui kolom komentar ini bila ada kesalahan pengetikan sekecil apapun (typo atau bahasa latex yang error) atau kesalahan konsep dan pembahasan soal. Terima kasih. Ganbatte!

Subscribe
Notify of
guest

3 Comments
Newest
Oldest Most Voted
Inline Feedbacks
View all comments
Muhamad Alfian Nurdiansyah

Saya ingin jawaban no 6

Rosnani

terima kasih sdh berbagi …semoga jadi amal kebaikan dan pahala.aamiin.