True or Not?

Algebra Level 3

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

Bonus: Can you prove this with mathematical induction ?


Try another problem on my set! Warming Up and More Practice
Cannot be determined False True

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.

1 solution

Chew-Seong Cheong
May 27, 2017

Let the contribution of 1's to f ( k ) f(k) from the last digit ( 1 0 0 ) (10^0) be a 0 a_0 ; second last, a 1 a_1 ; third last, a 2 a_2 and so on. For example: for f ( 6 ) f(6) , a 0 = 1 a_0=1 from 1, while a d = 0 a_d = 0 for d 1 d \ge 1 , therefore, f ( 6 ) = a 0 = 1 f(6) = a_0 = 1 ; and for f ( 16 ) f(16) , a 0 = 2 a_0 = 2 from 1 and 11, and a 1 = 7 a_1 = 7 from 10 to 16 and a d = 0 a_d = 0 for d 2 d \ge 2 , therefore, f ( 16 ) = a 0 + a 1 = 2 + 7 = 9 f(16) = a_0+a_1 = 2+7 = 9 .

We note that for every 10, a 0 a_0 adds 1. Therefore, for 1 0 n 10^n , a 0 = 1 0 n 10 = 1 0 n 1 a_0 = \dfrac {10^n}{10} = 10^{n-1} . Similarly, for every 100, a 1 a_1 adds 10 (from 10 to 19), and a 1 = 10 × 1 0 n 100 = 1 0 n 1 a_1 = 10 \times \dfrac {10^n}{100} = 10^{n-1} ; for every 1000, a 2 a_2 adds 100 (from 100 to 199), and a 2 = 100 × 1 0 n 1000 = 1 0 n 1 a_2 = 100 \times \dfrac {10^n}{1000} = 10^{n-1} ...; for for every 1 0 n 10^n , a n 1 a_{n-1} adds 1 0 n 1 10^{n-1} , and a n 1 = 1 0 n 1 × 1 0 n 1 0 n = 1 0 n 1 a_{n-1}= 10^{n-1} \times \dfrac {10^n}{10^n} = 10^{n-1} ; and from the 1 0 n 10^n digit, a n = 1 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 f(10^n) = \sum_{k=0}^n a_k = \sum_{k=0}^{n-1} 10^{n-1} + a_n = \boxed{n(10^{n-1}) + 1}

Nice! Thanks for the great proof, as I expected, sir!

Fidel Simanjuntak - 4 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...