INDUKSI MATEMATIKA

Download Tayangan

Induksi matematika merupakan salah satu alat pembuktian yang sering digunakan di ranah matematika. Biasanya induksi matematika digunakan untuk membuktikan formula matematika bersifat diskrit. Berikut ini diberikan algoritma pembuktian dalam induksi matematika.

Misalkan untuk setiap bilangan asli n kita mempunyai pernyataan s(n). Jika :

  • s(1) benar,
  • Jika s(n) benar untuk n=k, maka s(n) benar untuk n=k+1.

Maka s(n) benar untuk setiap bilangan asli n.

Catatan : Dengan cara ini, s(1) benar mengakibatkan s(2) benar, selanjutnya s(2) benar mengakibatkan s(3) benar, dan seterusnya.

Sebagai contoh, kita akan menggunakan induksi matematika untuk membuktikan bahwa \forall n\in \mathbb{Z}^+, 13 \mid 100^n - 61^n . Misalkan s(n): 13 \mid 100^n -61^n. Pertama-tama akan ditunjukkan s(1) benar. Perhatikan bahwa

    \[100^1 - 61^1 = 39 = 13 \times 3.\]

Jadi pernyataan s(1) benar. Diasumsikan s(k) benar, yakni terdapat a \in \mathbb{Z} sedemikian hingga 100^k -61^k =13a.
Akan ditunjukkan s(k+1) benar. Diperoleh

    \begin{align*} 100^{k+1}-61^{k+1}=& 100 \times 100^k - 61 \times 61^k \\ =& 39 \times 100^k + 61 \times (100^k -61^k) \\ =& 13\times \left[ 3\times 100^k + 61 \times a \right]. \end{align*}

Jadi s(k+1) benar. Dengan induksi matematika, s(n) benar untuk setiap n \in \mathbb{Z}^+.

Tutorial: Soal Latihan dan Pembahasan Induksi Matematika