Induksi Matematika Dalam Pembuktian

Misalkan akan dibuktian bahwa rumus atau sifat $S\left( n \right)$ berlaku untuk semua bilangan asli $n$. Pembuktian rumus atau sifat $S\left( n \right)$ dengan menggunakan induksi matematika dikerjakan dengan algoritma sebagai berikut.

Algoritma : Pembuktian dengan induksi matematika

Langkah 1

Tunjukkan bahwa rumus $S\left( n \right)$ benar untuk $n=1$, atau \[\boxed{S\left( 1 \right)\text{ benar}}\]

Langkah 2

Tunjukkan bahwa jika rumus $S\left( n \right)$ benar untuk $n=k$, maka rumus $S\left( n \right)$ juga benar untuk nilai $n=k+1$ \[\boxed{S\left( k \right)\text{ benar} \Rightarrow S\left( {k + 1} \right)\text{ juga benar}}\]

Contoh 1

Buktikan bahwa:

${1^2} + {2^2} + {3^2} + \cdots + {n^2} = \sum\limits_{i = 1}^n {{i^2}} = \frac{1}{6}n\left( {n + 1} \right)\left( {2n + 1} \right)$

berlaku untuk semua $n$ bilangan asli.

Jawab

Misalkan $S\left( n \right)$ adalah rumus $\sum\limits_{i = 1}^n {{i^2}} = \frac{1}{6}n\left( {n + 1} \right)\left( {2n + 1} \right)$ berlaku untuk semua $n$ bilangan asli.

Langkah 1

Untuk $n=1$,

$\begin{array}{l} \sum\limits_{i = 1}^n {{i^2}} &= \frac{1}{6}n\left( {n + 1} \right)\left( {2n + 1} \right)\\ \Leftrightarrow \sum\limits_{i = 1}^1 {{i^2}} &= \frac{1}{6}1\left( {1 + 1} \right)\left( {2.1 + 1} \right)\\ \Leftrightarrow {1^2} &= \frac{1}{6}1\left( 2 \right)\left( 3 \right)\\ \Leftrightarrow 1 &= \frac{1}{6}\left( 2 \right)\left( 3 \right)\\ \Leftrightarrow 1 &= 1\left( {benar} \right) \end{array}$

Jadi, $S\left( n \right)$ benar untuk $n=1$ atau $S\left( 1 \right)$ benar.

Langkah 2

Misalkan $S\left( n \right)$ benar untuk $n=k$, maka $\sum\limits_{i = 1}^k {{i^2}} = \frac{1}{6}k\left( {k + 1} \right)\left( {2k + 1} \right)$

Selanjutnya harus dibuktikan bahwa $S\left( n \right)$ benar untuk $n=k+1$.

$\begin{array}{l} \sum\limits_{i = 1}^{k + 1} {{i^2}} &= \sum\limits_{i = 1}^k {{i^2}} + \sum\limits_{i = k + 1}^{k + 1} {{i^2}} \\ &= \frac{1}{6}k\left( {k + 1} \right)\left( {2k + 1} \right) + {\left( {k + 1} \right)^2}\\ &= \frac{1}{6}\left( {k + 1} \right)k\left( {2k + 1} \right) + {\left( {k + 1} \right)^2}\\ &= \frac{1}{6}\left( {k + 1} \right)\left[ {\left( {2{k^2} + k} \right) + \left( {6k + 6} \right)} \right]\\ &= \frac{1}{6}\left( {k + 1} \right)\left[ {\left( {2{k^2} + 7k + 6} \right)} \right]\\ &= \frac{1}{6}\left( {k + 1} \right)\left[ {\left( {k + 2} \right)\left( {2k + 3} \right)} \right]\\ &= \frac{1}{6}\left( {k + 1} \right)\left[ {\left( {k + 1} \right) + 1} \right]\left[ {2\left( {k + 1} \right) + 1} \right] \end{array}$

Bentuk $\frac{1}{6}\left( {k + 1} \right)\left[ {\left( {k + 1} \right) + 1} \right]\left[ {2\left( {k + 1} \right) + 1} \right]$ merupakan bagian ruas kanan $S\left( n \right)$ jika $n$ diganti dengan $n=k+1$.

