Induksi matematika adalah metode
pembuktian untuk proposisi perihal bilangan bulat. Induksi matematika merupakan teknik pembuktian yang baku didalam matematika. Induksi metamtika dapat mengurangi lagkah-langkah pembuktian bahwa semua bilangan bulat termasuk kedalma suatu himpunan kebenaran dengan hanya sejumlah langkah terbatas.
Contoh:
Jumlah
bilangan bulat positif dari 1 sampai n adalah n(n+1)/2
Bukti
:
Misalkan
n = 6 à p(6) adalah “Jumlah bilangan bulat
positif dari 1 sampai 6 adalah 6(6+1)/2” terlihat bahwa :
1 + 2 + 3 + 4 + 5 + 6 = 21 è 6(7)/2 = 21
Sehingga
proposisi (pernyataan) tersebut benar
Contoh:
Jumlah
n buah
bilangan ganjil positif pertama adalah n2.
Bukti:
Misalkan
n = 6 buah (n = 1,2,3,4,5,6) maka :
nn
= 1 à 1 =
1 è (1)2 = 1
nn
= 2 à 1+3
= 4 è (2)2 = 4
nn
= 3 à
1+3+5 = 9 è (3)2 = 9
nn
= 4 à
1+3+5+7 = 16 è (4)2 = 16
nn
= 5 à
1+3+5+7+9 = 25 è (5)2 = 25
nn
= 6 à
1+3+5+7+9+11 = 36 è (6)2 = 36
Sehingga
proposisi (pernyataan) tersebut benar
PRINSIP INDUKSI SEDERHANA
Misalkan
p(n) adalah proposisi bilangan bulat positif dan ingin dibuktikan bahwa p(n)
adalah benar untuk semua bilangan bulat positif n. Maka langkah-langkahnya adalah sebagai
berikut :
- p(n) benar
- Jika p(n) benar, maka p(n+1) juga
benar untuk setiap n ³
1
Sehingga p(n) benar untuk semua bilangan bulat positif n
Basis Induksi:
- Digunakan
untuk memperlihatkan bahwa pernyataan benar bila n
diganti dengan 1, yang merupakan bilangan bulat positif terkecil
- Buat
implikasi untuk fungsi berikutnya benar untuk setiap bilangan bulat positif \
Langkah Induksi:
- Berisi
asumsi (andaian) yang menyatakan bahwa p(n) benar.
- Asumsi
tersebut dinamakan hipotesis induksi.
Bila
kedua langkah tersebut benar maka pembuktian bahwa p(n) benar untuk semua bilangan positif n.
CONTOH:
Tunjukkan
bahwa untuk n ³
1,
1+2+3+…+n = n(n+1)/2 melalui induksi matematika
p(1)
benar ➜ n =
1 diperoleh dari :
1 = 1(1+1)/2
= 1(2)/2
= 2/2
=1
Misalkan
p(n) benar à
asumsi bahwa :
1+2+3+…+n = n(n+1)/2
Adalah
benar (hipotesis induksi). Perlihatkan bahwa p(n+1) juga benar yaitu
1+2+3+…+n+(n+1) = (n+1)[(n+1)+1]/2
1+2+3+…+n+(n+1)
= (1+2+3+…+n)+(n+1)
= [n(n+1)/2]+(n+1)
= [(n2+n)/2]+(n+1)
= [(n2+n)/2]+[(2n+2)/2]
= (n2+3n+2)/2
= (n+1)(n+2)/2
= (n+1)[(n+1)+1]/2
Langkah (i) dan (ii) dibuktikan benar, maka
untuk semua bilangan bulat positif n, terbukti bahwa untuk semua n ³
1,
1+2+3+…+n = n(n+1)/2