I have a question in exam and I did not solve it but I'm trying to solve it and still I don't know how to solve it. It is as following: how many vectors of size n without consecutive of 11s? for example if n=2, then we have the following list: {00, 01, 10}. If n=3, then we have all binary vectors of size 3 except these three {011, 110, 111}. If n=4, then we have have binary vectors of size except 8.
n ----> number of consecutive 11's
2 ----> 1
3 ----> 3
4 ----> 8
5 ----> 19
On
An inductive argument derives the number of adminissible bit sequence for n+1:
Example:
For $n=2$, there are two sequences with end digit $..0$ and one sequence with end digit $..1$. All three sequences may be extended by appending a $0$. But only the two sequences $..0$ may be extended by appending a $1$.
If a binary string (vector) $c_1 \cdots c_n c_{n + 1}$ contains no (consecutive) substring $11$, then the same is true for the truncated substring $c_1 \cdots c_n$.
Now, given a string $c_1 \cdots c_n$, if $c_n = 0$, there are two strings, namely $c_1 \cdots c_{n - 1} 0 0$ and $c_1 \cdots c_{n - 1} 0 1$ not containing $11$ that truncate to that string, and if $c_n = 1$, there is only string, namely $c_1 \cdots 1 0 $ that truncates to that string.
This description immediately furnishes a recurrence relation: Let $a_n$ be the number of strings of length $n$ not containing $11$ and ending in $0$, and $b_n$ be the number of strings of length $n$ not containing $11$ and ending in $1$, so that $S_n := a_n + b_n$ is the total number of strings of length $n$ not containing $11$. Then, $a_n, b_n$ satisfy $$\left\{\begin{align} a_{n + 1} &= a_n + b_n = S_n\\ b_{n + 1} &= a_n \end{align}\right. .$$ Now, reindexing the first equation and substituting in the second gives $$b_{n + 1} = a_{n - 1} + b_{n - 1} = S_{n - 1},$$ and then adding this equation to the first equation above gives that $S_{n + 1} = a_{n + 1} + b_{n - 1}$ satisfies $$S_{n + 1} = S_n + S_{n - 1},$$ which is the usual Fibonacci recurrence relation. Using the $S_0 = 1$, $S_1 = 2$ gives that $S_n = F_{n + 2}$, where $F_n$ is the usual Fibonacci sequence (indexed so that $F_0 = 0$, $F_1 = 1$). So, the sequence $S_n$ is $1, 2, 3, 5, 8, 13, \ldots$, and can be written explicitly by shifting an index in Binet's Formula: $$S_n = \tfrac{1}{\sqrt{5}} \left(\phi^{n + 2} - (-\phi)^{-(n + 2)} \right).$$ For $n \geq 0$, we have $\left\vert \frac{1}{\sqrt{5}}(-\phi)^{-(n + 2)}\right\vert < \frac{1}{2}$, we can write $S_n$ compactly as $$S_n = \left[\tfrac{1}{\sqrt{5}} \phi^{n + 2} \right],$$ where $[x]$ denotes the integer nearest $x$.
Since there are $2^n$ strings of length $n$, the number of strings of length $n$ containing $11$ is $2^n - S_n$, which gives the sequence $$0, 0, 1, 3, 8, 19, \ldots$$ indicated in the question.