Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
$x^{10}-x^{5}-1=0$ –  leo Dec 10 '12 at 3:03

3 Answers 3

up vote 6 down vote accepted

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.

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

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)
share|improve this answer

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} $

Is this correct? If not please advise.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.