<s>[INST] 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"?
 [/INST] By inspection $f(3n+3)=4f(3n)+f(3n-3)$, as you’ve already noticed. This is easily verified:
$$\begin{align*}
f(3n+3)&=f(3n+2)+f(3n+1)\\
&=2f(3n+1)+f(3n)\\
&=3f(3n)+2f(3n-1)\\
&=3f(3n)+\big(f(3n)-f(3n-2)\big)+f(3n-1)\\
&=4f(3n)+f(3n-1)-f(3n-2)\\
&=4f(3n)+f(3n-3)\;.
\end{align*}$$
However, I didn’t arrive at this systematically; it just ‘popped out’ as I worked at eliminating terms with unwanted indices.
Added: Here’s a systematic approach, but I worked it out after the fact.
The generating function for the Fibonacci numbers is $$g(x)=\frac{x}{1-x-x^2}=\frac1{\sqrt5}\left(\frac1{1-\varphi x}-\frac1{1-\hat\varphi x}\right)\;,$$ where $\varphi = \frac12(1+\sqrt5)$ and $\hat\varphi=\frac12(1-\sqrt5)$, so that $f(n)=\frac1{\sqrt5}(\varphi^n-\hat\varphi^n)$. Thus, $f(3n)=\frac1{\sqrt5}(\varphi^{3n}-\hat\varphi^{3n})$. Thus, we want 
$$\begin{align*}
h(x)&=\frac1{\sqrt5}\sum_{n\ge 0}(\varphi^{3n}-\hat\varphi^{3n})x^n\\
&=\frac1{\sqrt5}\left(\sum_{n\ge 0}\varphi^{3n}x^n-\sum_{n\ge 0}\hat\varphi^{3n}x^n\right)\\
&=\frac1{\sqrt5}\left(\frac1{1-\varphi^3 x}-\frac1{1-\hat\varphi^3 x}\right)\\
&=\frac1{\sqrt5}\cdot\frac{(\varphi^3-\hat\varphi^3)x}{1-(\varphi^3+\hat\varphi^3)x+(\varphi\hat\varphi)^3x^2}\;.
\end{align*}$$
Now $\varphi+\hat\varphi=1$, $\varphi-\hat\varphi=\sqrt5$, $\varphi\hat\varphi=-1$, $\varphi^2=\varphi+1$, and $\hat\varphi^2=\hat\varphi+1$, so 
$$\begin{align*}
h(x)&=\frac1{\sqrt5}\cdot\frac{(\varphi^3-\hat\varphi^3)x}{1-(\varphi^3+\hat\varphi^3)x+(\varphi\hat\varphi)^3x^2}\\
&=\frac{(\varphi^2+\varphi\hat\varphi+\hat\varphi^2)x}{1-(\varphi^2-\varphi\hat\varphi)x-x^2}\\
&=\frac{(\varphi^2-1+\hat\varphi^2)x}{1-(\varphi^2+1+\hat\varphi^2)x-x^2}\\
&=\frac{(\varphi+\hat\varphi+1)x}{1-(\varphi+3+\hat\varphi)x-x^2}\\
&=\frac{2x}{1-4x-x^2}\;.
\end{align*}$$
It follows that $(1-4x-x^2)h(x)=2x$ and hence that $h(x)=4xh(x)+x^2h(x)+2x$. Since the coefficient of $x^n$ in $h(x)$ is $f(3n)$, this tells me that 
$$\begin{align*}
\sum_{n\ge 0}f(3n)x^n&=h(x)=4xh(x)+x^2h(x)+2x\\
&=\sum_{n\ge 0}4f(3n)x^{n+1}+\sum_{n\ge 0}f(3n)x^{n+2}+2x\\
&=\sum_{n\ge 1}4f(3n-3)x^n+\sum_{n\ge 2}f(3n-6)x^n+2x\;,
\end{align*}$$
which by equating coefficients immediately implies that $f(3n)=4f(3n-3)+f(3n-6)$ for $n\ge 2$. It also gets the initial conditions right: the constant term on the righthand side is $0$, and indeed $f(3\cdot 0)=0$, and the coefficient of $x$ is $4f(0)+2=2=f(3)$, as it should be.
</s>