For every real positive integer , define as the number of 1's that appear(s) in the decimal representation of all positive integer numbers from 1 to . For example, and . Is it true that for all positive integer ?
Bonus: Can you prove this with mathematical induction ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Let the contribution of 1's to f ( k ) from the last digit ( 1 0 0 ) be a 0 ; second last, a 1 ; third last, a 2 and so on. For example: for f ( 6 ) , a 0 = 1 from 1, while a d = 0 for d ≥ 1 , therefore, f ( 6 ) = a 0 = 1 ; and for f ( 1 6 ) , a 0 = 2 from 1 and 11, and a 1 = 7 from 10 to 16 and a d = 0 for d ≥ 2 , therefore, f ( 1 6 ) = a 0 + a 1 = 2 + 7 = 9 .
We note that for every 10, a 0 adds 1. Therefore, for 1 0 n , a 0 = 1 0 1 0 n = 1 0 n − 1 . Similarly, for every 100, a 1 adds 10 (from 10 to 19), and a 1 = 1 0 × 1 0 0 1 0 n = 1 0 n − 1 ; for every 1000, a 2 adds 100 (from 100 to 199), and a 2 = 1 0 0 × 1 0 0 0 1 0 n = 1 0 n − 1 ...; for for every 1 0 n , a n − 1 adds 1 0 n − 1 , and a n − 1 = 1 0 n − 1 × 1 0 n 1 0 n = 1 0 n − 1 ; and from the 1 0 n digit, a n = 1 . Therefore, we have:
f ( 1 0 n ) = k = 0 ∑ n a k = k = 0 ∑ n − 1 1 0 n − 1 + a n = n ( 1 0 n − 1 ) + 1