Jadi, jika $S\left( n \right)$ benar untuk $n=k$ maka $S\left( n \right)$ juga benar untuk $n=k+1$.

Dengan demikian, terbukti bahwa $\sum\limits_{i = 1}^n {{i^2}} = \frac{1}{6}n\left( {n + 1} \right)\left( {2n + 1} \right)$ benar atau berlaku untuk semua $n$ bilangan asli.

Contoh 2

Dengan menggunakan induksi matematika, buktikan bahwa ${7^n} - 1$ habis dibagi oleh $6$, berlaku untuk semua $n$ bilangan asli.

Jawab

Misalkan $S\left( n \right)$ adalah sifat yang menyatakan bahwa $S\left( n \right)$ habis dibagi oleh $6$ berlaku untuk semua $n$ bilangan asli.

Langkah 1

untuk $n=1$, diperoleh ${7^1} - 1=6$ habis dibagi oleh $6$. Jadi, $S\left( n \right)$ benar untuk $n=1$ atau $S\left( 1 \right)$ benar.

Langkah 2

Andaikan $S\left( n \right)$ benar untuk $n=k$ maka diperoleh sifat ${7^k} - 1$ habis dibagi $6$. Karena ${7^k} - 1$ habis dibagi $6$, maka dapat dinyatakan sebagai ${7^k} - 1=6p$ dengan $p$ adalah sembarang bilangan asli. Selanjutnya harus ditunjukkan bahwa $S\left( n \right)$ juga benar untuk $n=k+1$, diperoleh:

$\begin{array}{l} {7^{k + 1}} - 1 &= {7.7^k} - 1\\ &= {7.7^k} - 7 + 7 - 1\\ &= 7\left( {{7^k} - 1} \right) + 6\\ &= 7\left( {6p} \right) + 6\\ &= 6\left( {7p + 1} \right) \end{array}$

Jadi, jika $S\left( n \right)$ benar untuk $n=k$ maka $S\left( n \right)$ juga benar untuk $n=k+1$. Dengan demikian terbukti bahwa ${7^n} - 1$ habis dibagi oleh $6$ berlaku untuk semua $n$ bilangan asli.

Contoh 3

Buktikan bahwa:

$1 + 3 + 6 + \cdots + \frac{1}{2}n\left( {n + 1} \right) = \sum\limits_{i = 1}^n {\frac{1}{2}i\left( {i + 1} \right)} = \frac{1}{6}n\left( {n + 1} \right)\left( {n + 2} \right)$

berlaku untuk semua $n$ bilangan asli.

Jawab

Misalkan $S\left( n \right)$ adalah rumus $\sum\limits_{i = 1}^n {\frac{1}{2}i\left( {i + 1} \right)} = \frac{1}{6}n\left( {n + 1} \right)\left( {n + 2} \right)$ berlaku untuk semua $n$ bilangan asli.

Langkah 1

Untuk $n=1$,

$\begin{array}{l} \sum\limits_{i = 1}^n {\frac{1}{2}i\left( {i + 1} \right)} &= \frac{1}{6}n\left( {n + 1} \right)\left( {n + 2} \right)\\ \Leftrightarrow \sum\limits_{i = 1}^1 {\frac{1}{2}i\left( {i + 1} \right)} &= \frac{1}{6}.1\left( {1 + 1} \right)\left( {1 + 2} \right)\\ \Leftrightarrow \frac{1}{2}.1\left( {1 + 1} \right) &= \frac{1}{6}.1\left( {1 + 1} \right)\left( {1 + 2} \right)\\ \Leftrightarrow 1 &= \frac{1}{6}.1\left( 2 \right)\left( 3 \right)\\ \Leftrightarrow 1 &= 1 \end{array}$

Jadi, $S\left( n \right)$ benar untuk $n=1$ atau $S\left( 1 \right)$ benar.

Langkah 2

Misalkan $S\left( n \right)$ benar untuk $n=k$, maka $\sum\limits_{i = 1}^k {\frac{1}{2}i\left( {i + 1} \right)} = \frac{1}{6}k\left( {k + 1} \right)\left( {k + 2} \right)$

