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 OEISA000045: 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 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.
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.