Using $n$ unique characters, there are exactly $n^k$ strings of length $k$.
Think of it this way:
You have $n$ choices for the first character, $n$ for the second one... $n$ for the $k$-th one.
So the amount of options is
$$\underbrace{n·n·n\ldots n}_{k\text{ times}} = n^k$$
If you want to know the amount of strings with $n$ unique characters with length up to $k$ then you need to add:
$$n^1 + n^2 + n^3 + ... + n^k = \frac{n^{k+1}-n}{n-1}$$
As Farnight and Andre noted, the number of sequences which don't contain consecutive zeroes will turn out to be Fibonacci numbers. Here is an alternate approach which yields a nice combinatorial identity for Fibonacci numbers.
Suppose we are looking at length $n$ binary sequences of $0$'s and $1$'s. Instead of thinking of it as $0$'s and $1$'s however, imagine it as $[\color{blue}{01}]$'s and $\color{red}{1}$'s with a possible $0$ at the far right. In other words, imagine we glued a 1 to the right of every 0 in order to forcibly avoid having two 0's in a row.
Either the furthest right entry in the sequence will be a 1 or a 0.
- First case: Furthest right entry is a 1 (either a part of a $\color{blue}{01}$ or a $\color{red}{1}$), E.g. $\underline{\color{blue}{01}}~\underline{\color{red}{1}}~\underline{\color{red}{1}}~\underline{\color{blue}{01}}~\underline{\color{blue}{01}}$
There can be anywhere from zero to $\lfloor\frac{n}{2}\rfloor$ number of $[\color{blue}{01}]$'s. Let $k$ be the number of $[\color{blue}{01}]$'s. Then there are $n-2k$ copies of $\color{red}{1}$'s to place. Thus, for a specific $k$, we have a total of $k+n-2k=n-k$ spaces in which we either place a $\color{blue}{01}$ or a $\color{red}{1}$ for a total of $\binom{n-k}{k}$. Ranging over all possible $k$, we find that there are $\sum\limits_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}$ possible sequences in the first case.
- Second case: Furthest right entry is a $0$. E.g. $\underline{\color{red}{1}}~\underline{\color{blue}{01}}~\underline{\color{red}{1}}~\underline{\color{red}{1}}~\underline{\color{red}{1}}~\underline{\color{red}{1}}~\underline{0}$
There can be anywhere from zero to $\lfloor\frac{n-1}{2}\rfloor$ number of $[\color{blue}{01}]$'s. Let $k$ again be the total number of $[\color{blue}{01}]$'s. Then there are $n-1-2k$ copies of $\color{red}{1}$'s to place. Thus for a specific $k$, we have a total of $k+n-1-2k=n-1-k$ spaces in which we either place a $\color{blue}{01}$ or a $\color{red}{1}$ for a total of $\binom{n-1-k}{k}$ possibilities. Ranging over all $k$, we find there are $\sum\limits_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n-1-k}{k}$ sequences in the second case.
Thus combining the cases, we have a total of $\sum\limits_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}+\sum\limits_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n-1-k}{k}$.
Noting that this answers the same question in a different form than the other answers, it gives us the identity for $n\geq 0$:
$F_{n+2} = \sum\limits_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}+\sum\limits_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n-1-k}{k}$
For your specific example of length 8 binary sequences, my form gives:
$$\sum\limits_{k=0}^{\lfloor\frac{8}{2}\rfloor}\binom{8-k}{k}+\sum\limits_{k=0}^{\lfloor\frac{8-1}{2}\rfloor}\binom{8-1-k}{k}\\
=\sum\limits_{k=0}^{4}\binom{8-k}{k}+\sum\limits_{k=0}^{3}\binom{7-k}{k}\\
=\binom{8}{0}+\binom{7}{1}+\binom{6}{2}+\binom{5}{3}+\binom{4}{4}+\binom{7}{0}+\binom{6}{1}+\binom{5}{2}+\binom{4}{3}\\
=1+7+15+10+1+1+6+10+4= 55$$
and $55$ is the $10^{th}$ Fibonacci number.
(note also, I count the Fibonacci sequence with $F_0=0, F_1=1, F_2=1,F_3=2,\dots$ whereas it seems Farnight above me counts $F_0=1,F_1=1,F_2=2,\dots$.)
A much cleaner approach which yields the same answer:
In a binary sequence of length $n$ without, there will be between $0$ and $\lfloor\frac{n}{2}\rfloor$ zeroes. Supposing that there are $k$ zeroes, then there are $n-k$ ones. Set up $n-k$ ones on a line. There are then $n-k+1$ spaces between or to the far left or right of the ones in which a zero may be placed. Pick $k$ of them to be occupied with a zero.
Ranging over all values of $k$, you get $\sum\limits_{k=0}^{\lfloor \frac{n}{2}\rfloor} \binom{n-k+1}{2}$, which again equals the same as the other answers. For $n=8$ you have $\sum\limits_{k=0}^4\binom{9-k}{k}=\binom{9}{0}+\binom{8}{1}+\binom{7}{2}+\binom{6}{3}+\binom{5}{4} = 1+8+21+20+5 = 55$
Of course, to complete the problem, note the numbers and formulae we came up with were counting how many sequences did not have consecutive zeroes. To count how many sequences do have consecutive zeroes, apply inclusion-exclusion. There are $2^n$ different length-$n$ binary sequences, so there are $2^n-F_{n+2}$ sequences which do have consecutive zeroes (or depending on how you define the starting values for the Fibonacci sequence, $2^n-F_{n+1}$). In our current example, there are then $2^8-55=256-55=201$.
To find the probability, take that number and divide by the size of the sample space, in our case $2^n$. Hence the probability for our example is $\frac{201}{256}$.
Best Answer
You can define $A(n)$ as the number of strings of length $n$ not containing three $0$'s and ending in $1$, $B(n)$ as the number of strings of length $n$ not containing three $0$'s and ending in one $0$, , $C(n)$ as the number of strings of length $n$ not containing three $0$'s and ending in two $0$'s, and $D(n)$ as the number of strings of length $n$ containing three zeros. Then $A(1)=1$, $B(1)=1$, $C(1)=0$, $D(1)=0$ and for $n>1$, $$ \begin{align} A(n)&=A(n-1)+B(n-1)+C(n-1) \\ B(n)&=A(n-1)\\ C(n)&=B(n-1)\\ D(n)&=2D(n-1)+C(n-1) \end{align} $$