Modul Induksi Matematika [PDF]

Citation preview

Baca ini terlebih dahulu: 1. Modul ini dapat disebarluaskan secara gratis 2. Dilarang keras untuk memperjualbelikan modul ini 3. Dilarang keras mengubah sebagian atau seluruh modul ini



Dibuat oleh: Lingga Musroji, Ambisforia e-mail: [email protected] Line: limuzzz Kaskus: musejakarta Jika ada kesalahan, pertanyaan, atau saran, silakan hubungi kontak di atas. Terimakasih.



A. Induksi Matematika Lemah Induk matematika lemah umum digunakan untuk membuktikan suatu pernyataan matematis yang domainnya adalah bilangan bulat atau disimbolkan ∀𝑛 ∈ ℕ(𝑝(𝑛)). Ada beberapa langkah yang perlu diperhatikan, yaitu: 1. 2. 3. 4.



Membuktikan kasus awal, yaitu 𝑛0 Mengasumsikan pernyataan benar untuk suatu bilangan bulat 𝑘, sehingga 𝑝(𝑘) benar Membuktikan jika 𝑝(𝑘) benar, maka 𝑝(𝑘 + 1) juga benar Kesimpulan



Perhatikan bahwa setiap langkah harus dituliskan dengan jelas.



1. Penjumlahan a. Buktikan 𝑝(𝑛): 1 + 2 + 3 + ⋯ + 𝑛 =



𝑛(𝑛+1) 2



untuk 𝑛 ≥ 1.



1. Untuk 𝑛 = 1: Sisi kiri: 1 = 1 Sisi kanan:



1(1+1) 2



=1



Terbukti benar. 2. Asumsikan 𝑝(𝑛) benar untuk 𝑛 = 𝑘, maka 1 + 2 + 3 + ⋯ + 𝑘 =



𝑘(𝑘+1) 2



3. Akan dibuktikan bahwa 𝑝(𝑘 + 1) juga benar (𝑘 + 1)(𝑘 + 2) 𝑘(𝑘 + 1) 𝑘 + (𝑘 + 1) = (𝑘 + 1) ( + 1) = 2 2 2 (𝑘 + 1)((𝑘 + 1) + 1) = 2 Terbukti 𝑝(𝑘 + 1) benar 1 + 2 + 3 … + 𝑘 + (𝑘 + 1) =



4. Kesimpulan: pernyataan 𝑝(𝑛): 1 + 2 + 3 + ⋯ + 𝑛 =



𝑛(𝑛+1) 2



untuk setiap 𝑛 ≥ 1 benar.



Catatan: tanda = menandakan kita menggunakan rumus yang kita dapatkan di langkah kedua. b. Buktikan 𝑝(𝑛):



1 1 1 + + + 1×3 2×4 3×5



⋯+



1 𝑛(𝑛+2)



1. Untuk 𝑛 = 1: 1



1



Sisi kiri: 1×3 = 3 3



1 (2×1+3)



3



5



3 4



= −



1



Sisi kanan: 4 − 2 (1+1)(1+2) = 4 − 12 = 3 Terbukti benar. 2. Asumsikan 𝑝(𝑛) benar untuk 𝑛 = 𝑘, maka



1 (2𝑛+3) 2 (𝑛+1)(𝑛+2)



untuk 𝑛 ≥ 1



1 1 1 1 3 1 (2𝑘 + 3) + + + ⋯+ = − 1×3 2×4 3×5 𝑛(𝑛 + 2) 4 2 (𝑘 + 1)(𝑘 + 2) 3. Akan dibuktikan 𝑝(𝑘 + 1) juga benar: 1 1 1 1 1 + + + ⋯+ + 1×3 2×4 3×5 𝑘(𝑘 + 2) (𝑘 + 1)((𝑘 + 1) + 2) (2𝑘 + 3) 3 1 1 1 = − + 4 (𝑘 + 1) (2(𝑘 + 2)) (𝑘 + 1) (𝑘 + 3) 3 1 1 2𝑘 + 3 = + ( − ) 4 𝑘 + 1 𝑘 + 3 2(𝑘 + 2) 3 1 (2(𝑘 + 2) − (2𝑘 + 3)(𝑘 + 3)) = + 4 𝑘+1 2(𝑘 + 3)(𝑘 + 2) 3 1 (2𝑘 + 4 − 2𝑘 2 − 9𝑘 − 9) = + 4 𝑘+1 2(𝑘 + 3)(𝑘 + 2) (−2𝑘 2 − 7𝑘 − 5) 3 1 = + (𝑘 + 1) 4 2(𝑘 + 2)(𝑘 + 3) 3 1 −(2𝑘 + 5)(𝑘 + 1) = + (𝑘 + 1) 4 2(𝑘 + 2)(𝑘 + 3) 3 2(𝑘 + 1) + 5 = − 4 2((𝑘 + 1) + 1)((𝑘 + 1) + 2) Terbukti 𝑝(𝑘 + 1) juga benar 4. Terbukti 𝑝(𝑛) benar untuk setiap 𝑛 ≥ 1



