Permutation & Combination - how many numbers smaller than $2.10^8$ and are divisible by $3$ can be written by means of the digits $0$,$1$ and $2$ How many numbers smaller than $2\times10^8$ and divisible by $3$ can be written by means of the digits $0$,$1$ and $2$?
Left zero padding not allowed.
I am getting this as -
$3$ digits - $2\cdot3 = 6$
$4$ digits - $2\cdot3\cdot3 = 18$
$5$ digits - $2\cdot3\cdot3\cdot3 = 54$
$6$ digits - $2\cdot3\cdot3\cdot3\cdot3 = 162$
$7$ digits - $2\cdot3\cdot3\cdot3\cdot3\cdot3\cdot3 = 486$
$8$ digits - $2\cdot3\cdot3\cdot3\cdot3\cdot3\cdot3\cdot3 = 1458$  
From $10^8$ to $2\times10^8$ - $2\cdot3\cdot3\cdot3\cdot3\cdot3\cdot3
\cdot3\cdot3/2 = 2187$
I get $4371$ as the answer, but in the book the result is $4351$, am I making an error somewhere?
 A: We solve the simpler problem of counting the numbers from $0$ to $10^8-1$ of the right shape that are divisible by $3$. We do allow zero padding to make all the numbers into $8$-digit numbers. This makes no difference to the count.
The same method works for the other half of our interval. 
We use a general approach, though the particular case is too simple and quickly collapses. One could then in hindsight give a slicker argument, but we won't do that. 
Let $a(n)$ be the number of $n$-digit numbers that use only $0$, $1$, and $2$ and are divisible by $3$. Let $b(n)$ be the number of $n$-digit numbers, of the right form, that give remainder $1$ on division by $3$, and let $c(n)$ be the same thing, except for remainder $2$. We have $a(1)=b(1)=c(1)=1$. Note that
$$a(n+1)=a(n)+b(n)+c(n).$$
This is because a qualifying $n+1$ digit number can be obtained by appending a $0$ to an $n$-digit number divisible by $3$, or a $2$ to an $n$-digit number that has remainder $1$, or a $1$ to an $n$-digit number that has remainder $2$. Similarly, we have $b(n)=a(n)+b(n)+c(n)$ and $c(n)=a(n)+b(n)+c(n)$. 
It follows that $a(2)=b(2)=c(2)=3$, and $a(3)=b(3)=c(3)=9$, and so on. Thus $a(8)=3^7$. 
For the numbers from $1\times 10^8$ to $2\times 10^8-1$, do the same calculation for numbers of the form $1x$, where $x$ is a (padded) $8$-digit number. 
