Let f be the Fibonacci sequence,

f(0) = 0

f(1) = 1

f(n) = f(n-1) + f(n-2), for all n > 1

Then prove for n > 1 that

\(P(n) := f(n+1)^2 - f(n)^2 = f(n-1)\times f(n+2)\)

The base cases are easy

For n = 2

\(f(3)^2 - f(2)^2 = 2^2 - 1^2 = 4 - 1 = 3\)

\(f(1)\times f(4) = 1 \times 3 = 3\)

Similarly for n = 3 (P(n) = 5).

So we assume that the statement P(n) is true of n. Technically, I should substitute 'k' or something, but there's no need as I think it's clear what variable we're labeling.

We want to show (WTS) that P(n+1) is true, expressed by (after simplifying)

\(P(n+1) := f(n+2)^2 - f(n+1)^2 = f(n)\times f(n+3)\)

At some point, you

*must*use the induction assumption, either directly or through some sort of substitution. I find this EXTREMELY difficult because there's so many forms of this function to relate. I mean, any f(k) can be rewritten as a sum of some offset of f(k)--e.g., f(n+1) = f(n) + f(n-1) AND f(n+1) = f(n+3) - f(n+2). Tricky!! To complicate matters even more, we have to deal with the squaring of f.

I spent all class trying to find an innovative way to intuit the solution, but I couldn't. Writing this out here has given me some ideas, but I figured I'd share the misery ... I mean joy!