Hi:

And interesting it is indeed!

For a 1 digit number, we see 9 once.

2 digits: __ __, __ __ , __ __ The 9 can show up in the 1st, 2nd, or both places. If it only appears in one position, then the other position can be filler by any of 9 digits. And it can show in both places only one way, i.e., 99, where we see the 9 twice. The total "n(2)" = (2c1)X9^1 + 2(2c2)X9^0 = 20.

Employing the same logic gives,

n(3) = (3c1)X9^2 + 2(3c2)X9^1 + 3(3c3)x9^0 = 300.

n(4) = (4c1)X9^3 + 2(4c2)X9^2 + 3(4c3)x9^1 + 4(4c4)x9^0 = 4000

.

.

.

n(k)= (kc1)x9^(k-1) + 2(kc2)x9^(k-2) +...+k(kck)x9^(k-k) = kX10^(k-1).

Hence, as the number of appearances in {0,1,2,...,10^9} is the same as those in {0,1,2,...,999999999}, the solution of your specific question is,

n(9) = 9X10^8 or 900,000,000.

With regard to proof, it should be fairly short business to demonstrate that

n(k)= kX10^(k-1) implies n(k+1)=(k+1)X10^[(k-1)+1] for k in {1,2,3,...}, making induction a reasonably "clean" course of action. ...best laid plans...

Regards,

Rich B.