 |
| Ilustrasi induksi matematika |
Dalam matematika, induksi matematika merupakan suatu cara pembuktian yang cukup umum digunakan. Pembuktian ini seringkali digambarkan dengan menggunakan sederetan batu bata yang telah disusun sedemikian hingga jika kita menjatuhkan salah satu bata ke arah bata di belakangnya, maka bata-bata yang ada di belakangnya tersebut akan ikut jatuh. Bata-bata tersebut akan ikut jatuh hanya dengan kondisi:
(i) Setidaknya satu diantara bata-bata tersebut jatuh
(ii) Jarak antar deretan bata lebih kecil daripada tinggi bata.
Dalam induksi matematika, bata-bata tersebut merupakan bilangan asli dan jatuhnya bata tersebut adalah teorema/pernyataan yang ingin kita buktikan. Pembuktian ini dilakukan dengan memeriksa:
(i) Pernyataan tersebut benar untuk suatu bilangan asli $n_0$,
(ii) Andaikan pernyataan tersebut benar untuk bilangan asli $n=k$, maka pernyataan tersebut juga harus benar untuk $n=k+1$.
Jika keduanya terpenuhi, maka pernyataan tersebut terbukti benar untuk semua bilangan asli $n>=n_0$.
Contoh 1.
Buktikan dengan induksi matematika $1+2+3+4+...+n= \frac{n(n+1)}{2}$.
Penyelesaian:
(i) Akan ditunjukkan bahwa $p(n)$ benar untuk $n=1$
Jelas bahwa,
$1=\frac{1(1+1)}{2}$
$1=1$
Jadi, $p(n)$ benar untuk $n=1$
(ii) Andaikan $p(n)$ benar untuk $n=k$ sehingga dipunyai $1+2+3+4+...+k= \frac{k(k+1)}{2}$.
Akan dibuktikan bahwa $p(n)$ benar untuk $n=k+1$.
(yang akan dibuktikan yaitu $1+2+3+4+...+(k+1)= \frac{(k+1)(k+2)}{2}$
$1+2+3+4+...+(k+1)=1+2+3+4+...+k+(k+1)$
ingat bahwa dalam urutan bilangan asli bilangan $k$ muncul sebelum bilangan $k+1$
$\leftrightarrow 1+2+3+4+...+(k+1)= \frac{k(k+1)}{2} + k+1$
$\leftrightarrow 1+2+3+4+...+(k+1)= \frac{k(k+1)}{2} + \frac{2(k+1)}{2}$
$\leftrightarrow 1+2+3+4+...+(k+1)= \frac{k(k+1)+2(k+1)}{2}$
$\leftrightarrow 1+2+3+4+...+(k+1)= \frac{(k+1)(k+2)}{2}$
Jadi, $p(n)$ juga benar untuk $n=k+1$
Karena pernyataan tersebut memenuhi kedua syarat induksi, maka pernyataan tersebut benar.
Contoh 2.
Buktikan dengan induksi matematika $2+4+6+8+...+2n= n(n+1)$.
Penyelesaian:
(i) Akan ditunjukkan bahwa $p(n)$ benar untuk $n=1$
Jelas bahwa,
$2\cdot 1=1(1+1)$
$2=2$
Jadi, $p(n)$ benar untuk $n=1$
(ii) Andaikan $p(n)$ benar untuk $n=k$ sehingga dipunyai $2+4+6+8+...+2k= k(k+1)$.
Akan dibuktikan bahwa $p(n)$ benar untuk $n=k+1$.
(yang akan dibuktikan yaitu $2+4+6+8+...+2(k+1)= (k+1)(k+2)$)
$2+4+6+8+...+2(k+1)=2+4+6+8+...+2k+2(k+1)$
ingat bahwa dalam urutan bilangan asli bilangan $k$ muncul sebelum bilangan $k+1$
$\leftrightarrow 2+4+6+8+...+2(k+1)= k(k+1)+ 2(k+1)$
$\leftrightarrow 2+4+6+8+...+2(k+1)= (k+1)(k+2)$
diperoleh dengan memanfaatkan sifat distributif
Jadi, $p(n)$ juga benar untuk $n=k+1$
Diperoleh bahwa pernyataan tersebut memenuhi kedua syarat induksi, maka pernyataan $2+4+6+8+...+2n= n(n+1)$ terbukti benar.
Contoh 3.
Buktikan dengan induksi matematika $1+3+5+...+(2n-1)= n^2$.
Penyelesaian:
(i) Akan ditunjukkan bahwa $p(n)$ benar untuk $n=1$
Jelas bahwa,
$2\cdot 1 - 1=1^2$
$1=1$
Jadi, $p(n)$ benar untuk $n=1$
(ii) Andaikan $p(n)$ benar untuk $n=k$ sehingga dipunyai $1+3+5+...+(2k-1)= k^2$.
Akan dibuktikan bahwa $p(n)$ benar untuk $n=k+1$.
(yang akan dibuktikan yaitu $1+3+5+...+(2(k+1)-1)= (k+1)^2$
$1+3+5+...+(2(k+1)-1)= 1+3+5+...+(2k-1)+(2(k+1)-1)$
ingat bahwa dalam urutan bilangan asli bilangan $k$ muncul sebelum bilangan $k+1$
$\leftrightarrow 1+3+5+...+(2(k+1)-1)= k^2+(2(k+1)-1)$
$\leftrightarrow 1+3+5+...+(2(k+1)-1)= k^2+(2k+2-1)$
$\leftrightarrow 1+3+5+...+(2(k+1)-1)= k^2+2k+1$
$\leftrightarrow 1+3+5+...+(2(k+1)-1)= (k+1)^2$
Jadi, $p(n)$ juga benar untuk $n=k+1$
Diperoleh bahwa pernyataan tersebut memenuhi kedua syarat induksi, maka pernyataan $1+3+5+...+(2n-1)= n^2$ terbukti benar.
Contoh 4.
Buktikan dengan induksi matematika $1\cdot 2+2 \cdot 3+ 3\cdot 4+ 4\cdot 5+...+n(n+1)= \frac{n(n+1)(n+2)}{3}$.
Penyelesaian:
(i) Akan ditunjukkan bahwa $p(n)$ benar untuk $n=1$
Jelas bahwa,
$1\cdot 2=\frac{1(1+1)(1+2)}{3}$
$2=2$
Jadi, $p(n)$ benar untuk $n=1$
(ii) Andaikan $p(n)$ benar untuk $n=k$ sehingga dipunyai $1\cdot 2+2 \cdot 3+ 3\cdot 4+ 4\cdot 5+...+k(k+1)= \frac{k(k+1)(k+2)}{3}$.
Akan dibuktikan bahwa $p(n)$ benar untuk $n=k+1$.
(yang akan dibuktikan yaitu $1\cdot 2+2 \cdot 3+ 3\cdot 4+ 4\cdot 5+...+(k+1)(k+2)= \frac{(k+1)(k+2)(k+3)}{3}$
$1\cdot 2+2 \cdot 3+ 3\cdot 4+ 4\cdot 5+...+(k+1)(k+2)= 1\cdot 2+2 \cdot 3+ 3\cdot 4+ 4\cdot 5+...+k(k+1)+(k+1)(k+2)$
ingat bahwa dalam urutan bilangan asli bilangan $k$ muncul sebelum bilangan $k+1$
$\leftrightarrow 1\cdot 2+2 \cdot 3+ 3\cdot 4+ 4\cdot 5+...+(k+1)(k+2)= \frac{k(k+1)(k+2)}{3}+(k+1)(k+2)$
$\leftrightarrow 1\cdot 2+2 \cdot 3+ 3\cdot 4+ 4\cdot 5+...+(k+1)(k+2)= \frac{k(k+1)(k+2)}{3}+\frac{3(k+1)(k+2)}{3}$
diperoleh dengan menyamakan penyebut
$\leftrightarrow 1\cdot 2+2 \cdot 3+ 3\cdot 4+ 4\cdot 5+...+(k+1)(k+2)= \frac{k(k+1)(k+2)+3(k+1)(k+2)}{3}$
$\leftrightarrow 1+3+5+...+(2(k+1)-1)= \frac{(k+1)(k+2)(k+3)}{3}$
diperoleh dengan memanfaatkan sifat distributif
Jadi, $p(n)$ juga benar untuk $n=k+1$
Diperoleh bahwa pernyataan tersebut memenuhi kedua syarat induksi, maka pernyataan $1\cdot 2+2 \cdot 3+ 3\cdot 4+ 4\cdot 5+...+n(n+1)= \frac{n(n+1)(n+2)}{3}$ terbukti benar.
Contoh 5.
Buktikan dengan induksi matematika $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3 \cdot 4}+...+\frac{1}{n(n+1)}= \frac{n}{n+1}$.
Penyelesaian:
(i) Akan ditunjukkan bahwa $p(n)$ benar untuk $n=1$
Jelas bahwa,
$1\cdot 2=\frac{1(1+1)(1+2)}{3}$
$2=2$
Jadi, $p(n)$ benar untuk $n=1$
(ii) Andaikan $p(n)$ benar untuk $n=k$ sehingga dipunyai $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3 \cdot 4}+...+\frac{1}{k(k+1)}= \frac{k}{k+1}$.
Akan dibuktikan bahwa $p(n)$ benar untuk $n=k+1$.
(yang akan dibuktikan yaitu $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3 \cdot 4}+...+\frac{1}{(k+1)(k+2)}= \frac{k+1}{k+2}$)
$\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3 \cdot 4}+...+\frac{1}{(k+1)(k+2)}=\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3 \cdot 4}+...+\frac{1}{k(k+1)}+\frac{1}{(k+1)(k+2)}$
ingat bahwa dalam urutan bilangan asli bilangan $k$ muncul sebelum bilangan $k+1$
$\leftrightarrow \frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3 \cdot 4}+...+\frac{1}{(k+1)(k+2)}= \frac{k}{(k+1)}+\frac{1}{(k+1)(k+2)}$
$\leftrightarrow \frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3 \cdot 4}+...+\frac{1}{(k+1)(k+2)}= \frac{k(k+2)+1}{(k+1)(k+2)}$
$\leftrightarrow \frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3 \cdot 4}+...+\frac{1}{(k+1)(k+2)}= \frac{k^2+2k+1}{(k+1)(k+2)}$
$\leftrightarrow \frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3 \cdot 4}+...+\frac{1}{(k+1)(k+2)}= \frac{(k+1)(k+1)}{(k+1)(k+2)}$
$\leftrightarrow \frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3 \cdot 4}+...+\frac{1}{(k+1)(k+2)}= \frac{(k+1)}{(k+2)}$
Jadi, $p(n)$ juga benar untuk $n=k+1$
Diperoleh bahwa pernyataan tersebut memenuhi kedua syarat induksi, maka pernyataan $\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3 \cdot 4}+...+\frac{1}{n(n+1)}= \frac{n}{n+1}$ terbukti benar.
Contoh 6.
Buktikan dengan induksi matematika bahwa
Penyelesaian:
