for each $ r$ from 0 thru 9, we compute $ N(r)$, the number of of $ k$ for which $ f(k) = r$. for $ f(k) = r$, $ k$ must contain at least $ r + 1$ digits, and at most 10 digits (in the context of this problem). the number of $ d$-digit numbers with exactly $ r$ 0's is $ 9^{d - r}\binom{d - 1}{r}$. So $ N(r) = \sum_{d = r + 1}^{10}9^{d - r}\binom{d - 1}{r}$. Thus $ S = \sum_{r = 0}^{9}\sum_{d = r + 1}^{10}2^r\cdot 9^{d - r}\binom{d - 1}{r} = \sum_{d = 1}^{10} 9^{d} \sum_{r = 0}^{d - 1}(\frac {2}{9})^r \binom{d - 1}{r} = \sum_{d = 1}^{10} 9^{d}(\frac {2}{9} + 1)^{d - 1} = \sum_{d = 1}^{10}9\cdot 11^{d - 1} = 9\cdot \frac {11^{10} - 1}{10}$.

pleurestique wrote: ... is $ 9\cdot 10^{d - r - 1}\binom{d - 1}{r}$.... why? there should be some mistakes here?

i had it right the first time. now it's back to its original purity.