Latihan 7.
Berikut ini contoh teknik induksi yang lebih rumit, yang disebut induksi ganda.
Anda akan membuktikan bahwa bilangan-bilangan Fibonacci memenuhi identitas \(F_n^2 + F_{n+1}^2 = F_{2n+1}\text{.}\) Salah satu caranya adalah dengan membuktikan identitas yang lebih umum,
\begin{equation*}
F_mF_n + F_{m+1}F_{n+1} = F_{m+n+1}\text{,}
\end{equation*}
lalu memperhatikan bahwa ketika \(m = n\text{,}\) kita memperoleh hasil yang diinginkan.
Perhatikan bahwa sekarang kita memiliki dua variabel, sehingga kita ingin membuktikan hal ini untuk semua \(m \ge 0\) dan semua \(n \ge 0\) secara bersamaan. Untuk setiap pasangan \((m,n)\) tersebut, misalkan \(P(m,n)\) adalah pernyataan \(F_mF_n + F_{m+1}F_{n+1} = F_{m+n+1}\text{.}\)
(a)
Pertama, tetapkan \(m = 0\text{,}\) lalu berikan pembuktian dengan induksi matematika bahwa \(P(0,n)\) berlaku untuk semua \(n \ge 0\text{.}\) Perhatikan bahwa pembuktian ini akan sangat mudah.
(b)
Sekarang tetapkan \(n\) sembarang, lalu berikan pembuktian dengan induksi matematika kuat bahwa \(P(m,n)\) berlaku untuk semua \(m \ge 0\text{.}\)
(c)
Sekarang Anda dapat menyimpulkan bahwa \(P(m,n)\) berlaku untuk semua \(m,n\ge 0\text{.}\) Apakah Anda memercayainya? Jelaskan mengapa induksi semacam ini sah. Sebagai contoh, mengapa pembuktian Anda di atas menjamin bahwa \(P(2,3)\) benar?