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?
 A: Note that we can't always do this with integer coefficients. For example,
$$
F_{n}=\frac52F_{n-2}+\frac12F_{n-5}\tag{1}
$$
and
$$
F_{n}=\frac{13}3F_{n-3}-\frac23F_{n-7}\tag{2}
$$

We can use the fact that
$$
\left(\frac{1\pm\sqrt5}2\right)^n=\frac1{2^n}\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}5^k\pm\frac{\sqrt5}{2^n}\sum_{k=0}^{\lfloor(n-1)/2\rfloor}\binom{n}{2k+1}5^k\tag{3}
$$
to get
$$
\begin{align}
F_n=
&\frac{\sum\limits_{k=0}^{\lfloor(b-1)/2\rfloor}\binom{b}{2k+1}5^k}
{\sum\limits_{k=0}^{\lfloor(b-a-1)/2\rfloor}\binom{b-a}{2k+1}5^k}\frac{F_{n-a}}{2^a}\\
&+\left[\sum_{k=0}^{\lfloor b/2\rfloor}\binom{b}{2k}5^k
-\frac{\sum\limits_{k=0}^{\lfloor(b-1)/2\rfloor}\binom{b}{2k+1}5^k}
{\sum\limits_{k=0}^{\lfloor(b-a-1)/2\rfloor}\binom{b-a}{2k+1}5^k}
\sum_{k=0}^{\lfloor(b-a)/2\rfloor}\binom{b-a}{2k}5^k\right]\frac{F_{n-b}}{2^b}\tag{4}
\end{align}
$$
Thus, there is always a recurrence with rational coefficients for any $0\lt a\lt b$.

Note that if we let $\psi=-1/\phi$, then both $\phi$ and $\psi$ satisfy
$$
\begin{align}
0
&=(x^n-\phi^n)(x^n-\psi^n)\\
&=x^{2n}-(\phi^n+\psi^n)x^n+(\phi\psi)^n\\
&=x^{2n}-L_nx^n+(-1)^n\tag{5}
\end{align}
$$
where $L_n$ is a Lucas Number. Therefore, the Fibonacci numbers satisfy
$$
F_n=L_kF_{n-k}-(-1)^kF_{n-2k}\tag{6}
$$
Fix $k$ and let $a_j=jk$ and $b_j=(j+1)k$. Equation $(6)$ has integer coefficients for $a_1,b_1$.
Equation $(6)$ says that if we have coefficients $\lambda_j,\kappa_j\in\mathbb{Z}$ for $a_j,b_j$, then
$$
\begin{align}
F_n
&=\lambda_jF_{n-jk}+\kappa_jF_{n-(j+1)k}\\
&=(\lambda_jL_k+\kappa_j)F_{n-(j+1)k}-(-1)^k\lambda_jF_{n-(j+2)k}\\
&=\lambda_{j+1}F_{n-(j+1)k}+\kappa_{j+1}F_{n-(j+2)k}\tag{7}
\end{align}
$$
where $\lambda_{j+1}=\lambda_jL_k+\kappa_j$ and $\kappa_{j+1}=(-1)^{k+1}\lambda_j$ are both integers for $a_{j+1},b_{j+1}$.
Note that $b_j=(j+1)k=(j+1)(b_j-a_j)$.
Using $(6)$ and $(7)$, we get a recurrence with integer coefficients if $b-a\mid b$.
In particular, given $k=b-a$ and $j=\frac{b}{b-a}-1$, we have
$$
\begin{bmatrix}\lambda\\\kappa\end{bmatrix}
=\begin{bmatrix}L_k&1\\(-1)^{k+1}&0\end{bmatrix}^j
\begin{bmatrix}1\\0\end{bmatrix}\tag{8}
$$
Since $\small\begin{bmatrix}2&1\\-1&-1\end{bmatrix}^2=\begin{bmatrix}3&1\\-1&0\end{bmatrix}$, we can apply $(8)$ even if $b-a=2$ when $b$ is odd. We deal with this in the next section.

As noted by achille hui, $b-a=2$ also allows $\lambda,\kappa\in\mathbb{Z}$. This follows from the case $b-a=1$.
If we apply $(8)$ to the case $a=b-1$, we get
$$
\begin{align}
F_n
&=F_b F_{n-b+1}+F_{b-1}F_{n-b}\\
&=F_b(F_{n-b+2}-F_{n-b})+F_{b-1}F_{n-b}\\
&=F_b F_{n-b+2}+(F_{b-1}-F_b)F_{n-b}\\
&=F_b F_{n-b+2}-F_{b-2}F_{n-b}\tag{9}
\end{align}
$$
Thus, for $a=b-2$,
$$
\begin{bmatrix}\lambda\\\kappa\end{bmatrix}
=\begin{bmatrix}F_b\\-F_{b-2}\end{bmatrix}\tag{10}
$$

Conclusion: The Conjecture, as stated, is false. However, if $b-a\mid b$ or $b-a=2$, then there are $\lambda,\kappa\in\mathbb{Z}$, given in $(8)$ or $(10)$, so that
$$
F_n=\lambda F_{n-a}+\kappa F_{n-b}\tag{11}
$$
A: 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.
A: 
Assume $0 < a < b$, the necessary and sufficient condition for the existence of $\lambda, \mu \in \mathbb{Z}$ such that
  $$F_n = \lambda F_{n-a} + \mu F_{n-b},\quad\forall n \in \mathbb{Z}_{+}\tag{*1}$$
  is either
  $$b - a \le 2\quad\text{ or }\quad b - a = \gcd(a,b) > 2.$$

