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?
Best Answer
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} $$