a manipulation of Fibonacci recurrence

Question

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 1

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

Answer 2

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.