Induksi Matematika: Membuktikan Keterbagian

Jenis induksi matematika pembagian dapat dijumpai pada berbagai macam soal yang menggunakan kalimat berikut ini:

• a habis dibagi dengan b

• b faktor dari a

• b membagi a

• a adalah kelipatan dari b

Keempat ciri tersebut, menjadi petunjuk bahwa pernyataan tersebut dapat diselesaikan dengan menggunakan induksi matematika jenis pembagian. Hal-hal yang perlu diingat ialah apabila bilangan a habis dibagi dengan b, maka a = b.k dengan k adalah bilangan bulat.

Maka, jika p habis dibagi a serta q habis dibagi a, sehingga (p + q) juga akan habis dibagi a.

Contoh Soal

1. Buktikan bahwa (aⁿ − bⁿ) habis dibagi oleh (a − b), (∀a, b ∈ Z)(∀n ∈ N).

• Langkah Basis

Tunjukkan bahwa p(n) benar untuk n = 1

p(1): (a¹ − b¹) = (a − b), jelas habis dibagi oleh (a − b)

• Langkah Induksi

Asumsikan bahwa p(n) benar untuk n = k

p(k): (a^k − b^k) habis dibagi oleh (a − b)

Akan ditunjukkan bahwa p(n) benar untuk n = k + 1

p(k + 1): (a^{k + 1} − b^{k + 1}) = a^k.a − b^k.b

= a^k.a − b^k.a + b^k.a − b^k.b

= (a^k − b^k).a + b^k.(a − b)

Menurut asumsi, (a^k − b^k).a habis dibagi (a − b), begitu juga jelas untuk b^k.(a − b), sehingga

(a^k − b^k).a + b^k.(a − b) habis dibagi oleh (a − b)

berarti p(n) benar untuk n = k + 1

• Langkah Konklusi

Karena telah ditunjukkan bahwa p(n) benar untuk n = 1, dan telah diasumsikan bahwa p(n) benar untuk n = k, sehingga dapat ditunjukkan bahwa p(n) benar untuk n = k + 1. Oleh karena itu, p(n) benar untuk setiap n bilangan asli.

2. Buktikan bahwa (a^{2n − 1} + b^{2n − 1}) habis dibagi oleh (a + b), (∀a, b ∈ Z)(∀n ∈ N).

• Langkah Basis

Tunjukkan bahwa p(n) benar untuk n = 1

p(1): (a^{2.1 − 1} + b^{2.1 − 1}) = (a + b), jelas habis dibagi oleh (a + b)

• Langkah Induksi

Asumsikan bahwa p(n) benar untuk n = k

p(k): (a^{2k − 1} + b^{2k − 1}) habis dibagi oleh (a + b)

Akan ditunjukkan bahwa p(n) benar untuk n = k + 1

p(k + 1): (a^{2k + 1} + b^{2k + 1}) = a^{2k − 1}.a² + b^{2k − 1}.b²

= a^{2k − 1}.a² + b^{2k − 1}.a² − b^{2k − 1}.a² + b^{2k − 1}.b²

= (a^{2k − 1} + b^{2k − 1}).a² − b^{2k − 1}.(a² − b²)

= (a^{2k − 1} + b^{2k − 1}).a² − b^{2k − 1}.(a + b).(a − b)

Menurut asumsi, (a^{2k − 1} + b^{2k − 1}) habis dibagi (a + b), begitu juga jelas untuk suku lain, sehingga

(a^{2k − 1} + b^{2k − 1}).a² − b^{2k − 1}.(a + b).(a − b) habis dibagi oleh (a + b)

berarti p(n) benar untuk n = k + 1

• Langkah Konklusi

Karena telah ditunjukkan bahwa p(n) benar untuk n = 1, dan telah diasumsikan bahwa p(n) benar untuk n = k, sehingga dapat ditunjukkan bahwa p(n) benar untuk n = k + 1. Oleh karena itu, p(n) benar untuk setiap n bilangan asli.

3. Buktikan bahwa (∀n ∈ N). n⁵ − n habis dibagi oleh 5

• Langkah Basis

Tunjukkan bahwa p(n) benar untuk n = 1

p(1): 1⁵ − 1 = 0, jelas habis dibagi oleh 5

• Langkah Induksi

Asumsikan bahwa p(n) benar untuk n = k

p(k): k⁵ − k habis dibagi oleh 5

Akan ditunjukkan bahwa p(n) benar untuk n = k + 1

p(k + 1): (k + 1)⁵ − (k + 1) = k⁵ + 5k⁴ + 10k³ + 10k² + 5k + 1 − k − 1

= 5(k⁴ + 2k³ + 2k² + k) + k⁵ − k

Menurut asumsi, k⁵ − k habis dibagi 5, begitu juga jelas untuk suku lain, sehingga

5(k⁴ + 2k³ + 2k² + k) + k⁵ − k habis dibagi oleh 5

berarti p(n) benar untuk n = k + 1

• Langkah Konklusi

Karena telah ditunjukkan bahwa p(n) benar untuk n = 1, dan telah diasumsikan bahwa p(n) benar untuk n = k, sehingga dapat ditunjukkan bahwa p(n) benar untuk n = k + 1. Oleh karena itu, p(n) benar untuk setiap n bilangan asli.

4. Buktikan bahwa (∀n ∈ N). n³ − 4n + 6 habis dibagi oleh 3

• Langkah Basis

Tunjukkan bahwa p(n) benar untuk n = 1

p(1): 1³ − 4.1 + 6 = 3, jelas habis dibagi oleh 3

• Langkah Induksi

Asumsikan bahwa p(n) benar untuk n = k

p(k): k³ − 4k + 6 habis dibagi oleh 3

Akan ditunjukkan bahwa p(n) benar untuk n = k + 1

p(k + 1): (k + 1)³ − 4(k + 1) + 6 = k³ + 3k² + 3k + 1 − 4k − 4 + 6

= 3k² + 3k − 3 + k³ − 4k + 6

= 3(k² + k − 1) + k³ − 4k + 6

Menurut asumsi, k³ − 4k + 6 habis dibagi 3, begitu juga jelas untuk suku lain, sehingga

3(k² + k − 1) + k³ − 4k + 6 habis dibagi oleh 3

berarti p(n) benar untuk n = k + 1

• Langkah Konklusi

Karena telah ditunjukkan bahwa p(n) benar untuk n = 1, dan telah diasumsikan bahwa p(n) benar untuk n = k, sehingga dapat ditunjukkan bahwa p(n) benar untuk n = k + 1. Oleh karena itu, p(n) benar untuk setiap n bilangan asli.

Berikut video induksi matematika Part 1:

Berikut video induksi matematika Part 2: