Why does this alternate Fibonacci relation appear to be true?

Question

So the normal fibonacci relation is famously as follows:

$$\begin{aligned}F_0 &= 0 \\ F_1 &= 1 \\ F_n &= F_{n-1} + F_{n-2}\end{aligned}$$

My friend appears to have discovered this alternate relation that allows you to skip by 3s, but I can't find it anywhere else to confirm why it works.

$$\begin{aligned}F_0 &= 0 \\ F_3 &= 2 \\ F_n &= 4F_{n-3} + F_{n-6}\end{aligned}$$

I think it's just a case of "simplification", but I wanted to confirm that. Does this work look correct?

$$\begin{aligned} F_n &= F_{n-1} + F_{n-2} \\ F_n &= F_{n-2} + F_{n-3} + F_{n-2} \\ F_n &= 2F_{n-2} + F_{n-3} \\ F_n &= 2(F_{n-3} + F_{n-4}) + F_{n-3} \\ F_n &= 3F_{n-3} + 2F_{n-4} \\ F_n &= 3F_{n-3} + F_{n-4} + F_{n-5} + F_{n-6} \\ F_n &= 4F_{n-3} + F_{n-6} \end{aligned}$$

Edit: I get that it doesn't do the entire sequence this way. We only needed the even terms for what we were working on. That's why I even called out that it skipped by 3s. To "fix" it all you would need to do is define the first 6 anyways.

Answer 1

Your derivation that $F_n=4F_{n-3} + F_{n-6}$ is correct ... so this is indeed true for the Fibonacci numbers.

However, your alternative formulation does not define $F_1$ and $F_2$, so you can't call it an alternative formulation. And even if you define $F_1$ and $F_2$, what are $F_4$ and $F_5$?

Indeed, given that the recursive part of your formulation makes reference to $F_{n-6}$, you need to define all 'base' values $F_0$ through $F_5$ separately in order for this to work as an alternative formulation.

Answer 2

That alternative definition "forgets" the terms $F_n$ when $n$ is not a multiple of three. So $F_5$, say, could be a crazy elephant.

Answer 3

The characteristic polynomial of the new recurrence is

$$t^6-4t^3-1=(t^2-t-1)(t^4+t^3+2t^2-t+1)=0$$ indeed has $\phi$ and $-\phi^{-1}$ among its real roots. The remaining four roots are complex conjugate.

You are still free to set $F_1,F_2,F_4$ and $F_5$, and they don't have to follow the standard Fibonacci sequence.

E.g.

$$\color{green}0, 1, 1, \color{green}{2}, 3, 5, \color{green}{8}, 13, 21, \color{green}{34}, 55, 89, \color{green}{144}, 233, 377, \color{green}{610},\cdots$$ vs. $$\color{green}{0}, 0, 1, \color{green}{2}, 3, 4, \color{green}{8}, 12, 17, \color{green}{34}, 51, 72, \color{green}{144}, 216, 305, \color{green}{610},\cdots$$