METODE DAN PEMBUKTIAN induksi matematika.pptx

metode, prinsip induksi matematika

1. Lasro Sampang Marulitua Sihotang (4202411007) Bertha Marlini Saragih (4202411015) Novieta Putri Purba (4203111036) Putri Handayany Purba (4203111056) Yohana Agesty Ginting (4203111124) METODE PEMBUKTAN By : Kelompok 8

2. 02 PRINSIP INDUKSI MATEMATIKA TEORI BINOMIAL 01

3. INDUKSI MATEMATIKA   Induksi Matematika merupakan suatu teknik yang dikembangkan untuk membuktikan pernyataan . Pernyataan yang dimaksudkan dibatasi hanya pada pernyataan yang menyangkut bilangan bulat . Induksi Matematika digunakan untuk mengecek hasil proses yang terjadi secara berulang sesuai dengan pola tertentu . Induksi Matematika digunakan untuk membuktikan pernyataan yang khusus menyangkut bilangan bulat positif. Dengan menggunakan Induksi Matematika akan mengurangi pembuktian bahwa semua bilangan bulat positif termasuk ke dalam suatu himpunan kebenaran dengan jumlah langkah terbatas . PRINSIP INDUKSI MATEMATIKA

4. MATERI INDUKSI MATEMATIKA Pernyataan perihal bilangan bulat Prinsip induksi sederhana Prinsip induksi yang dirampatan Prinsip induksi kuat Prinsip induksi secara umum 1. Pernyataan perihal bilangan bulat Pernyatan perihal bilangan bulat mengkaitkan suatu masalah yang dihubungkan dengan bilangan bulat. Untuk memberikan ilustrasi mengenai pernyataan yang dimaksud,diperlihatkan dengan memberikan contoh berikut:   CONTOH 1 : Misalkan p(n) adalah pernyataan yang menyatakan :”Jumlah bilangan bulat positip dari 1 sampai n adalah n(n+1)/2” Buktikan bahwa p(n) benar. Jika dicoba dengan beberapa nilai n,memang timbul dugaan bahwa p(n) benar,misalnya untuk n=5 P(5) adalah :”jumlah bilangan bulat positip dari 1 sampai 5 adalah 5(5+1)/2.Terlihat bahwa: 1+2+3+4+5=5(5+1)/2 15=15 (TERBUKTI)

5. 2. prinsip induksi sederhana Misalkan p ( n ) adalah pernyataan perihal bilangan bulat positif . Kita ingin membuktikan bahwa p ( n ) benar untuk semua bilangan bulat positif n . Untuk membuktikan pernyataan ini , kita hanya perlu menunjukkan bahwa :   p (1) benar , dan jika p ( n ) benar , maka p ( n + 1) juga benar , untuk setiap , Langkah 1 dinamakan basis induksi , sedangkan langkah 2 dinamakan langkah induksi . Langkah induksi berisi asumsi ( andaian ) yang menyatakan bahwa p ( n ) benar . Asumsi tersebut dinamakan hipotesis induksi . Bila kita sudah menunjukkan kedua langkah tersebut benar maka kita sudah membuktikan bahwa p ( n ) benar untuk semua bilangan bulat positif n .  

6. Contoh 1 : Tunjukkan bahwa n ≥ 1, 1 + 2 + 3 + … + n = n(n+1)/2 melalui induksi matematika Jawab : Langkah 1 : Untuk n = 1 1 = 1 (1+1)/2 1 = 1 (2)/2 1 = 2/2 1 = 1 (Terbukti ) Maka ; 1 = 1(1+1)/2 adalah benar . Langkah 2 : Misalkan untuk n ≥ 1 1 + 2 + 3 + … + n = n (n + 1) /2 1 + 2 + 3 + … + n + (n +1) = (n +1) ((n + 1) + 1)/ 2 (1 + 2 + 3 + … + n) + (n +1) = (n +1) ((n + 1) + 1)/ 2 ( n(n+1)/2) ) + (n+1) = (n +1) ((n + 1) + 1)/ 2 ( (n 2 + n)/2 ) + (2n+2)/2 = (n +1) ((n + 1) + 1)/ 2 (n 2 + 3n + 2)/2 = (n +1) ((n + 1) + 1)/ 2 (n+1)(n+2)/2 = (n +1) ((n + 1) + 1)/ 2 (n+1) ((n+1) + 1) / 2 = (n +1) ((n + 1) + 1)/ 2 (Terbukti) Karena langkah 1 dan langkah 2 keduanya telah dibuktikan benar , maka untuk semua bilangan bulat positif n, TERBUKTI bahwa 1 + 2 + 3 + … + n = n (n + 1) /2

