Why are Fibonacci numbers on the Collatz conjecture function?

Question

$C(x) = \frac{1}{2}x$ if $x$ is even, $3x + 1$ if $x$ is odd

I will use $E$ to refer to an even number, and $O$ to refer to an odd number

1. $C(E)$ may be $E$ or may be $O$, as an even number divided by $2$ may be even or odd
2. $C(O)$ is always $E$, as an odd number multiplied by $3$ and added $1$ is always even

with that, we could construct a map after applying the function $C(x)$ $n$ times

Let's say you start with some arbitrary odd number $O$.

0. $O$

If you apply the the function to $O$ it will be some even number $E$

1. $E$

If you apply the function to $E$ you will have 2 possible values, $E$ and $O$

2. $(E, O)$

Now $E$ can turn intro $E$ or $O$, and $O$ turn intro $E$

3. $(E, O, E)$

If you continue the process and see how many terms you get on each iteration, what you get is: $1, 1, 2, 3, 5, 8, 13, 21...$

Why did it happen? Are those really the Fibonacci numbers?

Answer 1

One of definitions of Fibonacci numbers (wikipedia claims it was the original one used by Fibonacci) is as follow: imagine that we have a pair of newborn rabbits. Newborn rabbits take one month to grow up. Grown up pair of rabbits every month give birth to a new pair of rabbits. Then $n$-th Fibonacci number is number of rabbits we have in $n$-th month: we have $F_{n - 1}$ grown up rabbits and $F_{n - 2}$ newborn for a total of $F_{n - 1} + F_{n - 2} = F_n$ rabbits, next month we will have $F_{n - 1} + F_{n - 2} = F_n$ grown up ($F_{n - 1}$ we already had plus $F_{n - 2}$ newly grown) and $F_{n - 1}$ newborn.

This is exactly the same process you use if you consider $O$ as a newborn rabbit, and $E$ as a grown up: on each step, each newborn rabbit grows up, while already grown up remain and also give birth to newborn.