two successive zeros I am trying to solve a programming problem, but i dont know how to find number of numbers that dont contain two successive zeros. Please help me. 
for deeper understanding i included part of the problem in message. 
Let’s consider K-based numbers, containing exactly N digits. We define a number to be valid if its K-based notation doesn’t contain two successive zeros. For example:
1010230 is a valid 7-digit number;
1000198 is not a valid number; 
0001235 is not a 7-digit number, it is a 4-digit number.

Thank you!
 A: Let $L(n)$ be the number of strings with an alphabet of $K$ characters that don't end in $0$ and don't have two successive $0$'s.  Let $M(n)$  be the number of strings with an alphabet of $K$ characters that end in $0$ and don't have two successive $0$'s.  Then $L(1)=K-1, M(1)=0$(because of no leading zero)$, L(n)=(K-1)(L(n-1)+M(n-1)), M(n)=L(n-1)$ the third because you can add any non-zero character to an acceptable string to get an acceptable string that doesn't end in zero, and you can add a zero to any acceptable string that doesn't end in zero to get an acceptable string that ends in zero.  This makes a $2 \times 2$ matrix that takes $(L(n)\  M(n))^T$ to $(L(n+1)\  M(n+1))^T$ so you might find the eigenvalues and eigenvectors of that matrix.  To get the final answer, you take $L(n)+M(n)$.
Added:  to get a closed form we represent the recursion as $$\begin {pmatrix} L(n) \\ M(n) \end {pmatrix}=\begin {pmatrix} 9 & 9 \\ 1 & 0 \end {pmatrix}\begin {pmatrix} L(n-1) \\ M(n-1) \end {pmatrix}$$
This has eigenvalues $\lambda_{\pm}=\frac 32 (3 \pm \sqrt {13})$ with corresponding eigenvectors $\begin {pmatrix} 9+3\sqrt {13} \\ 1 \end {pmatrix},\begin {pmatrix} 9-3\sqrt {13} \\ 1 \end {pmatrix}$.  Starting from $\begin {pmatrix} L(0) \\ M(0) \end {pmatrix}=\begin {pmatrix} K-1 \\ 0 \end {pmatrix}$ we get  $$\begin {pmatrix} L(n) \\ M(n) \end {pmatrix}= \frac{K-1}{6\sqrt{13}}\begin {pmatrix} 9+3\sqrt {13} \\ 1 \end {pmatrix}\lambda_+^n-\frac{K-1}{6\sqrt{13}}\begin {pmatrix} 9-3\sqrt {13} \\ 1 \end {pmatrix}\lambda_-^n$$
A: To count the $k$-ary strings (that is, strings on the alphabet $0, 1, 2, \ldots, k-1$) of length $n$ with no two $0$'s in a row that do not start with $0$, first choose the number of nonzero digits we would like to have - call this $m$.  Then choose any string on $m$ digits using the digits $1, 2, \ldots, k-1$ (but not $0$).  Now choose any subset of size $n-m$ of these digits, and insert a $0$ to the right of each.  The result is a string that does not start with $0$ and has no two $0$'s adjacent, and every such string is attained uniquely with this process.  This gives the answer
$$\sum_{m=0}^n (k-1)^m {m \choose {n-m}}.  $$
