Soal dan Pembahasan – Induksi Matematika pada Keterbagian Bilangan

      Induksi matematika (atau induksi lengkap, kadang juga disebut sebagai Induksi Matematis, atau dalam bahasa Inggris, Mathematical Induction) adalah salah satu metode pembuktian pernyataan matematika yang melibatkan bilangan asli dan pembuktiannya itu dalam 2 tahap: Basis Induksi dan Langkah Induksi.

Baca Juga: Soal dan Pembahasan – Notasi Sigma     

         Suatu rumus atau lema umum yang berlaku untuk setiap bilangan asli (atau hanya tidak berlaku untuk bilangan asli tertentu) dapat dibuktikan kebenarannya dengan induksi matematika. Langkah-langkah dalam membuktikannya secara induksi adalah:

Tahap I: Basis Induksi

 Lakukan pemisalan bahwa pernyataan yang diberikan adalah $P_n$, dengan $n$ sebagai variabel induksi. Tunjukkan bahwa rumus atau pernyataan benar jika $n = 1$ (atau bilangan asli terkecil yang diberikan). Jika benar, lanjutkan ke tahap kedua.

Tahap II: Langkah Induksi

Tunjukkan bahwa jika rumus atau pernyataan benar untuk $P_k$ (hipotesis induksi), maka juga benar untuk $P_{k+1}$. Secara matematis ditulis, $P_k \Rightarrow P_{k+1}$  (kedua pernyataannya harus BENAR).
Catatan: Prinsip yang sama dengan efek domino juga terjadi pada mekanisme Rube Goldberg Machine.

Mekanisme Rube Goldberg Machine
Mekanisme Rube Goldberg Machine

Baca Juga: Soal dan Pembahasan – Barisan dan Deret Aritmetika

Soal-soal berikut merupakan soal tentang induksi matematika yang berhubungan dengan keterbagian bilangan. 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

Today Quote

Beberapa orang seperti lilin, yang membakar diri mereka sendiri untuk memberi cahaya kepada benda di sekitarnya.

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

Penyelesaian

Basis induksi:
Misalkan
$P_n: n^3 -n$ habis dibagi $6$.
Ambil $n = 1$, sehingga diperoleh
$P_1: 1^3 -1 = 0$ habis dibagi $6$. Pernyataan ini jelas benar. Jadi, $P_n$ benar untuk $n = 1$.
Langkah induksi:
Misalkan
$P_k: k^3 -k$ habis dibagi $6$, merupakan pernyataan yang diasumsikan benar. Akan ditunjukkan bahwa $P_{k+1}$ juga benar. Dalam hal ini,
$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)$, 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 Matematis, 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$.

Penyelesaian

Basis Induksi:
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$
Ambil $n = 1$, diperoleh
$P_1: 3~|~1^3 + 2(1)$
Jelas bahwa $3$ membagi habis dirinya sendiri, sehingga untuk $n = 1$, pernyataan yang akan dibuktikan di atas 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.
Sekarang, perhatikan bahwa
$P_{k+1}: 3~|~(k+1)^3+2(k+1) \bigstar$
Dalam hal ini, akan ditunjukkan bahwa $(k+1)^3 + 2(k+1)$ juga merupakan kelipatan 3. Hal ini dapat ditunjukkan sebagai berikut.
$\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 Matematis, 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}$.

Penyelesaian

Basis induksi:
Misalkan $P_n:
7^n -2^n$ habis dibagi $5$.

Ambil $n = 1$, berarti diperoleh
$P_1: 7^1 -2^1=5$, yang jelas habis dibagi $5$ sehingga pernyataannya 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, di mana $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 Matematis, 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.

Penyelesaian

Basis Induksi:
Misalkan $P_n: a^{2n-1} + b^{2n-1}$ habis dibagi oleh $a + b$.
Ambil $n = 1$, sehingga
$P_1: a + b$ habis dibagi oleh $a +b$ (dirinya sendiri) jelas merupakan pernyataan yang benar.
Langkah induksi:

