Fibonacci

Trees and bits (part 1)

Let us dwell on the subject of the family tree as treated in introduction.



This is the family tree of a couple of rabbits in the problem of Fibonacci. A 0 represents a pair of newborn rabbits, and a 1 represents a couple of, at least 1 year old, rabbits. At the same time the picture representent the family tree of a drone. A 0 represents a drone and a 1 represents a female bee.


The red part of the family tree is also a representation of the family tree of a drone, and the blue part is the family tree of the mother of a drone. This yields that the n-th row (from the root) can be split into a blue part (a copy of the n-1-st row) and a red part (copy of the n-2-nd row).
The number of bees on the n-th row (say a_n) satisfies the recursion a_n = a_n-1 + a_n-2. Thus a_n = F_n, the n-th Fibonacci number.

The n-th row (n>1) of the family tree (from the root) is composed of the first F_n characters from the infinite sequence 1 0 1 1 0 1 0 1 1 0 1 1 ....
The k-th character of this sequence is denoted by f(k). For which k is f(k) = 1? Well, for k = 1,3,4,6,8,9,11,...
We will show that the i-th number of 1,3,4,6,8,9,11,... is [i],
in other words, f(k) = 1 if and only if k = [i] for certain integer i.
(With the brackets [] we mean that the number is rounded off. = (1 + 5)/2, the golden ratio).
(proof (not easy)).

There exists a simple procedure to create the sequence 1,3,4,6,8,9,11,....
To that end, we create a sequence a₁, b₁, a₂, b₂, a₃, b₃, ... of positive integers according to the following receipt:
a_n is the smallest positive integer that has not yet appeared in the sequence (so a₁ = 1).
b_n = a_n + n.
Now regard the sequences a₁, a₂, a₃, ... and b₁, b₂, b₃, ... .
They are the sequences
1,3,4,6,8,9,11,... and 2,5,7,10,13,15,18,...
Notice that the first of these sequences is the sequence [], [2], [3], ... .
The second sequence is the sequence [²], [2²], [3²], ... .
This shows that every positive integer can be written as [n²] or as [n].
Actually, every positive integer can also be written as [n²] - [n].
Notice that if a_i = F_n, then b_i = F_n+1 and visa versa.
In addition n is even. The same is true for Lucas numbers.