Prinsip Induksi Sederhana

Prinsip Induksi Sederhana adalah cara untuk

menyatakan suatu pernyataan yang akan dibuktikan bahwa pernyataan tersebut benar.

Misal p(n) menyatakan suatu pernyataan   bilangan   bulat   positip dan akan dibuktikan bahwa pernyataan p(n) tersebut benar untuk  semua bilangan  positip n  maka untuk membuktikan  pernyataan ini  digunakan  aturan  sbb:

Langkah 1 :  p(1) benar  dan

Langkah 2 : Untuk semua  bilangan  bulat  positi f n ≥ 1, jika  p(n) benar  maka p(n + 1) juga  benar.

Dimana langkah 1. disebut   dengan   basis induksi   dan   langkah 2   disebut   langkah induksi dengan p(n)  disebut  hipotesis  induksi.

Contoh  1.

Buktikan  bahwa  1+ 2 + 3 + … + n = n(n+1)/2  untuk setiap n  bilangan bulat positip

Bukti :

Langkah  1,

Akan diperlihatkan pernyataan benar untuk  n = 1, untuk  n = 1 maka 1 = 1(1+1)/2.

Langkah Induksi

Akan  ditunjukkan  pernyataan  benar  untuk  setiap  bilangan  bulat  n,    n  ≥  1,  apabila pernyataan benar untuk n = k  maka pernyataan benar untuk n = k + 1.

Jika diasumsikan  pernyataan  1 + 2 + 3+ … + n = n(n+1) /2  benar

maka

1 + 2 + 3 + … + n + (n+1)= (1 + 2 + 3 + … + n) +(n+1)

= n(n+1) /2  +  (n+1)

= n(n+1)+ 2(n+1)

=  n(n + 1) + 2(n + 1)

2

= (n+1)(n+2)/2

= (n+1)((n+1)+1)/2

Karena kedua langkah induksi telah terpenuhi maka   untuk setiap bilangan positip n berlaku  bahwa :   1 + 2 + 3 + … +  n = n(n+1)/2    .

Contoh 2.

Buktikan  bahwa banyak n buah bilangan bulat  positif ganjil pertama  adalah  n2

Bukti  :

Misalkan p(n)  merupakan pernyataan  yang  menyatakan  bahwa  jumlah  n  buah bilangan bulat  positif  ganjil  pertama  adalah  n2, maka :

Langkah  1,

Untuk  n = 1 maka  12 = 1 maka  p(1)  benar , karena banyak  buah bilangan ganjil positif pertama  adalah  n2

Langkah Induksi

Untuk n = n

Andaikan  untuk  n ≥ 1 pernyataan  1 + 3 + 5… + (2n-1) = n2     benar

maka  akan ditunjukkan  bahwa  1+ 3 + … + (2n-1) + (2n+1) = (n+1)2  yaitu

1 + 3 + … + (2n-1)+ (2n+1) =  {(1+2+3+ … +n)}+(2n+1)

=  n2 +  (2n+1)

=   n2  +  2n + 1

= (n+1)2