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 F_n+1. E.g., out of the 8 binary words of length 4, there are F₅ = 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 F_n+2. E.g., out of the 16 binary strings of length 4, there are F₆ = 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 F_n+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.

Consecutive 0s are marked by green dots.
Consecutive 1s are marked in strong red.

• 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 F_n. E.g. out of 32 binary words of length 6 there are F₆ = 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 F_n+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.

Even numbers of consecutive 0s are marked by green dots, even numbers of consecutive 1s are marked in strong red.
Columns without green dots or strong red are marked by black dots.

Even numbers of consecutive 1s (corresponding to odd composition addends 3, 5, 7...) are marked in strong red.
Columns without light red (= columns with only odd composition addends) are marked by black dots.

• Further, the number of compositions of n without addends equal to 1 is the Fibonacci number F_n$-$1.
  E.g. out of the 8 compositions of 4 there are F₃ = 2 without 1s - they are 2+2 and the 4 itself.
  Out of the 16 compositions of 5 there are F₄ = 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.

Counting columns without green dots or strong red squares, from left side to a green trigon, gives a Pentanacci number.