Prinsip – Prinsip Dalam Induksi Matematika

Selamat datang di tempat belajar matematika online, Disini kami menyediakan materi pembelajaran matematika yang sedang teman teman cari lengkap dengan pembahasan contoh soal,Seperti artikal yang kami buat kali ini yaitu tentang ,.,,, yang kami susun secara lengkap dan juga jelas agar dapat membantu menyelesaikan masalah matematika yang sedang teman – teman hadapi. materi ini di berikann untuk jenjang pendidikan SMA Kelas 12 . Tidak perlu begitu banyak berbasa basi mari kita simak Prinsip – Prinsip Dalam Induksi Matematika selengkapnya di bawah ini.

images-26 Prinsip - Prinsip Dalam Induksi Matematika

Induksi matematika adalah : Metode pembuktian untuk proposisi perihal bilangan bulat, induksi matematika merupakan

teknik pembuktian yang baku di dalam matematika, induksi matematika dapat mengurangi langkah-langkah pembuktian bahwa semua bilangan bulat termasuk ke dalam 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
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
1.      p(n) benar
2.
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
F Digunakan untuk memperlihatkan bahwa pernyataan benar
bila n diganti dengan 1, yang merupakan bilangan bulat positif terkecil
F Buat implikasi untuk fungsi berikutnya benar untuk
setiap bilangan bulat positif
Langkah induksi
F Berisi asumsi (andaian) yang menyatakan bahwa p(n)
benar.
F Asumsi tersebut dinamakan hipotesis induksi.
Bila kedua langkah tersebut benar maka pembuktian bahwa p(n) benar untuk semua bilangan positif n.
Contoh :
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 induksi
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.
Prinsip Induksi yang Dirampatkan
 
Prinsip induksi sederhana dapat 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 bulat n
³ n0
Contoh soal
Buktikan dengan induksi matematika bahwa 3n
< n! untuk n bilangan bulat positif yang lebih besar dari 6
Jawab :
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
.
Prinsip Induksi Kuat
 
Prinsip induksi yang lebih kuat adalah sbb :
1.
p(n0)
benar
2.
Jika
p(n0), p(n0+1), …, p(n) benar, maka p(n+1) juga benar
untuk setiap n
³ n0
            sehingga
p(n) benar untuk semua bilangan bulat n
³ n0
Versi induksi yang lebih kuat mirip dengan induksi
sederhana, perbedaannya adalah pada langkah (ii) :
F hipotesis induksi yang lebih kuat
bahwa semua pernyataan p(1), p(2), …, p(n) adalah
benar
F Hipotesis induksi sederhana
bahwa p(n) benar
Prinsip induksi kuat memungkinkan kita mencapai
kesimpulan yang sama meskipun memberlakukan andaian yang lebih banyak
.
Contoh soal :
Bilangan bulat positif disebut prima jika dan hanya
jika bilangan bulat tersebut habis dibagi dengan 1 dan dirinya sendiri.
Buktikan dengan induksi matematika (prinsip induksi kuat) bahwa setiap bilangan
bulat positif n(n
³ 2)
dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima
.
Jawab :
Misalkan p(n) adalah proposisi setiap bilangan bulat
positif n(n
³ 2)
dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima
Basis induksi
p(2) benar à 2 sendiri adalah bilangan prima dan 2 dinyatakan sebagai
perkalian dari satu buah bilangan prima, yaitu dirinya sendiri
Langkah induksi
Misalkan p(n) benar, asumsikan bahwa bilangan 2, 3, …,
n dapat dinyatakan sebagai perkalian (satu atau lebih) bilangan prima
(hipotesis induksi). Perlihatkan juga bahwa p(n+1) benar, yaitu n + 1
juga dapat dinyatakan sebagai perkalian bilangan prima.
Hal ini dapat ditunjukkan sbb :
Jika n + 1 bilangan prima à perkalian satu atau lebih bilangan prima
Jika n + 1 bukan bilangan prima à terdapaat bilangan bulat positif a yang membagi habis
n + 1 tanpa sisa
                                    (n+1)/a
= b atau (n+1) = ab
            dimana