7. 3 . Prinsip Induksi yang Dirampatkan Misalkan p ( n ) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p ( n ) benar untuk semua bilangan bulat n  n . Untuk membuktikan ini , kita hanya perlu menunjukkan bahwa : p ( n ) benar , dan jika p ( n ) benar maka p ( n +1) juga benar,untuk semua bilangan bulat n  n ( ) contoh: untuk semua bilangan bulat tidak negatif n,buktikan dengan induksi matematik bahwa 2 +2 1 +2 2 +........+2 n =2 n+1 -1 penyelesaian : Basis induksi . U ntuk n=0(bilangan bulat negatif pertama) kita peroleh 2 =2 0+1 -1 Ini jelas benar,sebab 2 = 1 = 2 0+1 -1 1 =2 1 -1 1=2-1 =1 ( Terbukti)     Langkah induksi . Andaikan bahwa p(n) benar,yaitu 2 +2 1 +2 2 +.........+2 n =2 n+1 -1 Adalah benar (hipotesis induksi).Kita harus menunjukkan bahwa P(n+1) juga benar,yaitu 2 +2 1 +2 2 +.......+2 n +2 n+1 =2 (n+1)+1 -1 (2 +2 1 +2 2 +.......+2 n )+2 n+1 =2 (n+1)+1 -1 (2 n+1 -1)+ 2 n+1 =2 (n+1)+1 -1 (2 n+1 +2 n+1 )-1=2 (n+1)+1 -1 (2. 2 n+2 )-1=2 (n+1)+1 -1 2 n+2 -1=2 (n+1)+1 -1 2 (n+1)+1 -1=2 (n+1)+1 -1 (Terbukti ) Karena langkah (i) dan (ii) keduanya telah diperhatikan benar,maka untuk semua bilangan bulat positif n,terbukti bahwa 2 +2 1 +2 2 +........+2 n =2 n+1 -1

8. 4. Prinsip Induksi kuat Kadang-kadang versi induksi yang lebih kuat diperlukan untuk membuktikan pernyataan mengenai bilangan bulat . Versi induksi yang lebih kuat adalah sebagai berikut : Misalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n > n0. Untuk membuktikan ini , kita hanya perlu menunjukkan bahwa benar , dan Jika maka juga benar untuk setiap bilangan bulat n>n   Sehingga p(n) benar untuk setiap bilangan bulat n>n   Catatlah bahwa versi induksi yang lebih kuat ini mirip dengan induksi sederhana , kecuali bahwa pada langkah 2 kita mengambil hipotesis induksi yang lebih kuat bahwa semua pernyataan p ( 1),p(2), ...,p(n) adalah benar daripada hipotesis yang menyatakan bahwa p(n) benar ( pada induksi sederhana ). Prinsip induksi kuat memungkinkan kita mencapai kesimpulan yang sama meskipun memberlakukan andaian yang lebih banyak .  

