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

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)$$
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.