Misalkan $P_k: a^{2k-1} + b^{2k-1}$ habis dibagi oleh $a + b$. Asumsikan pernyataan ini benar. Harus ditunjukkan bahwa $P_{k+1}$ juga benar, di mana
$P_{k+1}: a^{2k+1} + b^{2k+1}$ habis dibagi oleh $a + b$.
Sekarang, 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 Matematis, pernyataan $P_n$ benar untuk $n \in \mathbb{N}$. $\blacksquare$

[collapse]

Soal Nomor 5
Buktikan bahwa $n^3 + 5n$ habis dibagi $6$ untuk $n$ bilangan asli dengan menggunakan induksi matematika.

Penyelesaian

Basis induksi:
Misalkan
$P_n: n^3 + 5n$ habis dibagi $6$.
Ambil $n = 1$, berarti diperoleh
$P_1: 1^3 + 5(1) = 6$ habis dibagi $6$. Pernyataan ini jelas benar. Jadi, $P_n$ benar untuk $n = 1$.
Langkah induksi:
Sekarang, 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$, maka $P_{k+1}$ telah terbukti kebenarannya.
Dari sini, disimpulkan bahwa kebenaran $P_k$ mengimplikasikan kebenaran $P_{k+1}$ sehingga berdasarkan Prinsip Induksi Matematis, 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$, dengan $n$ bilangan asli.

Penyelesaian

Basis Induksi:
Misalkan proposisi di atas dinyatakam sebagai 
$P_n: x^n -1$ habis dibagi oleh $x -1$
Ambil $n = 1$, sehingga diperoleh
$P_1: x -1$ habis dibagi oleh $x -1$
Jelas bahwa suatu bilangan pasti habis dibagi oleh dirinya sendiri, sehingga pernyataan di atas bernilai benar. Ini artinya, untuk $n = 1$, $P_n$ bernilai benar. Basis induksi selesai. 
Langkah Induksi:
Sekarang misalkan $n = k$, berarti proposisi di atas menjadi
$P_k: x^k -1$ habis dibagi oleh $x -1$
Asumsikan $P_k$ benar, maka harus ditunjukkan bahwa $P_{k+1}$ juga benar, dengan
$P_{k+1}: x^{k+1} -1$ habis dibagi oleh $x – 1$. 
Sekarang, 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 Matematis, $P_n$ benar untuk $n$ bilangan asli. $\blacksquare$

[collapse]

Soal Nomor 7
Buktikan bahwa salah satu faktor dari $n^3+3n^2+2n$ adalah $3$ dengan $n$ bilangan asli.

Penyelesaian

Basis Induksi:
Misalkan proposisi di atas dinyatakan sebagai
$P_n$: Salah satu faktor dari $n^3+3n^2+2n$ adalah $3$. 
Ambil $n = 1$, sehingga 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, maka harus 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 Matematis, proposisi $P_n$ di atas benar untuk $n$ bilangan asli. $\blacksquare$

[collapse]

Soal Nomor 8
Buktikan bahwa salah satu faktor dari $2^{2n-1} + 3^{2n-1}$ adalah $5$ dengan $n$ bilangan asli.

Penyelesaian

Basis Induksi:
Misalkan proposisi di atas dinyatakan sebagai
$P_n$: Salah satu faktor dari $2^{2n-1} + 3^{2n-1}$ adalah $5$. 
Ambil $n = 1$, sehingga 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, maka harus 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 Matematis, proposisi $P_n$ di atas benar untuk $n$ bilangan asli. $\blacksquare$

[collapse]

Soal Nomor 9
Buktikan bahwa $41^n -14^n$ adalah kelipatan $27$ dengan $n$ bilangan asli.

Penyelesaian

Basis Induksi:
Misalkan proposisi di atas dinyatakan sebagai
$P_n: 41^n -14^n$ adalah kelipatan $27$
Ambil $n = 1$, sehingga 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, maka harus ditunjukkan bahwa $P_{k+1}$ juga benar, dengan
$P_{k+1}: 41^{k+1} -14^{k+1}$ adalah $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. Untuk 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 Matematis, proposisi $P_n$ di atas benar untuk $n$ bilangan asli. $\blacksquare$