9. Contoh : Bilangan bulat positif disebut prima jika dan hanya jika bilangan bulat tersebut habis dibagi dengan 1 dan dirinya sendiri . Kita ingin membuktikan bahwa setiap bilangan bulat positif n (n > 2) dapat dinyatakan sebagai perkalian dari ( satu atau lebih ) bilangan prima. Buktikan dengan prinsip induksi kuat .   Penyelesaian : Misalkan p( ri ) adalah proposisi bahwa setiap bilangan bulat positif n ( zi > 2) dapat dinyatakan sebagai perkalian dari ( satu atau lebih ) bilangan prima. Basis induksi : p(2) benar , karena 2 sendiri adalah bilangan prima dan di sini 2 dapat dinyatakan sebagai perkalian dari satu buah bilangan prima, yaitu dirinya sendiri . Langkah induksi . Misalkanp {n) benar , yaitu asumsikan bahwa bilangan 2, 3, ..., n dapat dinyatakan sebagai perkalian ( satu atau lebih ) bilangan prima ( hipotesis induksi ). Kita perlu menunjukkan bahwa p{n + 1) benar , yaitu n + 1 juga dapat dinyatakan sebagai perkalian bilangan prima. Hal ini ditunjukkan sebagai berikut : jika Ti+l sendiri bilangan prima, maka jelas ia dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima. Jika 77 + 1 bukan bilangan prima, maka terdapat bilangan bulat positif a yang membagi habis 77 + 1 tanpa sisa . Dengan kata lain, (77 + 1)/ a = b atau (77 + 1) = ab yang dalam hal ini , 2 < a < b < n. Menurut hipotesis induksi , a dan b dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima. Ini berarti , 77 + 1 jelas dapat dinyatakan sebagai perkalian bilangan prima, karena n + 1 = ab. Karena langkah ( i ) dan (ii) sudah ditunjukkan benar , maka terbukti bahwa setiap bilangan bulat positif 77 (77 > 2) dapat dinyatakan sebagai perkalian dari ( satu atau lebih ) bilangan prima.   Catatlah bahwa pernyataan di atas lebih tepat dibuktikan dengan prinsip induksi kuat daripada dengan prinsip induksi sederhana . Kita tahu bahwa a dan b keduanya < n, karena itu , untuk dapat menerapkan hipotesis induksi terhadap keduanya , kita perlu mengetahui bahwa tiap bilangan bulat positif 2, 3, n dapat dinyatakan sebagai perkalian bilangan prima. Mengandaikan bahwa « dapat dinyatakan sebagai perkalian bilangan prima saja tidaklah cukup

10. 5 . Prinsip induksi secara umum Adalah mungkin membuat bentuk umum metode induksi sehingga ia 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 keterurutan dan mempunyai elemen terkecil . Relasi biner "<" pada himpunan A'dikatakan terumt dengan baik ( atau himpunan X dikatakan tenirut dengan baik dengan "<") bila memiliki properti berikut : Diberikan x, y, z G A', jika x <y dan y < 2, maka x< z. Diberikan x, y e A'. Salah satu dari kemungkinan ini benar : x < y atau y < x atau x =y, Jika A adalah himpunan bagian tidak kosong dari X, terdapat elemen x e A sedemikian sehingga x < y untuk semua y e A. Dengan kata lain, setiap himpunan bagian tidak kosong dari X mengandung " elemen terkecil ".   Himpunan bilangan riil tak-negatif tidak terurut dengan baik oleh relasi "<". Himpunan ini mempunyai properti ( i ) dan (ii) tetapi tidak (iii). Sebagai contoh , himpunan semua bilangan riil yang lebih besar dari 1, yaitu j x | x adalah bilangan riil danx > 1 j, tidak mengandung elemen terkecil . Himpunan pasangan terurut bilangan bulat tidak negatif terurut dengan baik oleh relasi dengan kata lain "<" didefinisikan oleh ( zz ,, zz2) («3 < "4) jika dan hanya jika ( zzt < zz3) atau ( zz , = zz3 dan ih < z,4). Properti ( i ), (ii), dan (iii) dimiliki oleh himpunan ini . Bentuk induksi secara umum dapat dituliskan sebagai berikut : Misalkan X terurut dengan baik oleh dan p(x) adalah pernyataan perihal elemen x dari X. Kita ingin membuktikan bahwa p(x) benar untuk semua x e X. Untuk membuktikan ini , kita hanya perlu menunjukkan bahwa ; p(xo) benar , yang dalam hal ini Xo adalah elemen terkecil di dalam X, dan 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 e X.

