Contoh

$1+2+3+\ldots+n=\frac{n\left(n+1\right)}{2}$

Untuk $n=1$ maka $1=\frac{1\left(1+1\right)}{2}$
Untuk $n=2$ maka $1+2=\frac{2\left(2+1\right)}{2}=3$
Untuk $n=3$ maka $1+2+3=\frac{3\left(3+1\right)}{2}=6$
Untuk $n=4$ maka $1+2+3+4=\frac{4\left(4+1\right)}{2}=10$

Pertanyaannya adalah

Bagaimana membuktikan bahwa rumus diatas berlaku untuk semua $n\in\mathbb{N}$ ?

Tentu saja kita tidak mungkin mengecek satu-persatu bilangan asli. Untuk membuktikannnya kita harus menggunakan induksi matematika

Induksi Matematika

Merupakan metode pembuktian untuk membuktikan pernyataan berbentuk

$P\left(n\right)$ : Untuk suatu bilangan asli $n$ berlaku $P$

bahwa $P\left(n\right)$ berlaku untuk semua $n\in\mathbb{N}$ .

Langkah-langkah pada Induksi Matematika

Ada 2 langkah pada Induksi matematika untuk memebuktikan pernyataan $P\left(n\right)$ berlaku untuk semua $n\in\mathbb{N}$ .

Langkah pertama disebut Langkah dasar. Buktikan untuk $n=1$ berlaku $P\left(1\right)$
Langkah kedua disebut Langkah Induksi. Asumsi berlaku untuk $n=k$ berlaku $P\left(k\right)$ , buktikan untuk $n=k+1$ berlaku $P\left(k+1\right)$ .

Contoh

1. Kita buktikan rumus diatas $1+2+3+\ldots+n=\frac{n\left(n+1\right)}{2}$

Langkah dasar: Untuk $n=1$ berlaku

$1=\frac{1\left(1+1\right)}{2}$

Terbukti untuk $n=1$ , selanjutnya

Langkah Induksi: Asumsi untuk $n=k$ berlaku $1+2+3+\ldots+k=\frac{k\left(k+1\right)}{2}$ .

Akan dibuktikan untuk $n=k+1$ berlaku

$1+2+3+\ldots+k+\left(k+1\right)=\frac{k+1\left(\left(k+1\right)+1\right)}{2}$

Inilah yang akan kita buktikan. Berdasarkan asumsi $n=k$ maka sisi kiri dapat ditulis

$\frac{k\left(k+1\right)}{2}+\left(k+1\right)$

Jabarkan:

$\frac{k\left(k+1\right)}{2}+\left(k+1\right)=\frac{k\left(k+1\right)+2\left(k+1\right)}{2}$

$=\frac{k^{2}+3k+2}{2}$

$=\frac{\left(k+1\right)\left(k+2\right)}{2}$

$=\frac{\left(k+1\right)\left(\left(k+1\right)+1\right)}{2}$

Terbukti untuk $n=k+1$ , langkah induksi telah lengkap maka bisa kita simpulkan

$1+2+3+\ldots+n=\frac{n\left(n+1\right)}{2}$

berlaku untuk semua $n\in\mathbb{N}$

2. Buktikan $5^n-1$ habis dibagi 4 untuk setiap bilangan asli $n$

Langkah dasar: Untuk $n=1$ , jelas $5^1-1$ habis dibagi 4

Langkah Induksi: Asumsi untuk $n=k$ berlaku $5^k-1$ habis dibagi 4. Akan dibuktikan $5^{k+1}-1$ habis dibagi 4

$5^{k+1}-1=5.5^k-1$

$=(1+4).5^k-1$

$=5^k+4.5^k-1$

$=(5^k-1)+4.5^k$

berdasarkan asumsi $5^k-1$ habis dibagi 4, begitupula $4.5k$ habis dibagi 4, itu berarti $5^{k+1}-1$ habis dibagi 4.

Langkah induksi telah lengkap maka bisa kita simpulkan $5^n-1$ habis dibagi 4 untuk setiap bilangan asli $n$

3. Buktikan $n!>3^n$ untuk semua $n\geq7$

Untuk contoh ke-3 saya akan menunjukan langkah dasar tidak harus selalu dimulai dari $n=1$ tapi tergantung kondisi. Pada contoh ini langkah dasar dimulai dari $n=7$ , kenapa? Karena persamaan diatas tidak berlaku untuk $n<7$