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}
$$
Consecutive Fibonacci numbers are relatively prime, which is fairly easy to establish, so there are no consecutive even Fibonacci numbers.
Thus, if $F_{n}$ is even, then $F_{n-1}$ is odd, $F_{n+1}$ is odd, $F_{n+2}$ is odd, and $F_{n+3}$ is even. So every third Fibonacci number is even. In other words, your formula says for even $F_{n}$,
$$
F_{n+3} = 4F_{n} + F_{n-3}
$$
Can you see why this formula is true?
Best Answer
You can actually use the formula $\frac{\varphi^n - (-\varphi)^{-n}}{\sqrt{5}}$ where $\varphi = \frac{1 + \sqrt{5}}{2}$. But for all non integer values you get complex numbers. These numbers are of the form $a + bi$ where a and b are the numbers you're famillar with, and $i$ is a constant defined as $i^2 = -1$ or equivalently $i = \sqrt{-1}$.
You can plot this function:
When you look at the plot, you can see the red line which is the imaginary part of the number, and the imaginary part is zero at all of the integer values, which makes sense since the fibonacci numbers aren't imaginary.
Edit: You can avoid complex numbers by using another formula. $$\frac{\varphi^x - \cos(\pi x)\varphi^{-x}}{\sqrt{5}}$$ When you plot this function, you get:
