proof : even nth Fibonacci number using Mathematical Induction I know that the sequence $f$ of even Fibonacci numbers has the recurrence relation 

$$f(n) = 4f(n-1) + f(n-2) \quad \text{for n } \ge 2$$

How to prove that this formula is true using Induction ? 
 A: This problem is a good illustration of when induction is helpful and when it isn't.
Let $F(n)$ represent the $n$'th Fibonacci number (where $F(0)=0$ and $F(1)=1$).  The first thing you want to observe is that $F(n)$ is even if and only if $n$ is a multiple of $3$.  That should be handled by induction, and I'll let you handle that by yourself.  (Hint: your assumption for the induction step is that $F(3n)$ is even and $F(3n-1)$ and $F(3n-2)$ are both odd.)
With that done, you just need to show that $F(3n)=4F(3n-3)+F(3n-6)$ for all $n\ge2$.  In fact, that's not anything special about multiples of $3$, so I'll just show that $F(n)=4F(n-3)+F(n-6)$ for all $n\ge6$ instead.  Let such an $n$ be given.  Note that $$F(n-4)=F(n-3)-F(n-5)\\F(n-6)=F(n-4)-F(n-5)$$ are both rearrangements of the standard recurrence relation.  Using them and the standard recurrence relation it follows for any $n\ge6$ that
$$F(n)=F(n-1)+F(n-2)\\=2F(n-2)+F(n-3)\\=3F(n-3)+2F(n-4)\\=4F(n-3)+F(n-4)-F(n-5)\\=4F(n-6)+F(n-6)$$
A: Once you know that $f(n)=F(3n)$ (as in Matthew Daly's answer), you can use Binet's formula:
$$
f(n)=F(3n)=\alpha \phi^{3n}+ \beta \psi^{3n}=\alpha (\phi^3)^n+ \beta (\psi^3)^n
$$
Now $\phi^3+\psi^3=4$ and $\phi^3\psi^3=-1$ and so $\phi^3$ and $\psi^3$ are roots of $x^2=4x+1$. Therefore, $f(n+2) = 4f(n+1) + f(n)$, as required.
