Number of 10 digit numbers having digits 0,1,2 so that no two 0s are consecutive. Question : Find the number of 10 digit numbers having digits 0,1,2 so that no two 0s are consecutive. (here a number cannot begin with 0)
And here's my attempt : Let $b_n$ denote the number of such numbers with length $n$ and ending with $1,2$ (here the leading digit cannot be $0$) and $a_n$ the number of numbers ending with $0$.
Let $c_n=a_n+b_n$, we want to find $c_{10}$.
Note that $$a_n=b_{n-1}$$ since the second last digit of this thing should be a $1$ or a $2$. Also, $b_n=b_{n-1}+a_{n-1}=c_{n-1}$. It suffices to find $b_{11}$ but $b_n=b_{n-1}+b_{n-2}$ so it is easy to compute.
Note: I am not looking for the answer, just to check if my approach is correct and if better approaches exist
EDIT :  I guess this is a slightly less confusing way : denote by $a_n,b_n,c_n$ number of "numbers" of length $n$ ending with $0,1,2$ respectively, and $d_n=a_n+b_n+c_n$. Clearly, $b_n=c_n$ and $a_n=b_{n-1}+c_{n-1}=2b_{n-1}$. Further $b_n=c_n=a_{n-1}+b_{n-1}+c_{n-1}=d_{n-1}$. But $b_n=2b_{n-2}+2b_{n-1}$ which is easy to compute
 A: The recurrence for $b_n$ is $b_n = 2 c_{n-1} = 2b_{n-1} + 2a_{n-1} = 2b_{n-1}+2b_{n-2}$ since given any number of length $n-1$ you can construct two numbers of length $n$ ending with $1$ or $2$.
A: The method here is to use something along the line of
1, 2  can have trailing 0, 1, 2   ie y
0     can have trailing    1, 2   ie x

If we suppose these numbers are x, y at some point, the next iteration gives 3x+2y, or
    1   2    3    4    5    6
x   0   2    6   14   34   82
y   2   6   14   34   82  198

This is an alternation of the silver series, with steps at 1+sqrt(2).
The series to extend is the even numbers, 2, 6,34,198  at the rate of t(n+1)=6t(n)-t(n-1).
The value of this is isoquad(6,5,2,6) = 6726.
The 6 comes from that this is t(n+1)=6t(n)-t(n-1). The 5 is the value to be found (col 5 = 10 digits), the 2, 6 are the leader values for t0 and t1 resp.
isoquad, written in rexx, is http://zabrodsky-rexx.byethost18.com/aat/a_memfis.html
The process is indeed correct, but we looked on the wrong cell for the answer.  The number presented is in the cell representing numbers starting with 1,2, and ending in a non-zero digit at 10 digits.
Repeating the calculation for 11 digits gives 16238.
Thanks to Barry Cipra for pointing the error exists.
A: Here's a different approach: The number of ways you can pick where to put $k$ $0$'s with none at the beginning and none adjacent, is $10-k\choose k$.  This comes from stars-and-bars counting of nonnegative solutions to $(x_1+1)+(x_2+1)+\cdots+(x_k+1)+x_{k+1}=10-k$. So a workable formula is
$$2^{10}{10\choose0}+2^9{9\choose1}+2^8{8\choose2}+2^7{7\choose3}+2^6{6\choose4}+2^5{5\choose5}$$
This easily generalizes to $n$-digit numbers; whether it's better than a recursive approach is debatable.
A: According to comment given by OP , he is asking to find the value of $a_{10}$ , but as he said , it is lazy to calculate this value. So , acccording to this reply , i assume that OP understand that how $a_n=2a_{n-1}+2a_{n-2}$ is obtained where $a_0=1,a_1=2 ,a_2=6$ .
Now, i will compute the value of $a_{10}$ using generating functions to make it easy for OP.
$\color{green}{\text{1.Step-)}}$ Lets define an ordinary generating function ,say $A(x)$, then $A(x)=\sum_{n=0}^\infty a_nx^n$
$\color{green}{\text{2.Step-)}}$ Multiply each term in this recurrence relation by $\sum_{n=0}^\infty x^n$ and try to write this recurrence relation in terms of $A(x)$.
$\color{green}{\text{3.Step-)}}$ $\sum_{n=0}^\infty a_nx^n=2\sum_{n=0}^\infty a_{n-1}x^n+2\sum_{n=0}^\infty a_{n-2}x^n$
$\color{green}{\text{4.Step-)}}$ Lets make a change in the bases to make it easy such that $$\sum_{n=0}^\infty a_nx^n=2\sum_{n=0}^\infty a_{n-1}x^n+2\sum_{n=0}^\infty a_{n-2}x^n \color{red}{\rightarrow }\sum_{n=0}^\infty a_{n+2}x^n=2\sum_{n=0}^\infty a_{n+1}x^n+2\sum_{n=0}^\infty a_{n}x^n$$
$\color{green}{\text{5.Step-)}}$ Lets check over each terms such that

*

*$2\sum_{n=0}^\infty a_{n}x^n =2A(x)$


*$2\sum_{n=0}^\infty a_{n+1}x^n= 2\frac{A(x)-1}{x}=\frac{2A(x)-2}{x}$


*$\sum_{n=0}^\infty a_{n+2}x^n = \frac{A(x) -a_1x-1}{x^2}$ where $a_1 =2$ ,so it is equal to $\frac{A(x) -2x-1}{x^2}$
Now we obtain that $$\frac{A(x) -2x-1}{x^2} =\frac{2A(x)-2}{x} + 2A(x) $$
By solving the equation , $$A(x) = \frac{1}{1-2x-2x^2}$$
We wrote our recurrence realiton in terms of series , so lets CALCULATE it using wolfram-alpha.
$$1+2x+6x^2 +16x^3 +44x^4 +120x^5 +...+6688x^9 +\color{blue}{18272}x^{10}+ 49920x^{11}+...$$
As you see , the coefficient of $x^{10}$ is $18,272$ , you can see the other values ,as well. For example , $a_{16}$is equal to coefficient of $x^{16}$ , so it is $7,598,336$
