Lanjut postingan mengenai induksi matematika. Secara formal Induksi Matematika ini bisa dide nisikan sebagai berikut.

Misalkan untuk setiap bilangan asli n kita mempunyai pernyataan P(n) yang bisa benar atau salah. Misalkan:

  1. P(1) benar.
  2. Jika P(n) benar, maka P(n+1) benar.

Sehingga P(n) benar untuk setiap bilangan asli n. Langkah 1 disebut dengan Langkah Dasar, sedangkan Langkah 2 disebut dengan Langkah Induktif. Jika pada Langkah Induktif yang diasumsikan adalah pernyataan P(i) benar untuk setiap bilangan i\leq n, maka perumusan induksi matematika seperti ini disebut Bentuk Kuat Induksi Matematika.

Contoh Soal :

Gunakan induksi matematika untuk membuktikan bahwa n!\geq 2^{n-1}, untuk setiap n=1,2,3,.......

Jawaban :

Akan di tunjukkan bahwa n!\geq 2^{n-1} benar untuk n = 1. Jelas sekali bahwa 1!=1\geq 1=2^0=2^{1-1}.

Asumsikan Bahwa n!\geq 2^{n-1} adalah benar untuk n=k. Akan ditunjukkan bahwa n!\geq 2^{n-1} juga benar untuk n=k+1, yaitu (k+1) \geq 2^{(k+1)-1}.

(k+1)!=(k+1)k!

(k+1)k! \geq (k+1) 2^{k-1}

(k+1)k! \geq 2.2^{(k-1)}

(k+1)k! \geq 2^{(k-1)+1}

Terbukti bahwa (k+1)k! \geq 2^{(k-1)+1}.  Karena Langkah Dasar dan Langkah Induktif terbukti, maka dapat disimpulkan bahwa n!\geq 2^{n-1}, untuk setiap n=1,2,3.....