Linear Combinations of Fibonacci Numbers (integer coefficients) While working on problem #2 on Project Euler, I came across the need to express $F_n$ as a linear combination of $F_{n-3}$ and $F_{n-6}$. This is relatively simple to do:
$$\begin{align} F_n &= F_{n-1}+F_{n-2}\\ &= F_{n-1}+F_{n-3}+F_{n-4}\\ &= F_{n-1}+F_{n-3}+F_{n-5}+F_{n-6}\\&= F_{n-2}+2F_{n-3}+F_{n-5}+F_{n-6}\\&= 3F_{n-3}+F_{n-4}+F_{n-5}+F_{n-6}\\&=4F_{n-3}+F_{n-6}\end{align}$$
This argument is ad hoc to an extreme, and it made me wonder about a more general conjecture:
Conjecture. Let $a,b<n$ and $a\neq b$. Then $F_n = \lambda F_{n-a} + \kappa F_{n-b}$ for some $\lambda,\kappa\in\mathbb Z$.
Is this true? If so, how can it be proven? If not, can we include some hypotheses on $a$ and $b$ that make it true?

Note that for any recurrence (including the Fibonacci sequence) which has a solution $u_n=A\alpha^n+B\beta^n$ the equation $$\lambda u_{n-a}+\mu u_{n-b}=\lambda(A\alpha^{n-a}+B\beta^{n-a})+\mu(A\alpha^{n-b}+B\beta^{n-b})=A(\lambda \alpha^{-a}+\mu\alpha^{-b})\alpha^n+B(\lambda \beta^{-a}+\mu\beta^{-b})\beta^n=u_n$$ implies $$\lambda \alpha^{-a}+\mu\alpha^{-b}=1$$and $$\lambda \beta^{-a}+\mu\beta^{-b}=1$$
And, given $\alpha, \beta, a, b$ this has a unique solution for $\lambda, \mu$ except in degenerate cases.
