# recurrence relation for squares of fibonacci numbers

I have a problem finding a proof that the squares of the Fibonacci numbers satisfy the recurrence relation $a_{n+3} - 2*a_{n+2} - 2*a_{n+1} + a_n = 0$ and solving this recurrence relation.

Some help would be great!

-

Let $(u_n)$ denote the sequence of Fibonacci numbers. By definition, $$u_{n+2} = u_{n+1} + u_n\quad\text{and}\quad u_{n+3} = u_{n+2} + u_{n+1} = 2u_{n+1} + u_n,$$ so that using $(x+y)^2 = x^2 + y^2 + 2xy$, $$a_{n+2} = a_{n+1} + a_n + 2u_n u_{n+1},\quad\text{and}\quad a_{n+3} = 4a_{n+1} + a_n + 4u_nu_{n+1}.$$ Finally, for all $n$ one has: $$a_{n+3} - 2a_{n+2} - 2a_{n+1} + a_n = (4-2-2)a_{n+1} + (1-2+1)a_n + (4-4)u_nu_{n+1}.$$

-

Using this on $\displaystyle a_{n+3}-2a_{n+2}-2a_{n+1}+a_n=0$

we have $\displaystyle a_n=A(-1)^n+B\left(\frac{3+\sqrt5}2\right)^n+C\left(\frac{3-\sqrt5}2\right)^n\ \ \ \ (1)$ where $A,B,C$ are arbitrary constants

Now using Binet's formula, the $n$th Fibonacci term $\displaystyle F_n=\frac{a^n-b^n}{a-b}$ where $a,b$ are the roots of $t^2-t-1=0$

$\displaystyle\implies a+b=1, ab=-1, (a-b)^2=(a+b)^2-4ab=5$

$\displaystyle\implies a^2=\frac{3+\sqrt5}2,b^2=\frac{3-\sqrt5}2;$

$$\displaystyle\implies F_n^2=\frac{a^{2n}+b^{2n}-2(ab)^n}{(a-b)^2}=\frac{(a^2)^n+(b^2)^n-2(-1)^n}5=\frac{\left(\frac{3+\sqrt5}2\right)^n+\left(\frac{3-\sqrt5}2\right)^n-2(-1)^n}5$$ which is clearly a special form of $(1)$

-

$$5a_n=5F_n^2=a^n+b^n-2c^n$$ where $\displaystyle a=\frac{3+\sqrt5}2,b=\frac{3-\sqrt5}2,c=-1$

$$a^n+b^n-2c^n-5a_n=0\ \ \ \ (1)$$

So, $a,b$ are the roots of $t^2-3t+1=0$ $\implies a^2=3a-1,a^3=a(3a-1)=3a^2-a=3(3a-1)-a=8a-3$

Replacing $n$ with $n+1,n+2,n+3$ respectively we can form three more equations

$$a^{n+1}+b^{n+1}-2c^{n+1}-5a_{n+1}=0$$ $$\iff a\cdot a^n+b \cdot b^n+2\cdot c^n-5a_{n+1}=0\ \ \ \ (2)$$

$$a^{n+2}+b^{n+2}-2c^{n+2}-5a_{n+1}=0$$ $$\iff(3a-1)a^n+(3b-1)b^n-2c^n-5a_{n+2}=0\ \ \ \ (3)$$

$$a^{n+3}+b^{n+3}-2c^{n+3}-5a_{n+3}=0$$ $$\iff(8a-3)a^n+(8b-3)b^n+2c^n-5a_{n+3}=0\ \ \ \ (4)$$

So, the eliminant of $a^n,b^n,c^n$ will be

$\det\begin{pmatrix} 1 & 1 & -2 & -5a_n \\ a & b & -2 & -5a_{n+1} \\ 3a-1 & 3b-1 & 2 & -5a_{n+2} \\ 8a-3 & 8b-3 & 2 & -5a_{n+3} \end{pmatrix}=0$

-