Fibonacci sequences, binary numbers and compositions

Fibonacci numbers

The Fibonacci numbers can be found in different ways in the sequence of binary strings.
Due to a bijection between binary strings and compositions,

every definition in terms of strings can also be given in terms of compositions, and vice versa.

• The number of binary words of length n (length from first digit to last value 1 digit) without consecutive 0s is the Fibonacci number Fn+1. E.g., out of the 8 binary words of length 4, there are F5 = 5 without consecutive 0s - they are 0101, 1101, 1011, 0111 and 1111.
• The number of strings of length n without consecutive 1s is the Fibonacci number Fn+2. E.g., out of the 16 binary strings of length 4, there are F6 = 8 without consecutive 1s - they are 0000, 1000, 0100, 0010, 1010, 0001, 1001 and 0101.
(By symmetry, the number of strings of length n without consecutive 0s is also Fn+2.)
This corresponds to the following statement about compositions, quoted from OEIS A000045:
F(n)=number of compositions of n-1 with no part greater than 2.
Example: F(4)=3 because we have 3 = 1+1+1=1+2=2+1.

00 corresponds to 1+1+1, 01 corresponds to 1+2, 10 corresponds to 2+1.

• The number of binary words of length n (length from first digit to last value 1 digit) without even numbers of consecutive 0s or 1s is the Fibonacci number Fn. E.g. out of 32 binary words of length 6 there are F6 = 8 with all runlengths odd - they are 000001, 010001, 000101, 010101, 011101, 000111, 010111 and 011111.
• The number of strings of length n without an odd number of consecutive 1s is the Fibonacci number Fn+1.
This corresponds to the following statement about compositions, quoted from OEIS:
F(n) = number of compositions of n into odd parts;
e.g. F(6) counts 1+1+1+1+1+1, 1+1+1+3, 1+1+3+1, 1+3+1+1, 1+5, 3+1+1+1, 3+3, 5+1.
• Further, the number of compositions of n without addends equal to 1 is the Fibonacci number Fn$-$ 1.
E.g. out of the 8 compositions of 4 there are F3 = 2 without 1s - they are 2+2 and the 4 itself.
Out of the 16 compositions of 5 there are F4 = 3 without 1s - they are 2+3, 3+2 and the 5 itself.

Fibonacci numbers of higher order

About the files showing two matrices:

• In the top matrices blocks of n or more consecutive 0s are indicated by green dots. The number of columns without green dots between two green trigons is an element of the Fibonacci sequence of order n.
• The number of compositions of natural numbers with no addend greater than n is a Fibonacci sequence of order n. Due to the bijection between compositions and binary numbers, this is what the bottom matrices show: The blocks of n or more consecutive 1s are indicated by strong red squares. The number of columns without strong red squares, from the left side to a green trigon, is an element of the Fibonacci sequence of order n.

Tribonacci numbers Binary and Tribonacci numbers: 1, 2, 4, 7, 13, 24, 44, 81, 149 (OEIS A000073)
Blocks of 3 and more consecutive 0s are indicated by green dots.
Blocks of 3 and more consecutive 1s are marked in strong red - they correspond to composition addends greater than 3. Blocks of consecutive 0s and 1s of a length divisible by 3 are marked by green dots and strong red squares.
Counting columns without green dots or strong red squares, from left side to a green trigon, gives a Tribonacci number.

Tetranacci numbers Binary and Tetranacci numbers: 1, 2, 4, 8, 15, 29, 56, 108, 208 (OEIS A000078)
Blocks of 4 and more consecutive 0s are indicated by green dots.
Blocks of 4 and more consecutive 1s are marked in strong red - they correspond to composition addends greater than 4. Blocks of consecutive 0s and 1s of a length divisible by 4 are marked by green dots and strong red squares.
Counting columns without green dots or strong red squares, from left side to a green trigon, gives a Tetranacci number.

Pentanacci numbers Binary and Pentanacci numbers: 1, 2, 4, 8, 16, 31, 61, 120, 236 (OEIS A001591)
Blocks of 5 and more consecutive 0s are indicated by green dots.
Blocks of 5 and more consecutive 1s are marked in strong red - they correspond to composition addends greater than 5.