Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $F_n$ be the Fibonacci number, and we know

$F_{n+2} = F_{n+1} + F_{n} $ with $F_0 =1,F_1 = 1$

And this can be manipulated to

$F_{n+6} = 4F_{n+3} + F_n$

if we let n be a multiple of 3, we can write $A_r = F_{3r}$, and we get

$A_{r+2} = 4A_{r+1} + A_r$ with $A_0=1, A_1=1$

So I am wondering, can we prove the relation:

$F_{r(k+2)} = AF_{r(k+1)} + BF_{rk}$, $k \in N$

exist for every $r \geq 1$ ? And is the pair of $(A,B)$ unique for every value of $r$?

share|cite|improve this question
Answer is yes. An easy way to see it is to use characteristic equations of recurrence relations. – Calvin Lin Mar 27 '14 at 21:43
up vote 3 down vote accepted

Recall the theory of recurrence relations: The characteristic equation of the fibonacci sequence is $X^2 - X - 1 = 0 $.

This tells us that $F_n = a \alpha^n + b \beta ^n $ (for some constants $a$ and $b$), where $ \alpha + \beta = -1 $ and $ \alpha \beta = -1$.

Setting $A_n = F_{rn}$, we get that $$A_n = a(\alpha^r)^n + b (\beta^r)^n.$$

Hence, $A_n$ must satisfy the recurrence relation

$$ A_n = A A_{n-1} + B A_{n-2},$$

which has the characteristic equation $X^2 - AX - B = 0$, which gives us $A= \alpha^r + \beta^r $ and $ -B= \alpha^r \beta^r = (-1)^r $.

Note: $A$ can be determined using Newton's polynomials. As Nate remarks, $ A = \alpha^r + \beta^r = F_{r} + F_{r-2}$.

share|cite|improve this answer
@egreg True, I forgot to shift my terms over. let me make the edit. – Calvin Lin Mar 27 '14 at 21:49
Moreover $A = F_r + F_{r-2}$ – Nate Mar 27 '14 at 21:52
@Nate Good observation. I was too lazy to carry out the calculations. – Calvin Lin Mar 27 '14 at 21:58
@Nate Could you tell me how did you calculate the value of A? – cinvro Mar 28 '14 at 0:33
To be honest, I knew what the answer should be because of the calculation I outlined in my answer, but I didn't post that until later. However you can get that from this method by actually calculating $a$ and $b$ and doing some algebra. – Nate Mar 28 '14 at 3:24

Here's another approach that gives you the coefficients $A$ and $B$ for free, but has one step that's a bit less elementary than @Calvin Lin's approach.

There is a well known matrix $M$ for which $F_n$ is the top left entry of $M^n$ for all $n$.

Therefore $F_{rk}$ is the top left entry of $(M^r)^k$ for all $k$.

Now apply the Cayley-Hamilton theorem to $M^r$ and multiply by $(M^r)^k$ to get that $(M^r)^{k+2} = Tr(M^r)\cdot(M^r)^{k+1} - det(M^r)\cdot (M^r)^k$

So the top left entries also satisfy this same recurrence, then it's just a matter of computing the trace and determinant of $M^r$ in terms of the Fibonacci numbers, which I'll leave to you to fill in the details.

share|cite|improve this answer
One tiny note: it might be explicitly worth pointing out that the matrix $M$ is $2\times 2$, which makes Cayley-Hamilton take a particularly easy form. – Steven Stadnicki Mar 27 '14 at 22:24

Your Answer


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.