2. Pertidaksamaan a. Buktikan bahwa 𝑝(𝑛): 2𝑛 > 𝑛2 untuk setiap 𝑛 ≥ 5 1. Untuk kasus 𝑛 = 5: Sisi kiri: 25 = 32 Sisi kanan: 52 = 25 Karena 32 > 25, maka 𝑝(𝑛) terbukti benar untuk 𝑛 = 5. 2. Asumsikan 𝑝(𝑛) benar untuk 𝑛 = 𝑘, maka 2𝑘 > 𝑘 2 3. Akan dibuktikan 𝑝(𝑘 + 1) juga benar 2𝑘+1 = 2 × 2𝑘 > 2𝑘 2 = 𝑘 2 + 𝑘 2 > 𝑘 2 + (2𝑘 + 1) = (𝑘 + 1)2 Terbukti 2𝑘+1 > (𝑘 + 1)2 4. Kesimpulan: terbukti bahwa 2𝑛 > 𝑛2 untuk setiap 𝑛 ≥ 5 benar.



Catatan: tanda > menandakan kita menggunakan pertidaksamaan dari langkah 2.



Untuk memahami > perhatikan bahwa 𝑘 2 > 2𝑘 + 1 untuk setiap 𝑛 ≥ 5. b. Buktikan bahwa 𝑝(𝑛): 2𝑛 < 𝑛! untuk setiap 𝑛 ≥ 4 1. Untuk kasus 𝑛 = 4: Sisi kiri: 24 = 16 Sisi kanan: 4! = 24 Karena 16 < 24, maka 𝑝(𝑛) terbukti benar untuk 𝑛 = 4 2. Asumsikan 𝑝(𝑛) benar untuk 𝑛 = 𝑘, maka 2𝑘 > 𝑘! 3. Akan dibuktikan 𝑝(𝑘 + 1) juga benar 2𝑘+1 = 2 × 2𝑘 < 2𝑘! < (𝑘 + 1)𝑘! = (𝑘 + 1)! Terbukti 𝑝(𝑘 + 1) benar 4. Kesimpulan: 2𝑛 < 𝑛! untuk setiap 𝑛 ≥ 4



3. Keterbagiaan Teori: bilangan bulat 𝑎 dikatakan habis dibagi oleh bilangan bulat 𝑏 jika ada bilangan bulat 𝑚 sehingga 𝑎 = 𝑚 × 𝑏. Contoh: 6 habis dibagi oleh 3 karena ada 𝑚 = 2 sehingga 6 = 2 × 3. a. Buktikan bahwa 𝑝(𝑛): 𝑛3 − 𝑛 habis dibagi 6 untuk setiap 𝑛 ≥ 1 1. Untuk kasus 𝑛 = 1: 13 − 1 = 0, karena ada 𝑚 = 0 sehingga 0 = 0 × 3 maka 𝑝(𝑛) benar untuk 𝑛 = 1 2. Asumsikan untuk 𝑛 = 𝑘, 𝑝(𝑛) benar, maka 𝑘 3 − 𝑘 habis dibagi 3 atau ada 𝑚 sehingga 𝑘 3 − 𝑘 = 3𝑚 3. Akan dibuktikan bahwa 𝑝(𝑘 + 1) juga benar (𝑘 + 1)3 − (𝑘 + 1) = 𝑘 3 + 3𝑘 2 + 3𝑘 + 1 − 𝑘 − 1 = (𝑘 3 − 𝑘) + 3(𝑘 2 + 𝑘) = 3𝑚 + 3(𝑘 2 + 𝑘) = 3(𝑚 + 𝑘 2 + 𝑘) Terbukti ada 𝑚′ = 𝑚 + 𝑘 2 + 𝑘 sehingga (𝑘 + 1)3 − (𝑘 + 1) = 3𝑚′. Jadi 𝑝(𝑘 + 1) juga benar. 4. Kesimpulan: 𝑛3 − 𝑛 habis dibagi 3 untuk setiap 𝑛 ≥ 1 b. Buktikan bahwa 4𝑛+1 + 52𝑛−1 habis dibagi 21 untuk setiap 𝑛 ≥ 1 1. Untuk kasus 𝑛 = 1: 41+1 + 52×1−1 = 42 + 51 = 21 = 1 × 21 Terbukti ada 𝑚 = 1 sehingga 41+1 + 5(2×1−1) = 𝑚 × 21 2. Asumsikan untuk 𝑛 = 𝑘, 𝑝(𝑛) benar, maka ada 𝑚 sehingga 4𝑘+1 + 52𝑘−1 = 21𝑚 3. Akan dibuktikan bahwa 𝑝(𝑘 + 1) juga benar 4(𝑘+1)+1 + 52(𝑘+1)−1



= 4 × 4𝑘+1 + 52 × 52𝑘−1 = 4 × 4𝑘+1 + 25 × (21𝑚 − 4𝑘+1 ) = 21 × (25𝑚) + 4 × 4𝑘+1 − 25 × 4𝑘+1 = 21 × (25𝑚) − 21 × 4𝑘+1 = 21(25𝑚 − 4𝑘+1 ) Terbutki ada 𝑚′ = 25𝑚 − 4𝑘+1 sehingga 4(𝑘+1)+1 + 52(𝑘+1)−1 = 21𝑚′. Jadi 𝑝(𝑘 + 1) juga benar 4. Kesimpulan: 4𝑛+1 + 52𝑛−1 habis dibagi 21 untuk setiap 𝑛 ≥ 1