Exercise 28.

You will prove that the Fibonacci numbers satisfy the identity \(F_n^2 + F_{n+1}^2 = F_{2n+1}\text{.}\) One way to do this is to prove the more general identity,

\begin{equation*} F_mF_n + F_{m+1}F_{n+1} = F_{m+n+1}\text{,} \end{equation*}

and realize that when \(m = n\) we get our desired result.

Note that we now have two variables, so we want to prove this for all \(m \ge 0\) and all \(n \ge 0\) at the same time. For each such pair \((m,n)\text{,}\) let \(P(m,n)\) be the statement \(F_mF_n + F_{m+1}F_{n+1} = F_{m+n+1}\)

  1. First fix \(m = 0\) and give a proof by mathematical induction that \(P(0,n)\) holds for all \(n \ge 0\text{.}\) Note this proof will be very easy.

  2. Now fix an arbitrary \(n\) and give a proof by strong mathematical induction that \(P(m,n)\) holds for all \(m \ge 0\text{.}\)

  3. You can now conclude that \(P(m,n)\) holds for all \(m,n\ge 0\text{.}\) Do you believe that? Explain why this sort of induction is valid. For example, why do your proofs above guarantee that \(P(2,3)\) is true?

in-context