Recurrence relation about square of Fibonacci number

Question

Prove that the square of the Fibonacci number satisfy the recurrence relation $a_{n+3}-2a_{n+2}-2a_{n+1}+a_n = 0$, and solve this recurrence relation with the correct initial conditions.

Answer 1

You know that $F_{n+3} = F_{n+2} + F_{n+1}$. So you have: $F_{n+3}^2 = F_{n+2}^2 + F_{n+1}^2 + 2F_{n+2}F_{n+1}$.

Then notice that $F_{n+2} = F_{n+1} + F_n$, so you get $F_{n+3}^2 = F_{n+2}^2 + F_{n+1}^2 + 2F_{n+1}F_n + 2F_{n+1}^2 \Rightarrow F_{n+3}^2 - F_{n+2}^2 - 2F_{n+1}^2 = F_{n+1}^2 + 2F_{n+1}F_n$

Then add $F_n^2$ to both parts of this equality:

$F_{n+3}^2 - F_{n+2}^2 - 2F_{n+1}^2 + F_n^2 = F_{n+1}^2 + 2F_{n+1}F_n + F_n^2$

After that you may notice that the right part of the equality is a perfect square. Use $F_{n+2} = F_{n+1} + F_n$ again. Finally, you get:

$F_{n+3}^2 - F_{n+2}^2 - 2F_{n+1}^2 + F_n^2 = F_{n+2}^2 \Rightarrow F_{n+3}^2 - 2F_{n+2}^2 - 2F_{n+1}^2 + F_n^2 = 0$,

q.e.d.

The correct initial conditions are simply squares of the first three (!) Fibonacci numbers:

$F_0^2 = 0, F_1^2 = 1, F_2^2 = 1$

To solve this recurrence relation, you have to consider a generating function $A(x) = \sum\limits_{n=0}^\infty a_n x^n$ with the recurrence relation $a_{n+3} = 2a_{n+2} + 2a_{n+1} - a_n$ and initial conditions $a_0 = 0, a_1 = 1, a_2 = 1$. Let's modify it:

$A(x) = \sum\limits_{n=0}^\infty a_n x^n$

$A(x) = a_0 + a_1 x + a_2 x^2 + \sum\limits_{n=0}^\infty a_{n+3} x^{n+3}$

$A(x) = a_0 + a_1 x + a_2 x^2 + \sum\limits_{n=0}^\infty (2a_{n+2} + 2a_{n+1} - a_n) x^{n+3}$

$A(x) = x + x^2 + 2\sum\limits_{n=0}^\infty a_{n+2}x^{n+3} + 2\sum\limits_{n=0}^\infty a_{n+1}x^{n+3} - \sum\limits_{n=0}^\infty a_n x^{n+3}$

$A(x) = x + x^2 + 2x(A(x) - x) + 2x^2 A(x) - x^3 A(x)$.

Thus,

$A(x) = \frac{-x^2 + x}{x^3 - 2x^2 - 2x + 1}$.

Answer 2

Alright so $a_k = (F_k)^2 \forall k$ So the intial conditions are quite simple $a_0 = (F_0)^2 = 0$ and $a_1 = (F_1)^2 = 1$. Now the actual proof. $ a_{n+3} = (F_{n+3})^2=(F_{n+2}+F_{n+1})^2 = F_{n+2}^2 +F_{n+2}F_{n+1} +F_{n+2}F_{n+1} + F_{n+1}^2 = a_{n+2} + F_{n+2}(F_{n+2}-F_n)+(F_{n+1}+F_n)F_{n+1}+a_{n+1}=a_{n+2}+F_{n+2}^2-F_{n+2}F_{n}+F_{n+1}^2+F_{n}F_{n+1}+a_{n+1}=2a_{n+2}+2a_{n+1}-F_n(F_{n+2}-F_{n+1})= 2a_{n+2}+2a_{n+1}-F_n^2= 2a_{n+2}+2a_{n+1}-a_n$ Thus we get $a_{n+3} =2a_{n+2}+2a_{n+1}-a_n$, move everything to the left side and you get the expression you are looking for.