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$? 
 A: 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}$.
A: 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.