2
£ a £ b £ n.
Menurut hipotesis induksi, a dan b dapat dinyatakan
sebagai perkalian satu atau lebih bilangan prima.
Ini berarti bahwa n+1 jelas dapat dinyatakan sebagai
perkalian bilangan prima, karena n+1 = ab
Langkah (i) dan (ii) dibuktikan benar, maka terbukti
bahwa setiap bilangan bulat positif n(n
³ 2)
dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima
.
Bentuk Induksi Secara Umum
 
Membuat bentuk umum metode induksi sehingga dapat
diterapkan tidak hanya untuk pembuktian proposisi yang menyangkut himpunan
bilangan bulat positif tetapi juga pembuktian yang menyangkut himpunan obyek
yang lebih umum.
Syaratnya himpunan obyek tersebut harus mempunyai :
1.
Keterurutan
2.
Elemen
terkecil
Relasi biner “<“ pada himpunan X dikatakan terurut
dengan baik (atau himpunan X dikatakan terurut dengan baik dengan “<“) bila
memiliki properti berikut :
3.
Diberikan
x, y, z
Î X, jika x < y dan y < z maka x < z
4.
Diberikan
x, y
Î X. Salah satu dari kemungkinan ini benar : x < y
atau y < x atau x = y
5.
Jika
A adalah himpunan bagian tidak kosong dari X, terdapat elemen x
Î A sedemikian sehingga x £ y untuk semua y Î A. Dengan kata lain, setiap himpunan bagian tidak
kosong dari X mengandung “elemen terkecil”
Misalkan X terurut baik oleh “<“ dan p(x) adalah
pernyataan perihal elemen x dari X. Pembuktian bahwa p(x) benar untuk semua x
Î X. Untuk pembuktiannya hanya perlu menunjukkan bahwa
:
p(x0) benar, yang dalam hal ini x0 adalah
elemen terkecil di
dalam X
Jika p(y) benar untuk y < x, maka p(x) juga benar
untuk setiap x > x0 di dalam X

Sehingga p(x) benar untuk
semua x
Î X
Soal :
Tinjau barisan bilangan yang didefinisikan sbb :
                               0               jika
m = 0 dan n = 0
Sm,n =
Sm-1, n + 1     jika n =
0
                          Sm, n-1 + 1       jika n ¹ 0
 Sebagai
contoh :
S0,0 = 0                       
S1,0 = S0,0 + 1 = 0 + 1 = 1
S0,1 = S0,0 + 1 = 1        S1,1 = S1,0 + 1 =
1 + 1 = 2
S2,0 = S1,0 + 1 = 2        S2,1 = S2,0 + 1 =
2 + 1 = 3,…
Buktikan dengan induksi matematik bahwa untuk pasangan
tidak negatif m dan n, Sm,n = m+n
Jawab  :
Basis induksi
(0,0) elemen terkecil di dalam X, maka Sm,n
= 0 + 0 = 0
Langkah induksi
Buktikan semua (m,n) > (0,0) di dalam X bahwa jika
Sm’,n’ = m’ + n’ benar untuk semua (m’,n’) < (m,n) maka Sm,n
= m+n juga benar.
Andaikan bahwa Sm’,n’ = m’ + n’ benar untuk
semua (m’,n’)
à hipotesis induksi
Tunjukkan juga bahwa Sm,n =m + n baik untuk
n = 0 atau n
¹ 0.
Kasus 1 :
Jika n = 0 maka dari definisi Sm,n = Sm-1,n
+1
Karena (m-1, n) < (m, n) maka dari hipotesis induksi
             Sm-1,n = (m-1) + n sehingga Sm,n
= Sm-1,n +1 = (m-1)+n+1=m+n
Kasus 2 :
Jika n ¹ 0 maka dari definisi Sm,n = Sm,n-1
+1
Karena (m, n-1) < (m, n) maka dari hipotesis
induksi
             Sm,n-1 = m + (n-1) sehingga Sm,n
= Sm,n-1 +1 = m+(n-1)+1=m+n
Langkah (i) dan (ii) sudah dibuktikan benar, maka
terbukti bahwa untuk pasangan tidak negatif m dan n, Sm,n
= m+n
Tags: