Today we look at another puzzle. Let f(n) be the number of ones that occur in the decimal representations of all the numbers from 1 to n. For example, this gives f(8) = 1, f(9) = 1, f(10) = 2, f(11) = 4,  and f(12) = 5. Determine the value of f(10 to the power 100) written as f(10^100).
Since the number of 1s are easy to enumerate, we simply list the pattern we see:
f(10^1) = 2 = 1 + 1 ( we have to add 1 for the numbers that start with 1 and are followed by consecutive zeros as the last number for the given range)
f(10^2) = 21 = 20 + 1 ( 9 horizontal 1 and nine vertical 1 + both together + 1 which we calculate as
                                        1 times 2 Choose 1 times 9^1+
                                         2 times 2 Choose 2 times 9^0) +
                                         1 for the number 1 and trailing zeros.
f(10^3) = 301 = 300 + 1 (Out of three digits, numbers with only 1 is  1 times 3 Choose 1 times 9^2)
                                        (Out of three digits, numbers with two ones is 2 times 3 Choose 2 times 9^1)
                                        (Out of three digits, numbers with three ones is 3 times 3 Choose 3 times 9^0)
                                         +1 for the number 1 and trailing zeros.
Therefore we can start writing the combinatorics for 10 power 100
f(10^100) = 1 times 100Choose1 times 9Power99 +
                         2 times 100Choose2 times 9Power98 +
                          3 times 100Choose3 times 9Power97 +

                          99 times 100Choose99 times 9Power1 +
                          100 times 100Choose100 times 9Power0 +
                           1 for the number 1 and all trailing zeros
                 =

We can express this as 1+Sum(i times n-Choose-i) times Power(9, n-i)