Hint: Write in the base 3 and let { } be the digits which appear. The number of binomial coefficients not divisible by 3 is then given by .
Note that this works for any prime , not just 3.
Let
Let denote the number of binomial coefficients .
Now, assume that whereby
Now, we want to show that
It is obvious that , for all .
As a result, .
Then through induction, we show that for any natural n.
Then, we have
Then, when developing factors on the right-hand side, we get a sum of the factors , with a nonzero coefficient mod p. Now, since we can write any number uniquely in base p, all these factors are distinct and their coefficients mod 0 are nonzero. Thus, there are of these factors, which means that the number of binomial coefficients not divisible by p is
Do your best to finish this.