Let $\alpha = \frac{1+\sqrt{5}}{2}$ and $\beta = \frac{1 - \sqrt{5}}{2}$, we have
the Binet's formula for the Fibonacci numbers:
$$F_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}$$
Using this formula, it is easy to solve for $\lambda, \mu$ and find:
$$F_n = \frac{1}{F_{b-a}}\left(F_b F_{n-a} - (-1)^{b-a} F_a F_{n-b}\right)$$
It is known that Fibonacci sequences is a 
strong divisibility sequence.
For any positive integers $p, q$, we have
$$p | q \implies F_p | F_q\quad\text{ and }\quad \gcd(F_p,F_q) = F_{\gcd(p,q)}$$
What you are looking for is essentially equivalent to finding $a,b$ such that
$$F_{b-a} | F_a \;\land\; F_{b-a}|F_b\quad\iff\quad F_{b-a} | \gcd(F_a,F_b)
\quad\iff\quad
F_{b-a} | F_{\gcd(a,b)}$$
Since $\gcd(a,b) \le b - a \implies F_{\gcd(a,b)} \le F_{b-a}$ and $F_k$ is strictly increasing when $k > 2$, the
last condition is satisfied when and only when
$$b - a \le 2\quad\text{ or }\quad b - a = \gcd(a,b) > 2$$
This leads to three and only three families of solutions for $(*1)$. Namely,


*

*$b-a  = 1$


*

*$F_n = F_{a+1}F_{n-a} + F_{a} F_{n-a-1}$


*$b - a = 2$


*

*$F_n = F_{a+2}F_{n-a} - F_{a} F_{n-a-2}$


*$b - a = \gcd(a,b) > 2$, i.e there are integers $c > 2, m > 0$ such that


*

*$F_n = \frac{F_{(m+1)c}}{F_c} F_{n-mc} - (-1)^c \frac{F_{mc}}{F_c} F_{n-(m+1)c}$  


As a special case of this, if one take $m = 1$, this leads to


*

*$F_n = L_c F_{n-c} - (-1)^c F_{n-2c}$


where $L_c = \frac{F_{2c}}{F_c} = \alpha^c + \beta^c$ is the Lucas number.
A: Remember that the Fibonacci numbers are the unique sequence satisfying the equation $F_{n+1}=F_n+F_{n-1}$ and the conditions $F_0=0$, $F_1=1$.  Now, consider the sequence $G_n=aF_{n-s}+bF_{n-t}$.  Then it's obvious that $G_n$ satisfies the (linear) equation $G_{n+1}=G_n+G_{n-1}$; to have $G_n=F_n$ we then must only satisfy $G_0=aF_{-s}+bF_{-t}=0$ and $G_1=aF_{1-s}+bF_{1-t}=1$.  In matrix notation, this is the condition that $\left(\array{0\\1}\right)=\left(\array{F_{-s}&F_{-t}\\F_{1-s}&F_{1-t}}\right)\left(\array{a\\b}\right)$.  But now, presuming that the matrix $\left(\array{F_{-s}&F_{-t}\\F_{1-s}&F_{1-t}}\right)$ is invertible (more on this in a bit), we can rewrite this as $\left(\array{a\\b}\right)=\left(\array{F_{-s}&F_{-t}\\F_{1-s}&F_{1-t}}\right)^{-1}\left(\array{0\\1}\right) =\dfrac1{F_{-s}F_{1-t}-F_{-t}F_{1-s}}\left(\array{F_{1-t}&-F_{-t}\\-F_{1-s}&F_{-s}}\right)\left(\array{0\\1}\right)$.
Now, d'Ocagne's identity states that $F_mF_{n+1}-F_{m+1}F_n=(-1)^nF_{m-n}$; by plugging in $m=-s$, $n=-t$ we find that the determinant of our original matrix $F_{-s}F_{1-t}-F_{-t}F_{1-s}$ is just $(-1)^{t-s}F_{t-s}$; this is nonzero (and so the matrix is invertible) as long as $t\neq s$ (and the case $t=s$ is clearly degenerate - the non-invertibility there says that we can't write $F_n$ as a function of only $F_{n-s}$ for any $s$).
Finally, using the identity and multiplying out by the inverse matrix, we obtain $a=\dfrac{-F_{-t}}{(-1)^{t-s}F_{t-s}}$ and $b=\dfrac{F_{-s}}{(-1)^{t-s}F_{t-s}}$; since $F_{-n}=(-1)^{n+1}F_n$ these can be written as $$a=(-1)^s\dfrac{F_t}{F_{t-s}}$$ and $$b=-(-1)^t\dfrac{F_s}{F_{t-s}}$$  Now, we can use the divisibility property of the Fibonacci numbers, which implies that for $n\gt 2$, $F_n\mid F_m$ iff $n\mid m$.  This implies that for $a$ and $b$ to be integers, then (as others have noted) we must have either $|t-s|\leq 2$, or $(t-s)\mid s$ (note that this immediately implies that $(t-s)\mid t$, and so of course $a$ is an integer iff $b$ is).
