proof : even nth Fibonacci number using Mathematical Induction

Question

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 ?

Answer 1

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

Answer 2

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.