Binary sequence count of unique patterns 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.
 A: 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.
A: For those who may concern, here are some additional notes on the problem.
Let's have a close look at the $ 2^n $ sequences of length n. If we shrink the extra zeros out of each sequence, resulting in sequences containing no two consecutive zeros nor zeros at both the left and right ends, just like what Christian's answer suggested, then we have a shrinked version (denoted by $SS_n$) of the original $S_n$. Each item in $SS_n$ represents a unique pattern. The length of $SS_n$ is the total count of unique patterns, the final answer.
For the sequence of all 0's in $S_n$, it can be shrinked to  $\varnothing$  in $SS_n$, representing pattern [0].
For other item in $SS_n$, their count is the number of "sequences of length n containing no two consecutive zeros nor zeros at both ends". Christian has given a proof. Here is another one using the same denotion $s_n$. Since the number of "sequences of length n containing no two consecutive zeros" has been proved to be $F_{n+2}$, and $s_n$ is the $n-2$ case on it because the beginning and ending digits have to be 1. Thus $s_n = F_{(n-2)+2} =F_n$, Q.E.D.
Here is another perspective on the initial question using Pascal Triangle. $s_n$ is the sums of its "shallow" diagonals.

$P_i$, the sum of row $i$ of Pascal Triangle, is the number of unique patterns of sequences with $i$ 1's totally, given enough sequence length. It is also the number of compositions of integer $i$. And $P_i=2^{i-1}$
$P_{i, j}$, the $j$th item in the $i$th row of Pascal Triangle, is the count of patterns with $j$ items among total $P_i$ .
e.g., i=3, the 3rd row is 1, 2, 1.
There are $P_3=1+2+1=4$ unique patterns of sequences with 3 1's totally, given enough sequence length: [3], [1,2],[2,1],[1,1,1]. These are also patterns whose items' sum are 3, i.e. compositions of 3.
$P_{3, 1}$ is the number of patterns with 1 item among them, i.e. [3]. $P_{3, 2}$ is the number of patterns with 2 item among them: [1,2] and [2,1].
Now, back to the "shallow" diagonals, every time when the sequence length $n$ increase into $n+1$, new oppotunities open for $P_{i,j}$s which were not counted in $a_n$ because there were not enough length to expand (i.e. adding 0's). These $P_{i,j}$ items compose the $i$th "shallow" diagonal.
A: Denote by $S_n$ $(n\geq1)$ the set, and by $s_n$ the number of binary sequences of length $n$ containing no two consecutive zeros nor zeros at the ends. Then $s_1=s_2=1$, $s_3=2$, and one has the recursion formula
$$s_n=s_{n-1}+s_{n-2}\qquad(n\geq3)\ .$$
Proof. A word $w\in S_n$  ends with $11$ or with $01$. In the first case the word $w'$ obtained by dropping the last $1$ is in $S_{n-1}$, and in the second case the word $w''$ obtained by dropping the final $01$ is in $S_{n-2}$. Conversely, appending $1$ to a word in $S_{n-1}$ or $01$ to a word in $S_{n-2}$ produces each $w\in S_n$ exactly once.
It follows that $s_n=f_n$ (the $n$'th Fibonacci number) for all $n\geq1$. 
Now $s_n$ counts the number of your "patterns" (apart from the empty pattern) requiring at least $n$ letters to write down. But each pattern can as well be packed into  longer words by padding it with extra zeros. It follows that the number $p_n$  of patterns that can be packed into an $n$-letter word  is given by
$$p_n=1+\sum_{k=1}^n s_k=1+\sum_{k=1}^n f_k=1+(f_{n+2}-1)=f_{n+2}\ .$$
