How can the Fibonacci sequence be proven using induction?

[majestrooo]

Homework Statement

Prove for k >= 0, r >= 2

F_(k+r) = F_k * F_(r-2) + F_(k+1) * F_(r-1)

Homework Equations

I wonder if one should use induction ? If so, I don't know how to do it with two variables.

If not, should I use the Fibonacci definition F_n = F_n-1 + F_n-2 in some way by substitution and renaming
subindexes?

The Attempt at a Solution

Have only tried to substitute index like k + r = m, r-2 = m etc but no luck :(

 

[CompuChip]

If you fix k then you can easily do induction on r, and that works out. So if you can also show that it holds for r = 2 for this fixed k, then you have your result (k being arbitrary).

 

[majestrooo]

Ok cool, I solved it!

Now my next problem is to prove F_2n = (F_n-1)^2 + (F_n)^2

So I tried to set r = k in the previous identity but I didn't get a solution.

Here's my attempt

r = k

F_2k = F_k * F_k-2 + F_k+1 * F_k-1

= (F_k-1 + F_k-2) * F_k-2 + F_k+1 * F_k-1

= F_k-1 * F_k-2 + (F_k-2)^2 + F_k+1 * F_k-1

= F_k-1 * F_k-2 + (F_k-2)^2 + (F_k + F_k-1) * F_k-1

= F_k-1 * F_k-2 + (F_k-2)^2 + F_k * F_k-1 + (F_k-1)^2

= (F_k-2)^2 + F_k-1 * (F_k + F_k-2) + (F_k-1)^2

= (F_k-2)^2 - (F_k-1)^2 + (F_k-1)^2 (attention " - " before the second term)

= (F_k-2)^2 = (F_k + F_k-1)^2 = (F_k)^2 + 2F_k * F_k-1 + (F_k-1)^2

So how do I get rid of th second term? ;)