6
$\begingroup$

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

  • 0
    Why isn't $f_{n+2}=3f_n-f_{n-2}$ suitable?2011-12-27
  • 0
    @J.M., sorry I do not understand. If I were to expand $f_{n+2}$ the way I do it, I would end up with $2f_n + f_{n - 2} + f_{n - 3}$. Again, I can make this work if I know what I am trying to get. I wonder if you have read the question correctly - I am looking for even-valued (not even-indexed) fib numbers. If my assumption is mistaken, then sorry. However, I am not sure how to systematically arrive at a relation you have given and how to use it to help me simplify things.2011-12-27
  • 0
    It seems I did misunderstand you (and I apologize for this); have you looked at the references [here](https://oeis.org/A014445) by any chance?2011-12-27

8 Answers 8