How many natural $n$ exist such that $0 \le n \lt 10^{100}$, $n \equiv 0\pmod 3$ and $n$ contains at least one 9 as a digit. When I was trying to figure out this problem I had some pretty good ideas but I am still not able to combine them into solution.

*

*It is pretty obvious how we would calculate amount of numbers divisible by three in this range:
$$\biggl\lfloor\frac{10^{100}}{3}\biggr\rfloor$$


*Also it doesn't seem to be complicated to calculate amount of numbers containing at least one 9 as a digit, we should basically calculate how many of them exist such that it has one 9, two 9's, three 9's, ..., and up to amount of digits that we have in our number. As I understand now, we should consider 99-digit numbers, 98-digit numbers, ..., 1-digit numbers cases separately.


*Let's consider k-digit numbers, we will have such an amout of numbers, that contain 9 as a digit:
$${k \choose 1} + {k \choose 2} + {k \choose 3} + \cdots + {k \choose k -1} + {k \choose k} = 2^k - 1$$
Is there any chance to combine these two ideas into full solution?
If there isn't, can you, please, share some of your ideas how to figure out this problem?
 A: There are $\lfloor{\frac{10^{100}+2}{3}}\rfloor$ if we do not require $9$ as a digit.
Then count the number that do not have $9$ as digit. It's the number of solutions of
\begin{equation}
a_1 + a_2 + \cdots + a_{100} \equiv 0 (\text{mod } 3), \forall i, a_i \in \{0, 1, \cdots, 8\} 
\end{equation}
For arbitrary $(a_1, \cdots, a_{99})$, there are exactly three choice of $a_{100}$, meaning the number is $9^{99} \cdot 3$.
Hence the result is is $\lfloor{\frac{10^{100}+2}{3}}\rfloor - 9^{99} \cdot 3$.
A: When we have exactly $1\leq k\leq99$ digits $9$ the places where these digits stand can be chosen in ${100\choose k}$ ways. There are $k':=100-k$ places left where we can write the digits $0$, $1$, $\ldots$, $8$. Choose all but the last of these digits arbitrarily. This can be done in $9^{k'-1}$ ways. Choose the last of these digits such that  sum of all $k'$ of them is divisible by $3$. This can be done in $3$ ways, in each case. The total number $N$ of admissible strings then is
$$N=\sum_{k=1}^{99}{100\choose k}\cdot9^{99-k}\cdot3 \ +1\ ,\tag{1}$$
where I have added $1$ for the number having $100$ digits $9$. Using
$$\sum_{k=0}^{100}{100\choose k}9^{-k}=\left({10\over9}\right)^{100}$$
the expression $(1)$ can be simplified so that no $\Sigma$ appears.
