A binary sequence is a sequence of 1s and 0s, and there are $2^n$ such sequences of length $n$.
Define the "pattern" as the number of consecutive $1$s in the sequence. For example, when $n=5$, the sequence $11010$ has pattern $[2,1]$ and the sequence $10011$ has pattern $[1,2]$. These two are of different patterns.
When $n=3$, there are $5$ patterns for total $2^3$ sequences:
[0]: 000
[1]: 001, 010,100
[2]: 011,110
[1,1]: 101
[3]: 111
So, the question is: for binary sequence with length $n$, how many patterns are there? Denoted by $a_n$.
It seems to be related to the Fibonacci numbers. If true, please help to prove it.
Thank you.
Best Answer
First of all, note the following formula for the sum of the first n fibonacci numbers:
$F_1 + F_2 + ... + F_n = F_{n+2} - 1$
This can be seen easily by induction on n.
Now, consider your case.
Assume inductively that number of patterns, $a_n$ = $F_{n+2}$ for n <= some $n_0$.
Any pattern must begin with one of $0, 1, 2, 3, ... n$
Each pattern that begins with say 3 can be uniquely identified with a sequence that starts with $1110$. Number of such sequences = $a_{n-4}$.
Using a similar logic, number of patterns that begin with i = $a_{n-1-i}$. This goes on for 0< i < $n-1$. For i = n, we have a single possible sequence with n 1's. For i = n-1, $a_0$ can be taken as 1 for simplicity. (number of patterns with 0 elements = 1, which is just $|\{0\}|$). This also satisfies $a_i = F_{i+2}$ as $F_2 = 1$. For i=0, We count the all zeroes case, adding another 1.
Now, each of the cases we have found so far are disjoint from each other. We can add them up.
$a_n = a_{n-2} + a_{n-3} + ... + a_1 + a_0 + 1 + 1$
By induction hypothesis, this becomes:
$a_n = F_{n} + F_{n-1} + ... + F_3 + F_2 + F_1 + 1$
So $a_n = (F_{n+2} - 1) + 1$
(by the formula for sum of first n fibonacci numbers).
This gives us $a_n = F_{n+2}$, like we wanted.