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

Let $\alpha$ and $\beta$ be the two roots of the equation $x^2-x-1=0$.  Then the $n$-th Fibonacci number is equal to
$$\frac{\alpha^n-\beta^n}{\sqrt{5}}.$$
We are interested in the recurrence satisfied by the numbers
$$\frac{\alpha^{3n}-\beta^{3n}}{\sqrt{5}}.$$
If $x$ is either of $\alpha$ or $\beta$, then $x^2=x+1$.  Multiply by $x$. We get $x^3=x^2+x=2x+1$. It follows that $x^4=2x^2+x=3x+2$.  But then $x^5=3x^2+2x=5x+3$, and then $x^6=5x^2+3x=8x+5$.
We want $x^6=Ax^3+B$, where $A$ and $B$ are rational, indeed integers. So we want $8x+5=A(2x+1)+B$. Reading off $A$ and then $B$ is obvious: we need $A=4$ and $B=1$.   
So the numbers $\alpha^{3n}$ and $\beta^{3n}$ satisfy the recurrence $y_n=4y_{n-1}+y_{n-2}$. By linearity, so do the numbers $\frac{\alpha^{3n}-\beta^{3n}}{\sqrt{5}}$.
Comment: Note that using the same basic strategy, we can write down the recurrence satisfied by $\frac{\alpha^{kn}-\beta^{kn}}{\sqrt{5}}$.  The coefficients that we painfully computed by hand, step by step, can be expressed simply in terms of Fibonacci numbers, and therefore so can the recurrence for the numbers $\frac{\alpha^{kn}-\beta^{kn}}{\sqrt{5}}$.
