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.

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.

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.

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.