Need help deriving recurrence relation for even-valued Fibonacci numbers. That would be every third Fibonacci number, e.g. $0, 2, 8, 34, 144, 610, 2584, 10946,...$
Empirically one can check that:
$a(n) = 4a(n-1) + a(n-2)$ where $a(-1) = 2, a(0) = 0$.
If $f(n)$ is $\operatorname{Fibonacci}(n)$ (to make it short), then it must be true that $f(3n) = 4f(3n - 3) + f(3n - 6)$.
I have tried the obvious expansion:
$f(3n) = f(3n - 1) + f(3n - 2) = f(3n - 3) + 2f(3n - 2) = 3f(3n - 3) + 2f(3n - 4)$
$ = 3f(3n - 3) + 2f(3n - 5) + 2f(3n - 6) = 3f(3n - 3) + 4f(3n - 6) + 2f(3n - 7)$
... and now I am stuck with the term I did not want. If I do add and subtract another $f(n - 3)$, and expand the $-f(n-3)$ part, then everything would magically work out ... but how should I know to do that? I can prove the formula by induction, but how would one systematically derive it in the first place?
I suppose one could write a program that tries to find the coefficients x and y such that $a(n) = xa(n-1) + ya(n-2)$ is true for a bunch of consecutive values of the sequence (then prove the formula by induction), and this is not hard to do, but is there a way that does not involve some sort of "Reverse Engineering" or "Magic Trick"?

The definition of $F_n$ is given:


*

*$F_0 = 0$

*$F_1 = 1$

*$F_{n+1} = F_{n-1} + F_{n}$ (for $n \ge 1$)


Now we define $G_n = F_{3n}$ and wish to find a recurrence relation for it.
Clearly


*

*$G_0 = F_0 = 0$

*$G_1 = F_3 = 2$


Now we can repeatedly use the definition of $F_{n+1}$ to try to find an expression for $G_{n+1}$ in terms of $G_n$ and $G_{n-1}$.
$$\begin{align*}
G_{n+1}&= F_{3n+3}\\
&= F_{3n+1} + F_{3n+2}\\
&= F_{3n-1} + F_{3n} + F_{3n} + F_{3n+1}\\
&= F_{3n-3} + F_{3n-2} + F_{3n} + F_{3n} + F_{3n-1} + F_{3n}\\
&= G_{n-1} + F_{3n-2} + F_{3n-1} + 3 G_{n}\\
&= G_{n-1} + 4 G_{n}
\end{align*}$$
so this proves that $G$ is a recurrence relation.
