Contoh Pembuktian Menggunakan Induksi Matematika #1: Habis Dibagi 3
Mari kita membuktikan menggunakan induksi matematika! :D
Soal
Buktikan dengan induksi matematika bahwa:
$n^3 - n$ habis dibagi $3$ untuk setiap bilangan asli $n$.
Pembahasan
Ingat ya yang dimaksud dengan bilangan asli itu (disimbolkan dengan $\mathbb{N}$) adalah $1,2,3,4,5$,.., dst.
Untuk membuktikan bahwa $n^3 - n$ habis dibagi $3$ untuk setiap bilangan asli $n$ dengan metode induksi matematika, kita harus melakukan 3 langkah berikut.
#Langkah Pembuktian ke-1:
Buktikan Berlaku untuk $n = 1$.
Pada langkah ini, kita harus membuktikan bahwa $n^3 - n$ habis dibagi $3$ untuk $n= 1$.
Caranya?
Ya, substitusikan saja $n=1$ ke $n^3-n$. Kita akan memperoleh:
$\begin{split} n^3 - n &= (1)^3 - 1 \\ &= 1 - 1 \\ &= 0 \end{split}$
Jelas sekali ya bahwa $0$ itu kan habis dibagi dengan $3$.
Jadi, pada langkah ke-1 ini kita sudah berhasil membuktikan bahwa $n^3 - n$ habis dibagi $3$ untuk $n= 1$.
Mari kita berbahagia sebentar. Hahaha. :D
Untuk membuktikan bahwa $n^3 - n$ habis dibagi $3$ untuk $n=2,3,4,5,6...$ dst ya... silakan simak kelanjutan pembuktian di bawah! :D
#Langkah Pembuktian ke-2:
Diasumsikan Berlaku untuk suatu $n = p$.
Pada langkah ini, kita mengasumsikan bahwa $n^3 - n$ habis dibagi $3$ untuk suatu bilangan asli $n$ yang bernilai $p$.
Dengan kata lain, terdapat suatu bilangan asli $p$, sedemikian sehingga $p^3 - p$ habis dibagi $3$.
Ingat ya!
Ini baru asumsi lho!
Asumsi itu adalah sesuatu yang diyakini kebenarannya, tapi belum terbukti benar.
#Intermeso
Selingan Proses Pembuktian
Progress kita sejauh ini:
- Kita berhasil membuktikan bahwa $n^3 - n$ habis dibagi $3$ untuk nilai $n = 1$.
- Kita mengasumsikan bahwa $n^3 - n$ habis dibagi $3$ untuk suatu nilai $n=p$.
Pada intemeso alias selingan proses pembuktian ini, kita akan mengulik sedikit perihal bentuk $n^3 -n$.
Perhatikan bahwa $n^3-n$ itu kan bisa difaktorkan.
Ya toh? :D
Nah, jika $n^3 -n$ difaktorkan, akan diperoleh:
$n^3 - n = (n-1)\cdot(n)\cdot(n+1)$
Perhatikan bahwa untuk sebarang bilangan asli $n$, akan berlaku $n \neq (n-1)$.
Ya toh? :)
Untuk sebarang bilangan asli $n$, kita juga dapat menyatakan bahwa $n \neq (n+1)$.
Ya toh? :)
Jadi, kita dapat menyimpulkan bahwa $n$, $n-1$, dan $n+1$ adalah $3$ bilangan asli yang berbeda.
Ya tidak? :D
Dari sifat-sifat di atas, kita dapat menyatakan suatu sifat baru ini.
Jika bilangan $n$, $n-1$, dan $n+1$ kita kalikan,
kemudian terdapat suatu bilangan asli $x$ yang membagi habis hasil perkalian $3$ bilangan tersebut,
maka salah satu dari $n$, $n-1$, atau $n+1$ pastilah kelipatan $x$.
Kita akan menggunakan sifat di atas pada #Langkah Pembuktian ke-3.
Intermeso selesai sampai di sini.
Mari, sekarang kita kembali ke langkah utama pembuktian. :)
#Langkah Pembuktian ke-3:
Buktikan Berlaku untuk $n = p + 1$.
Pada langkah ini, kita harus membuktikan bahwa $n^3 - n$ habis dibagi $3$ untuk $n = p + 1$.
Sebelumnya, ingat bahwa pada bagian #Intermeso, kita dapat memfaktorkan $n^3 - n$ menjadi $(n-1)\cdot(n)\cdot(n+1)$.
Dengan demikian, dengan mensubstitusikan $n=p+1$ ke $(n-1)\cdot(n)\cdot(n+1)$, kita akan memperoleh:
$\begin{split} n^3 - n &=(n-1)\cdot(n)\cdot(n+1) \\ &= ((p+1) - 1)\cdot(p+1)\cdot((p+1)+1)\\ &= (p)\cdot(p+1)\cdot(p+2) \\ \end{split}$
Jadi, membuktikan bahwa $n^3 - n$ habis dibagi $3$ untuk $n = p + 1$ ekuivalen dengan membuktikan bahwa $(p)\cdot(p+1)\cdot(p+2)$ habis dibagi $3$.
***
Selanjutnya, bagaimanakah cara membuktikan bahwa $(p)\cdot(p+1)\cdot(p+2)$ habis dibagi $3$?
Ingat! Pada #Langkah Pembuktian ke-2, kita mengasumsikan bahwa $p^3 - p$ habis dibagi $3$.
Karena $p^3 - p$ dapat difaktorkan menjadi $(p-1)\cdot(p)\cdot(p+1)$, maka asumsi bahwa $p^3 - p$ habis dibagi $3$ akan ekuivalen dengan asumsi bahwa $(p-1)\cdot(p)\cdot(p+1)$ habis dibagi $3$.
Perhatikan bahwa $p$, $(p-1)$, dan $(p+1)$ adalah tiga bilangan asli yang berbeda. Oleh sebab itu, karena asumsi $(p-1)\cdot(p)\cdot(p+1)$ habis dibagi $3$, menurut sifat di dalam kotak biru di bagian #Intermeso, kita dapat menyimpulkan bahwa:
Salah satu dari $p$, $(p-1)$, atau $(p+1)$ adalah kelipatan $3$.
Bisa jadi, $p$ adalah kelipatan $3$.
Bisa jadi, $(p-1)$ adalah kelipatan $3$.
Bisa jadi, $(p+1)$ adalah kelipatan $3$.
Pokoknya, salah satu dari $p$, $(p-1)$, atau $(p+1)$ adalah kelipatan $3$.
Mari kita cermati tiga kemungkinan tersebut satu per satu. :)
***
##Kemungkinan Pertama:
$p$ adalah kelipatan $3$.
Pada kemungkinan ini, $p$ adalah bilangan asli kelipatan $3$.
Ingat!
Misi utama kita pada #Langkah Pembuktian ke-3 ini adalah membuktikan bahwa $(p)\cdot(p+1)\cdot(p+2)$ habis dibagi dengan $3$.
Perhatikan!
Karena $p$ adalah salah satu faktor dari $(p)\cdot(p+1)\cdot(p+2)$, maka dapat kita simpulkan bahwa $(p)\cdot(p+1)\cdot(p+2)$ merupakan bilangan asli kelipatan $3$.
Dengan kata lain, $(p)\cdot(p+1)\cdot(p+2)$ habis dibagi $3$.
Jadi, jika $p$ merupakan bilangan asli kelipatan $3$, maka $(p)\cdot(p+1)\cdot(p+2)$ akan habis dibagi $3$.
##Kemungkinan Kedua:
$(p-1)$ adalah kelipatan $3$.
Pada kemungkinan ini, $(p-1)$ adalah bilangan asli kelipatan $3$.
Oleh sebab itu, $(p-1) + 3 = p+2$ juga merupakan bilangan asli kelipatan $3$ dong?
Ingat!
Misi utama kita pada #Langkah Pembuktian ke-3 ini adalah membuktikan bahwa $(p)\cdot(p+1)\cdot(p+2)$ habis dibagi dengan $3$.
Perhatikan!
Karena $(p+2)$ adalah salah satu faktor dari $(p)\cdot(p+1)\cdot(p+2)$, maka dapat kita simpulkan bahwa $(p)\cdot(p+1)\cdot(p+2)$ merupakan bilangan asli kelipatan $3$.
Dengan kata lain, $(p)\cdot(p+1)\cdot(p+2)$ habis dibagi $3$.
Jadi, jika $(p-1)$ merupakan bilangan asli kelipatan $3$, maka $(p)\cdot(p+1)\cdot(p+2)$ akan habis dibagi $3$.
##Kemungkinan Ketiga:
$(p+1)$ adalah kelipatan $3$.
Pada kemungkinan ini, $(p+1)$ adalah bilangan asli kelipatan $3$.
Ingat!
Misi utama kita pada #Langkah Pembuktian ke-3 ini adalah membuktikan bahwa $(p)\cdot(p+1)\cdot(p+2)$ habis dibagi dengan $3$.
Perhatikan!
Karena $(p+1)$ adalah salah satu faktor dari $(p)\cdot(p+1)\cdot(p+2)$, maka dapat kita simpulkan bahwa $(p)\cdot(p+1)\cdot(p+2)$ merupakan bilangan asli kelipatan $3$.
Dengan kata lain, $(p)\cdot(p+1)\cdot(p+2)$ habis dibagi $3$.
Jadi, jika $(p+1)$ merupakan bilangan asli kelipatan $3$, maka $(p)\cdot(p+1)\cdot(p+2)$ akan habis dibagi $3$.
***
Dari pembuktian panjang di atas, kita dapat menyimpulkan bahwa:
- Jika $p$ adalah kelipatan $3$, maka $(p)\cdot(p+1)\cdot(p+2)$ akan habis dibagi dengan $3$.
- Jika $(p-1)$ adalah kelipatan $3$, maka $(p)\cdot(p+1)\cdot(p+2)$ akan habis dibagi dengan $3$.
- Jika $(p+1)$ adalah kelipatan $3$, maka $(p)\cdot(p+1)\cdot(p+2)$ akan habis dibagi dengan $3$.
Dengan kata lain:
Berdasarkan asumsi bahwa $(p-1)\cdot(p)\cdot(p+1)$ habis dibagi dengan $3$, akan berlaku benar bahwa $(p)\cdot(p+1)\cdot(p+2)$ akan habis dibagi dengan $3$.
Pernyataan di atas ekuivalen dengan:
Berdasarkan asumsi bahwa $p^3 - p$ habis dibagi dengan $3$, akan berlaku benar bahwa $(p+1)^3 - (p+1)$ akan habis dibagi dengan $3$.
#Kesimpulan:
Berdasarkan Langkah Pembuktian ke-1 hingga ke-3, kita dapat menyimpulkan benar bahwa $n^3 - n$ habis dibagi $3$ untuk setiap bilangan asli $n$.