INDUKSI
MATEMATIKA
Success is no accident.
Its hars work,
preseverance, learning, studying, sacrifice and most of all,
Love of you are doing
or learning to do.
-
PELE
Dalam matematika
diskrit, induksi matematika digunaan sebagai pembukti yang baku dari suatu
pernyataan. Metode pembuktian ini digunakan untuk membuktikan pernyataan yang
bergantung pada bilangan bulat positif.
3.1
Definisi
Induksi matematika (Mathematical induction) merupakan metode
pembuktian yang sering digunakan untuk menentukan kebenaran dari suatu pernyataan
yang di berikan dalam bentuk bilangan asli. Induksi matematika dapat mengurangi
langkah-langkah pembuktian bahwa semua bilangan bulat termasuk kedalam suatu
himpunan kebenaran dengan hanya sejumlah langkah terbatas.
Contoh :
1.
Jumlah bilangan bulat positif dari 1
sampai n adalah 
Bukti
:
Misalkan n = 6 --> p(6) adalah “Jumlah
bilangan bulat positif dari 1 sampai 6 adalah "(6+1)/2
” terlihat bahwa :
1 + 2 + 3 + 4 + 5 + 6 = 21 --> 6(7)/2 = 21
Sehingga proposisi (pernyataan) tersebut benar.
2.
Jumlah n buah bilangan ganjil positif pertama adalah n2
Bukti
:
Misalkan n = 6buah (n = 1,2,3,4,5,6)
maka :
¤ n
= 1 à 1 = 1 à (1)2 = 1
¤ n
= 2 à 1 + 3 = 3 à (2)2 = 4
¤ n
= 3 à 1 + 3 + 5 = 9 à (3)2
=
9
¤ n
= 4 à 1 + 3 + 5 + 7 =
16 à (4)2 = 16
¤ n
= 5 à 1 + 3 + 5 + 7 +
9 = 25 à (5)2 = 25
¤ n
= 6 à 1 + 3 + 5 + 7 +
9 + 11 = 36 à (6)2 = 36
Sehingga
proposisi (pernyataan) tersebut benar.
3.2
Prinsip Induksi Matematika
Induksi matematika (Mathematical induction) merupakan metode
pembuktian yang sering digunakan untuk menentukan kebenaran dari suatu
pernyataan yang diberikan dalam bentuk bilangan asli.
1.
Prinsip Induksi Sederhana
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 :
a.
Tunjukkan bahwa untuk n ≥ 1, 1 + 2 + 3 +
... + 4 = n(n+1)/2 melalui induksi matematika.
ü Basis
Induksi
P(1) benar --> n = 1 diperoleh dari :
1
= 1(1+1)/2
= 1(2)/2
= 2/2
= 1
ü Langkah
Induksi
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)C
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
b.
Gunakan induksi matematika untuk membuktikan
bahwa jumlah n buah bilangan ganjil positif pertama adalah n2.
ü Basis
Induksi
P(1)
benar --> jumlah 1 buah
bilangan ganjil positif pertama adalah 12 = 1
ü Langkah
Indusi
Misalkan
p(n) benar à asumsi bahwa :
1+3+5+...+(2n-1) = n2
Adalah
benar (hipotesis induksi)
Perlihatkan
bahwa p(n+1) juga benar, yaitu :
1+3+5+...+(2n-1)+(2n+1) = (n+1)2
Hal
ini dapat ditunjukkan sebagai berikut :
1+3+5+...+(2n-1)+(2n+1) = [1+3+5+...+(2n-1)]+(2n+1)
=
n2 + (2n+1)
=
n2 + 2n+1
=
(n+1)2
Langkah
(i) dan (ii) dibuktikan benar, maka
untuk jumlah n buah bilangan
ganjil positif pertama adalah n2.
2.
Prinsip Induksi yang Dirampatkan (Generalized)
Misalkan p(n) adalah
pernyataan perihal bilangan bulat n ≥ n0. Untuk membuktikannya perlu
menunjukkan bahwa :
1)
p(n0) benar
2)
Jika p(n) benar, maka p(n+1) juga benar
untuk setiap n ≥ n0
Sehingga
p(n) benar untuk semua bilangan n ≥ n0.
Contoh :
a.
Untuk semua bilangan bulat tidak negatif
n, buktikan dengan induksi matematika
bahwa 20+ 21+
22+…+ 2n= 2n+1 -1.
Misalkan p(n) adalah proposisi bahwa
untuk semua bilangan bulat tidak negatig n,
20+ 21+
22+…+ 2n= 2n+1 -1.
ü Basis
Induksi
p(0) benar à untuk n = 0 (bilangan bulat tidak negatif pertama)
diperoleh dari :
20 = 1 = 20+1 -1
= 21 -1
= 2 – 1
= 1
ü Langkah
Induksi
Misalkan
p(n) benar, yaitu proposisi :
20+
21+ 22+…+ 2n= 2n+1 -1
Diasumsikan
benar (hipotesis induksi). Perlihatkan bahwa p(n+1) juga benar, yaitu :
20+ 21+ 22+…+
2n+ 2n+1 = 2(n+1)+1 -1
Hal ini
dapat ditunjukkan sebagai berikut :
20+ 21+ 22+…+
2n+ 2n+1 = (20+ 21+ 22+…+
2n) + 2(n+1)
= 2(n+1)+1 -1 + 2n+1 (dari hipotesis induksi)
= (2n+1 + 2n+1)
– 1
= (2 . 2n+1) – 1
= 2n+2 – 1
= 2(n+1)+1 -1
Langkah (i)
dan (ii) dibuktikan benar, maka untuk semua bilangan bulat tidak negatif n,
terbukti bahwa 20+ 21+ 22+…+ 2n= 2n+1
-1.
b.
Buktikan dengan induksi matematika bahwa
3n < n! untuk
n bilangan bulat positif yang lebih besar dari 6
Misalkan
p(n) adalah proposisi bahwa 3n < n! untuk n bilangan bulat
positif yang lebih besar dari 6
ü Basis
Induksi
p(7) benar --> 37 < 7! « 2187 < 5040
ü Langkah
Induksi
Misalkan
bahwa p(n) benar, yaitu asumsikan bahwa 3n < n! adalah benar.
Perlihatkan juga bahwa p(n+1) juga benar, yaitu 3n+1 < (n+1)!
Hal ini
dapat ditunjukkan sbb :
3n+1 < (n+1)!
3
. 3n < (n+1) . n!
3n
. 3 / (n+1) < n!
Menurut
hipotesis induksi, 3n < n!, sedangkan untuk n > 6, nilai
3/(n+1) < 1, sehingga 3/(n+1) akan memperkecil nilai di ruas kiri persamaan.
Efek nettonya, 3n . 3/(n+1) < n! jelas benar
Langkah (i)
dan (ii) dibuktikan benar, maka terbukti bahwa 3n < n! untuk n
bilangan bulat positif lebih besar dari 6
Tidak ada komentar:
Posting Komentar