# a manipulation of Fibonacci recurrence

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

-
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

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

-
@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.

-
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