Induksi Matematika

Salah satu metode pembuktian yang dapat dipergunakan bagi perny ataan yang melibatkan kuantor universal adalah pembuktian dengan induksi. Pembuktian dengan induksi hanya dapat dipergunakan bila kuantor universal berhubungan dengan dengan bilangan bulat posi tip $Z^+$ atau bilangan asli $N$. Berikut diberikan pengertian induksi.

Definisi induksi:
Andaikan $S$ adalah himpunan yang terdiri dari bilangan asli dan mempunyai sifat bila $n \in S$, maka $n + 1 \in S$. Himpunan $S$ disebut sebagai himpunan induktif.

Metoda pembuktian induksi matematika didasarkan pada sifat-sifat bilangan bulat positip, yang dikenal sebagai Prinsip induksi mate matika.

Prinsip induksi matematika:
Andaikan $S$ adalah himpunan induktif dan $1 \in S$, maka $S$ adalah himpunan semua bilangan asli $N$.

Sebuah bukti dengan induksi dilakukan dengan mengikuti tiga langkah berikut:
Langkah 1: Definisikan himpunan bagian $S \subseteq N$ sedemikian hingga bila $S = N$, maka kesimpulan yang kita inginkan adalah benar.
Langkah 2: Perlihatkan bahwa $1 \in S$.
Langkah 3: Perlihatkan bahwa $S$ adalah himpunan induktif, yakni bila $n \in S$ maka $(n + 1) \in S$.
Kita perhatikan contoh berikut:

Buktikan bahwa untuk setiap bilangan bulat positif $n \ge 1$, berlaku $\displaystyle \sum \limits^{n}_{k=1}k=\frac{n(n+1)}{2}$

bukti:
Kita buktikan dengan induksi matematika. Untuk itu kita ikuti ketiga langkah berikut.
Langkah1: Definisikan himpunan $S \subseteq N$. Pada kasus ini kita definisikan himpunan $S$ sebagai himpunan $S=${$\displaystyle n \in N~:~\sum \limits^{n}_{k=1}k=\frac{n(n+1)}{2}$}.
Langkah 2: Perlihatkan bahwa $1 \in S$. Perhatikan bahwa untuk $n = 1$, $1 = 1(1 + 1)/2$ sehingga $1 \in S$.
Langkah 3: Perlihatkan bahwa $S$ adalah himpunan induktif, yakni bila $n \in S$ maka $(n + 1) \in S$. Andaikan $n \in S$, yakni $\displaystyle \sum \limits^{n}_{k=1}k=\frac{n(n+1)}{2}$. Akibatnya $$\sum \limits^{n+1}_{k=1}k=\sum \limits^{n}_{k=1}k+(n+1)$$ yakni $$\sum \limits^{n+1}_{k=1}k=\frac{n(n+1)}{2}+(n+1)$$ $$=\frac{n(n+1)}{2}+\frac{2(n+1)}{2}$$ $$=\frac{(n+1)(n+2)}{2}$$ $$=\frac{(n+1)((n+1)+1)}{2}$$ Jadi $(n+1) \in S$.
Sekarang kita dapat simpulkan bahwa $S = N$, yakni $\displaystyle \sum \limits^{n}_{k=1}k=\frac{n(n+1)}{2}$ adalah benar untuk semua bilangan bulat $n \ge 1$.

Demikianlah postingan mengenai materi induksi matematika. Sampai jumpa dan semoga bermanfaat.