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 ?


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


  • $\begingroup$ Wow, good answer, :) $\endgroup$ – user427802 Dec 7 '19 at 13:41

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.