Fibonacci sequences, binary numbers and compositions

From Wikiversity
Jump to navigation Jump to search

Fibonacci numbers[edit]

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

Binary and compositions 4.svg

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:

    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 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:
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 Fn1.
    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[edit]

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[edit]

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[edit]

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[edit]

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.