11. contoh Tinjau barisan bilangan yang didefinisikan sebagai berikut : ={ jika m=0 dan n=0 Buktikanlah dengan induksi matematik bahwa untuk pasangan tidak negatif m dan n, Sm,„ = m + n. Penyelesaian Basis induksi : Karena (0, 0) adalah elemen terkecil di dalam X, maka SQ,O = 0 + 0 = 0. Ini benar dari definisi 6o. Langkah induksi . Buktikan untuk semua ( tn , n) > (0, 0) di dalam X bahwa jika = m' + n' benar untuk semua (m', n') < (m, n) maka S„r „ = m + n juga benar . Andaikan bahwa S„-t = m’ + n’ benar untuk semua (m’, «’) < (m,«). Ini adalah hipotesis induksi . Kita perlu menunjukkan bahwa 5W4r = m + n, baik untuk n = 0 atau n*0 . Kasus 1: Jika n = 0, maka dari definisi + 1, Karena (m-1, n) < (m, n), maka dari-hipotesis induksi ,   Kasus 2: Jika n * 0, maka dari definisi + 1. Karena (m, n-1) < (m, «), maka dari hipotesis induksi , Karena langkah basis dan ( induktif sudah diperlihatkan benar , maka terbukti bahwa untuk pasangan tidak negatif m dan n m,n = tn + n.  

12. TEORI BINOMIAL Di aljabar, penjumlahan dua suku, seperti  a  +  b , disebut  binomial Teorema binomial  memberikan bentuk ekspansi dari pangkat binomial ( a  +  b ) n , untuk setiap  n  bilangan bulat tidak negatif dan semua bilangan real  a  dan  b . pangkat dari  a  +  b  merupakan penjumlahan dari suku-suku yang berupa kombinasi perkalian dari  a  dan  b .  

13. Maka kita dapatkan pola Cara segitiga pascal adalah cara yang dapat digunakan untuk bilangan yang pangkatnya kecil karena untuk yang berpangkat besar akan sulit jika harus menjabarkan dengan cara segitiga pascal. Maka cara lain yang dapat digunakan adalah cara kombinasi. Misalnya bilangan (a+b) 3 adalah hasil perkalian dari 3 faktor sbb.   Koefisien (a+b) 1 Koefisien (a+b) 2 Koefisien (a+b) 3 Koefisien (a+b) 4 Koefisien (a+b) 5 Koefisien (a+b) 6 Untuk menentukan koefisiennya dapat menggunakan segitiga pascal .

14. Kita pilih bagian yang ingin kita kalikan dari ketiga faktor itu. Misalnya, jika kita memilih a dari setiap faktor dan mengalikannya, maka kita peroleh aaa . Jika kita memilih a dari faktor pertama, a dari faktor kedua dan b dari faktor ketiga kemudian mengalikannya, maka kita peroleh aab , dan seterusnya. Sehingga semua kemungkinan pemilihan baik a maupun b dari masing-masing faktor adalah aaa ; aab ; aba ; abb ; baa ; bab ; bba ; bbb Jika dikalikan maka hasilnya : Hasil akhirnya adalah :    

15. Bilangan 3 yang merupakan koefisien dari muncul dari pemilihan a dari 2 faktor dan b dari 1 faktor sisanya . Hal ini bisa dilakukan dalam atau cara. Cara yang sama bisa dilakukan untuk memperoleh koefisien yang dalam hal ini merupakan pemilihan a dari faktor dan b dari 3 faktor lainnya yang dapat dilakukan dalam atau cara, dan seterusnya. Dari penjelasan diatas, maka didapatkan rumus:      

16. Contoh soal : Ekspansikan (a+b) 6 Ekspansikan (x+2y) 5 Jawab:   Ingat bahwa:   2.    

17. THANK YOU