How many positive integers less than $1{,}000{,}000$ have the digit $2$ in them?
I could determine it by summing it in terms of the number of decimal places, i.e. between $999{,}999$ and $100{,}000$, etc.
Then to determine the number of numbers between $999{,}999$ and $100{,}000$ that have the digit $2$ in them would be $9^5$.
Is this correct, or am I miscounting?
Best Answer
Though not always the smartest way, such questions can mechanically be answered as follows. (In this case the "smart" way to do it is Cameron's answer. It is instructive to see that this mechanical procedure basically recovers Cameron's method.) Let $a_n$ and $b_n$ be the amounts of $n$-digit numbers that do not and do have a $2$ in them. So $a_0=1$ and $b_0=0$. These number satisfy the recurrence $$ \begin{pmatrix}a_{n+1}\\b_{n+1}\end{pmatrix}= \begin{pmatrix}9&0\\1&10\end{pmatrix} \begin{pmatrix}a_n\\b_n\end{pmatrix} $$
(Take a moment to understand what this recurrence expresses.) Now $$ \begin{pmatrix}9&0\\1&10\end{pmatrix}^6 \begin{pmatrix}1\\0\end{pmatrix}=\begin{pmatrix}531441\\468559\end{pmatrix} $$
so the answer is $468559=10^6-9^6$.