Selanjutnya harus dibuktikan bahwa $S\left( n \right)$ benar untuk $n=k+1$.

$\begin{array}{l} \sum\limits_{i = 1}^{k + 1} {\frac{1}{2}i\left( {i + 1} \right)} &= \sum\limits_{i = 1}^k {\frac{1}{2}i\left( {i + 1} \right)} + \sum\limits_{i = k + 1}^{k + 1} {\frac{1}{2}i\left( {i + 1} \right)} \\ &= \frac{1}{6}k\left( {k + 1} \right)\left( {k + 2} \right) + \frac{1}{2}\left( {k + 1} \right)\left[ {\left( {k + 1} \right) + 1} \right]\\ &= \frac{1}{6}k\left( {k + 1} \right)\left( {k + 2} \right) + \frac{1}{2}\left( {k + 1} \right)\left( {k + 2} \right)\\ &= \frac{1}{6}\left( {k + 1} \right)\left( {k + 2} \right)\left( {k + 3} \right) \end{array}$

Bentuk $\frac{1}{6}\left( {k + 1} \right)\left( {k + 2} \right)\left( {k + 3} \right)$ merupakan bagian ruas kanan $S\left( n \right)$ jika $n$ diganti dengan $n=k+1$.

Jadi, jika $S\left( n \right)$ benar untuk $n=k$ maka $S\left( n \right)$ juga benar untuk $n=k+1$.

Dengan demikian, terbukti bahwa $\sum\limits_{i = 1}^n {\frac{1}{2}i\left( {i + 1} \right)} = \frac{1}{6}n\left( {n + 1} \right)\left( {n + 2} \right)$ benar atau berlaku untuk semua $n$ bilangan asli.

Contoh 4

Dengan menggunakan induksi matematika, buktikan bahwa ${a^n} - {b^n}$ habis dibagi oleh $\left( {a - b} \right)$, berlaku untuk semua $n$ bilangan asli.

Jawab

Misalkan $S\left( n \right)$ adalah sifat yang menyatakan bahwa ${a^n} - {b^n}$ habis dibagi oleh $\left( {a - b} \right)$ berlaku untuk semua $n$ bilangan asli.

Langkah 1

untuk $n=1$, diperoleh ${a^1} - {b^1} = a - b$ habis dibagi oleh $\left( {a - b} \right)$. Jadi, $S\left( n \right)$ benar untuk $n=1$ atau $S\left( 1 \right)$ benar.

Langkah 2

Andaikan $S\left( n \right)$ benar untuk $n=k$ maka diperoleh sifat ${a^k} - {b^k}$ habis dibagi $\left( {a - b} \right)$. Karena ${a^k} - {b^k}$ habis dibagi $\left( {a - b} \right)$, maka dapat dinyatakan sebagai ${a^k} - {b^k} = p\left( {a - b} \right)$ dengan $p$ adalah sembarang bilangan asli. Selanjutnya harus ditunjukkan bahwa $S\left( n \right)$ juga benar untuk $n=k+1$, diperoleh:

$\begin{array}{l} {a^{k + 1}} - {b^{k + 1}} &= a.{a^k} - b.{b^k}\\ &= a.{a^k} - b.{a^k} + b.{a^k} - b.{b^k}\\ &= {a^k}\left( {a - b} \right) + b\left( {{a^k} - {b^k}} \right)\\ &= {a^k}\left( {a - b} \right) + b.p\left( {a - b} \right)\\ &= \left( {a - b} \right)\left( {{a^k} + bp} \right) \end{array}$

dari hasil akhir diperoleh $\left( {a - b} \right)\left( {{a^k} + bp} \right)$ habis dibagi $\left( {a - b} \right)$. Jadi, jika $S\left( n \right)$ benar untuk $n=k$ maka $S\left( n \right)$ juga benar untuk $n=k+1$. Dengan demikian terbukti bahwa ${a^n} - {b^n}$ habis dibagi oleh $\left( {a - b} \right)$ berlaku untuk semua $n$ bilangan asli.