<s>[INST] strange fibonacci recurrence As it is well known fibonacci numbers satisfy the recurrence relation $$F_{n}=F_{n-1}+F_{n-2}$$ with initial conditions $F_{0}=0$ and $F_{1}=1$.
While playing around with numbers,I noticed the following recurrence relation for the fibonacci numbers
$$F_{n}=4F_{n+1}+F_{n-4}-(2F_{n+2}+F_{n-2})$$
Valid for $n\geq 4$
Can anyone enjoy the challenge of proving this simple relation?
 [/INST] It can be seen that:
$$F_{n-4} = F_{n-2} - F_{n-3} = - F_{n-1} + 2 F_{n-2} = 2 F_{n} - 3 F_{n-1} = - 3 F_{n+1} + 5 F_{n},$$
$$ F_{n-2} = F_{n} - F_{n-1} = - F_{n+1} + 2 F_{n}$$
and leads to:
\begin{align}
4F_{n+1}+F_{n-4}-(a F_{n+2}+F_{n-2}) &= 4 F_{n+1} - 3 F_{n+1} + 5 F_{n} - a F_{n+2} + F_{n+1} - 2 F_{n} \\
&= 2 F_{n+1} - a F_{n+2} + 3 F_{n}\\
&= (2 - a) F_{n+2} + F_{n}.
\end{align}
When $a =2$ this reduces to
$$ 4 F_{n+1} + F_{n-4} - 2 F_{n+2} - F_{n-2} = F_{n}.$$
When $a = 1$ this reduces to
$$ 4 F_{n+1} + F_{n-4} - F_{n+2} - F_{n-2} = L_{n+1}$$
where $L_{n}$ are the Lucas numbers.
</s>