For every real positive integer \(n\), define \( f(n) \) as the number of \(1 \)'s that appear(s) in the decimal representation of all positive integer numbers from \(1\) to \(n\). For example, \( f(6) =1\) and \( f(16) = 9 \). Prove that \( f(10^n) = n(10^{n-1}) + 1\) for all positive integer \(n\).

## Comments

Sort by:

TopNewestThere is a simple combinatorial argument for this.

Notice that \(f(n)=k+f(n-1)\) where \(k\) is the number of 1s in \(n\). Now, we have only a single 1 in powers of 10, so \(f(10^n)=f(10^n-1)+1\). Now, all numbers \(\leq 10^n-1\) are at most \(n\) digit numbers (can be thought of as \(n\) digit numbers using non negative digits). Now, we need to count the numbers having 1 in their digits. Fixing 1 at one of the digits places is done in \(n\) ways and the other \(n-1\) digit places can be assigned a digit from 0 to 9 in 10 ways for each digit place, hence \(10^{n-1}\) ways. Notice that there's no problem with excessive counting or missing out on counting a few since if a number has \(m\) 1s, it is counted exactly once for fixing 1 at each of the \(m\) digit places, thus it getting counted exactly \(m\) times as desired. Now then, by the rule of product, we have \(f(10^n-1)=n10^{n-1}\) and hence we conclude that,

\[f(10^n)=n\cdot 10^{n-1}+1\] – Prasun Biswas · 2 months, 3 weeks ago

Log in to reply

– Fidel Simanjuntak · 2 months, 3 weeks ago

What do you mean, by saying "fixing" ?Log in to reply

– Fidel Simanjuntak · 2 months, 3 weeks ago

Can you give a proof for \( f(n) = k + f(n-1) \)? I still don't get it..Log in to reply

– Prasun Biswas · 2 months, 3 weeks ago

If \(f(n)\) is the number of 1s in the numbers from 1 to \(n\), then this is equivalent to the number of 1s in the numbers from 1 to \(n-1\) plus the number of 1s in \(n\), right? Denoting by \(k\) the number of 1s in \(n\), we can write \(f(n)=k+f(n-1)\).Log in to reply

– Fidel Simanjuntak · 2 months, 3 weeks ago

What do you mean, by saying "fixing" ?Log in to reply

Such "fixing" argument tend to be common in counting (enumeration) problems. – Prasun Biswas · 2 months, 3 weeks ago

Log in to reply

– Fidel Simanjuntak · 2 months, 3 weeks ago

I'm sorry for bothering you, but I still don't get this " Notice that there's no problem with excessive counting or ........". Can you help me?Log in to reply

And don't worry, if you have any further problems understanding my solution, feel free to ask. I'll try my best to help you understand. After all, a solution is no good if it can't be completely understood by the reader. ;)

PS: I'm typing from my mobile, so I might be late responding to your queries, sorry for that. – Prasun Biswas · 2 months, 3 weeks ago

Log in to reply