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 $S$ be the shift operator on sequences (as in Bill Dubuque's answer). Note that the Fibonacci sequence is killed by $S^2-S-1$. The Fibonacci sequence will then be killed by any "polynomial" multiple of $S^2-S-1$. To get a recurrence for every $k^{\rm{th}}$ term, all we need to do is find a multiple of $S^2-S-1$ that only involves powers of $S^k$.
First note that $S^2-S-1=(S-a)(S-b)$ where $a=\phi$ (the golden ratio) and $b=-1/\phi$. Consider the operator $(S^k-a^k)(S^k-b^k)=S^{2k}-(a^k+b^k)S^k+(ab)^k$. It is a polynomial multiple of $S^2-S-1$, so it kills the Fibonacci sequence. It only involves powers of $S^k$.
Recall that one formula for the $k^{\rm{th}}$ Lucas number is $L_k=a^k+b^k$, and note that $ab=-1$. Thus, we get that $S^{2k}-L_kS^k+(-1)^k$ kills the Fibonacci sequence. 
Therefore, in summary, we get
$$
F_{n+2k}=L_kF_{n+k}-(-1)^kF_n\tag{1}
$$
For example,
$$
F_{n+2}=F_{n+1}+F_n\tag{k=1}
$$
$$
F_{n+4}=3F_{n+2}-F_n\tag{k=2}
$$
$$
F_{n+6}=4F_{n+3}+F_n\tag{k=3}
$$
$$
F_{n+8}=7F_{n+4}-F_n\tag{k=4}
$$
$$
F_{n+10}=11F_{n+5}+F_n\tag{k=5}
$$