[collapse]

Soal Nomor 10
Buktikan bahwa $4007^n -1$ habis dibagi $2003$ dengan $n$ bilangan asli.

Penyelesaian

Basis Induksi:
Misalkan proposisi di atas dinyatakan sebagai
$P_n: 4007^n -1$ habis dibagi $2003$. 
Ambil $n = 1$, sehingga diperoleh
$P_1$: $4007^1-1 = 4006$ habis dibagi $2003$. 
Pernyataan di atas benar ($4006 : 2003 = 2$). Dengan kata lain, $P_1$ bernilai benar. Basis induksi selesai. 
Langkah Induksi:
Misalkan $n = k$, berarti proposisi di atas dinyatakan kembali sebagai
$P_k: 4007^k – 1$ habis dibagi $2003$. 
Asumsikan $P_k$ benar, maka harus ditunjukkan bahwa $P_{k+1}$ juga benar, dengan
$P_{k+1}: 4007^{k+1} -1$ habis dibagi $2003$.
Sekarang, kita akan mengubah (memanipulasi) bentuk $4007^{k+1}-1$ sebagai berikut. 
$$\begin{aligned} 4007^{k+1}-1 \\ & = 4007^k \cdot 4007 – 1 \\ & = 4007^k \cdot (2003+2004) -(2004-2003) \\ & = 2003 \cdot 4007^k + 2004 \cdot 4700^k – 2004 + 2003 \\ & = \underbrace{2004(4700^k -1)}_{\text{berkelipatan 2003}} + \color{blue} {2003(4007^k + 1)} \end{aligned}$$Dua suku pada ekspresi terakhir di atas berkelipatan $2003$. Untuk suku pertama (yang telah diberi keterangan), memiliki kelipatan $2003$ berdasarkan asumsi bahwa $P_k$ benar. Untuk suku kedua (yang diberi warna biru), salah satu faktornya adalah $2003$, sehingga jelas merupakan kelipatan $2003$. 
Jadi, $P_{k+1}$ terbukti benar. 
Ternyata kebenaran $P_k$ mengimplikasikan kebenaran $P_{k+1}$. Berdasarkan Prinsip Induksi Matematis, proposisi $P_n$ di atas benar untuk $n$ bilangan asli. $\blacksquare$

[collapse]

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

Penyelesaian

Basis Induksi:
Misalkan $P_n: 2^{4n-1}$ habis dibagi $8$. 
Misalkan $n = 1$, berarti
$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, sehingga harus ditunjukkan bahwa $P_{k+1}$ juga benar, dengan
$P_{k+1}: 2^{4(k+1)-1} = 2^{4k+3}$ habis dibagi $8$.
Perhatikanlah 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$, maka pernyataan $P_{k+1}$ terbukti benar. Ini berarti, kebenaran $P_{k}$ mengimplikasikan kebenaran $P_{k+1}$. Berdasarkan Prinsip Induksi Matematis, $P_n$ benar untuk setiap $n \in \mathbb{N}$. $\blacksquare$

[collapse]

Soal Nomor 12
Periksa apakah $2002^{n+2} + 2003^{2n+1}$ habis dibagi $4005$ untuk $n$ bilangan asli.

Penyelesaian

Basis Induksi:
Misalkan konjektur di atas dinyatakan sebagai
$P_n: 2002^{n+2} + 2003^{2n+1}$ habis dibagi $4005$
Ambil $n = 1$, sehingga diperoleh
$P_1: 2002^3 + 2003^3 = 16.060.078.035$ habis dibagi $4005$
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: 2002^3 + 2003^5$ habis dibagi $4005$
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 $4005$ 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]

CategoriesUncategorizedTags, , ,

Leave a Reply

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!

Your email address will not be published. Required fields are marked *