Subbab 3.9 Induksi Kuat
Ada kalanya Prinsip Induksi Matematika, setidaknya dalam bentuk yang telah kita pelajari sejauh ini, tampak belum memadai. Berikut sebuah contoh konkret. Profesor meminta Bob mempelajari fungsi \(f(n)\) yang didefinisikan secara rekursif oleh \(f(n) = 2f(n-1) - f(n-2)\) dengan \(f(1)=3\) dan \(f(2)=5\text{.}\) Secara khusus, profesor meminta Bob menghitung \(f(10^{10})\text{,}\) yang tampaknya merupakan tugas berat. Sambil minum kopi, Bob mencoret-coret serbet dan memperoleh \(f(3)=7\) serta \(f(4)=9\text{.}\) Hanya berdasarkan perhitungan tersebut, ia menduga bahwa mungkin saja \(f(n) = 2n+1\) untuk setiap \(n\geq 1\text{.}\) Jika dugaan ini benar, ia cukup melaporkan bahwa \(f(10^{10})=2\cdot 10^{10}+1=20000000001\text{.}\)
Bob mulai memahami pembuktian dengan induksi, sehingga ia mencoba membuktikan dengan induksi bahwa \(f(n)=2n+1\) untuk setiap \(n\ge1\text{.}\) Untuk kasus dasar, ia mencatat bahwa \(f(1)= 3=2\cdot1+1\text{,}\) sehingga sejauh ini semuanya beres. Untuk langkah induksi, ia mengasumsikan sebagai hipotesis induksi bahwa \(f(k)=2k+1\) untuk suatu \(k\ge1\text{,}\) lalu mencoba membuktikan bahwa \(f(k+1)=2(k+1)+1\text{.}\) Jika langkah ini dapat diselesaikan, pembuktian dengan induksi tersebut pun selesai.
Namun, pada titik ini Bob tampaknya menemui jalan buntu karena
\begin{equation*}
f(k+1) = 2f(k) - f(k-1) = 2(2k+1) - f(k-1),
\end{equation*}
dengan menggunakan hipotesis induksi untuk mengganti \(f(k)\) dengan \(2k+1\text{.}\) Namun, ia benar-benar bingung harus berbuat apa dengan \(f(k-1)\text{.}\) Jika ia mengetahui bahwa \(f(k-1)=2(k-1)+1\text{,}\) ruas kanan akan menghasilkan \(2(2k+1) -(2k-1)= 2k+3=2(k+1)+1\text{,}\) tepat seperti yang diinginkannya. Bob selalu mengikuti aturan dan harus mengakui bahwa ia tidak mengetahui bahwa \(f(k-1)=2(k-1)+1\text{.}\) Ia hanya mengetahui bahwa \(f(k)=2k+1\text{.}\)
Bob hampir menyerah dan meminta komputernya mulai melakukan perhitungan secara rekursif ketika Carlos datang dan bertanya apa yang sedang ia lakukan. Carlos segera melihat bahwa pendekatan yang digunakan Bob untuk membuktikan \(f(n)=2n+1\) dengan induksi tidak akan berhasil—tetapi setelah berpikir sejenak, Carlos mengatakan bahwa ada bentuk pembuktian induktif yang lebih kuat dan dapat menyelesaikan masalah tersebut. Dengan sabar, Carlos menjelaskan kepada Bob sebuah proposisi yang disebut Prinsip Induksi Kuat. Untuk membuktikan bahwa suatu pernyataan terbuka \(S_n\) benar untuk setiap \(n\ge1\text{,}\) cukuplah:
-
Menunjukkan bahwa \(S_1\) benar; dan
-
Menunjukkan bahwa \(S_{k+1}\) benar setiap kali \(S_m\) benar untuk semua bilangan bulat \(m\) dengan \(1\le m\le k\text{.}\)
Keabsahan proposisi ini mengikuti dari prinsip induksi matematika biasa; kedua prinsip itu ekuivalen, meskipun bentuk di atas menggunakan hipotesis yang lebih kuat. Hal yang baru di sini ialah bahwa untuk membuktikan suatu pernyataan, terkadang menguntungkan bagi Anda untuk membuktikan sesuatu yang bahkan lebih kuat. Para matematikawan kombinatorika menyebutnya fenomena “bootstrap”.
Berbekal pengamatan ini, Bob melihat dengan jelas bahwa prinsip induksi kuat cukup untuk membuktikan bahwa \(f(n)=2n+1\) untuk setiap \(n\ge1\text{.}\) Jadi, ia dapat mematikan komputernya dan menikmati kopinya.
