combinatorics – How many natural $n$ exist such that $0 le n lt 10^{100}$, $n equiv 0pmod 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.

  1. It is pretty obvious how we would calculate amount of numbers divisible by three in this range:

  2. 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.

  3. 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} = 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?