# How to solve recurrence equation $f(n) = f(n-5) + f(n-10)$?

How to solve recurrence equation $f(n) = f(n-5) + f(n-10)$? For something like fibonacci sequence $f(n+1) = f(n) + f(n-1)$ I can solve for the quadratic equation $x^2-x-1=0$ then $f(n) = A x_1 + A^\prime x_2$. But what should I do for this one?

-
$x^{10}-x^{5}-1=0$ –  leo Dec 10 '12 at 3:03

In this case it is exactly Fibonacci recurrences, except separate ones for $n$ congruent to $0$ modulo $5$, $n$ congruent to $1$ modulo $5$, and so on up to $n$ congruent to $4$ modulo $5$. Knowing the values of $f(0)$ and $f(5)$ will let you compute $f$ at multiples of $5$, and nowhere else. Similarly, knowing $f(1)$ and $f(6)$ will let you compute $f(11)$, $f(16)$, $f(21)$, and so on, but nowhere else. So it is natural to separate the problem into cases.

So let $g_0(n)=f(5n)$, We have the familiar recurrence $g_0(n)=g_0(n-1)+g_0(n-2)$.

Let $g_1(n)=f(5n+1)$. We have the familiar recurrence $g_1(n)=g_1(n-1)+g_1(n-2)$.

And so on. For a concrete solution we will need initial values $f(0)$ up to $f(9)$.

Remark: You could however proceed "as usual," getting the characteristic equation $x^{10}-x^5-1=0$. This is a quadratic in $x^5$. Solve for $x^5$. We get the usual roots. For the values of $x$, take the ordinary fifth roots of the equation $y^2-y-1=0$, and multiply by fifth roots of unity (four of these are non-real.) After a while, one can get a general formula that will involve sines and cosines of $2n\pi/5$. However, this is very much less pleasant than the division into cases suggested above.

-
Hi, could you take a glance on my attempt below? much appreciated –  xiamx Dec 10 '12 at 4:13

Although a topic in Discrete math, I attempted this question using the tools I learned in linear algebra.

Rewrite it as $f(n+10) = f(n+5) +f(n)$, this can be represented as

$\left( \begin{array}{c} f_{n+10} \\ f_{n+5} \end{array} \right) = \left( \begin{array}{cc} 1 &1 \\ 1& 0 \end{array} \right) \left( \begin{array} {c} f_{n+5} \\ f_n \end{array} \right)$ $\left( \begin{array}{c} f_{n+10} \\ f_{n+5} \end{array} \right) = \left( \begin{array}{cc} 1 &1 \\ 1& 0 \end{array} \right)^{n+5} \left( \begin{array} {c} f_{1} \\ f_{-4} \end{array} \right)$

Then diagonalize $\left( \begin{array}{cc} 1 &1 \\ 1& 0 \end{array} \right)$ to find eigenvalues, which is the same as the ones for fibonacci, $1/2 (1-\sqrt5), 1/2 (1+\sqrt5)$

then $f_{n+5} = \alpha (1/2 (1-\sqrt5))^{n+5} +\beta (1/2 (1+\sqrt5))^{n+5}$

The second displayed line of matrices is not correct. The idea will work, but there needs to be either a separation into cases, or a much larger matrix, I think a $10\times 10$, except that there will be stuff only near the diagonal, essntially a string of five $2\times 2$ Fibonacci matrices, with $0$'s elsewhere. The general solution is a $10$-parameter solution, not the two parameter solution you obtained ($\alpha$, $\beta$). –  André Nicolas Dec 10 '12 at 4:20
I am not quite sure if this is what you were looking for but as was answered previously if you begin at $n=0,5,10,15,20,25,30,...$ and use the Binet form below you get the Fibonacci Numbers
$$\frac{1}{\sqrt{5}}\left(\sqrt[5]{\frac{1}{2}+\frac{\sqrt{5}}{2}}\right)^{n+5}-\frac{1}{\sqrt{5}}\left(\sqrt[5]{\frac{1}{2}-\frac{\sqrt{5}}{2}}\right)^{n+5}$$ If you use Excel you can paste the formula below in for A1=0, A2=5, A3=10..... and verify that you get the Fibonacci Numbers
(((1/2+SQRT(5)/2))^(1/5)^(A1+5)-((1/2-SQRT(5)/2))^(1/5)^(A1+5))/SQRT(5)