Digit Sum Mania

Calculus Level 3

If x x is a positive integer, define f ( x ) f(x) as the digit sum of x x . For example, f ( 2018 ) = 2 + 0 + 1 + 8 = 11 f(2018)=2+0+1+8=11 .

What is lim ⁡ n → ∞ ∑ k = 1 1 0 n k f ( k ) n 1 0 2 n \large\lim_{n\to\infty}\dfrac{\displaystyle\sum_{k=1}^{10^n}kf(k)}{n10^{2n}} where n n is an integer?

Bonus: What is lim ⁡ n → ∞ ∑ k = 1 n k f ( k ) n 2 log ⁡ 10 n \displaystyle\lim_{n\to\infty}\dfrac{\displaystyle\sum_{k=1}^{n}kf(k)}{n^2\log_{10}n} , where n n is an integer?


The answer is 2.25.

X X by X X , 17, Taiwan

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

Brian Moehring
Jul 9, 2018

Note that ∑ k = 0 1 0 n + 1 − 1 k f ( k ) = ∑ a = 0 9 ∑ k = 0 1 0 n − 1 ( 1 0 n a + k ) f ( 1 0 n a + k ) = ∑ a = 0 9 ∑ k = 0 1 0 n − 1 1 0 n a 2 + 1 0 n a f ( k ) + k a + k f ( k ) = 1 0 n ( ∑ a = 0 9 a 2 ) ( ∑ k = 0 1 0 n − 1 1 ) + 1 0 n ( ∑ a = 0 9 a ) ( ∑ k = 0 1 0 n − 1 f ( k ) ) + ( ∑ a = 0 9 a ) ( ∑ k = 0 1 0 n − 1 k ) + ( ∑ a = 0 9 1 ) ( ∑ k = 0 1 0 n − 1 k f ( k ) ) = 1 0 n ( 285 ) ( 1 0 n ) + 1 0 n ( 45 ) ( n ⋅ 1 0 n ⋅ 9 2 ) + ( 45 ) ( ( 1 0 n − 1 ) ( 1 0 n ) 2 ) + ( 10 ) ( ∑ k = 0 1 0 n − 1 k f ( k ) ) = ( 615 2 + 405 2 n ) ⋅ 1 0 2 n − 45 2 ⋅ 1 0 n + 10 ∑ k = 0 1 0 n − 1 k f ( k ) \begin{aligned} \sum_{k=0}^{10^{n+1}-1} kf(k) &= \sum_{a=0}^9 \sum_{k=0}^{10^n-1}(10^n a+k)f(10^n a+k) \\ &= \sum_{a=0}^9 \sum_{k=0}^{10^n-1}10^na^2 + 10^naf(k) + ka + kf(k) \\ &= 10^n\left(\sum_{a=0}^9 a^2\right)\left(\sum_{k=0}^{10^n-1} 1\right) + 10^n\left(\sum_{a=0}^9 a\right)\left(\sum_{k=0}^{10^n-1} f(k)\right) + \left(\sum_{a=0}^9 a\right)\left(\sum_{k=0}^{10^n-1} k\right) + \left(\sum_{a=0}^9 1\right)\left(\sum_{k=0}^{10^n-1} kf(k)\right) \\ &= 10^n(285)(10^n) + 10^n(45)\left(n\cdot 10^n \cdot \frac{9}{2}\right) + (45)\left(\frac{(10^n-1)(10^n)}{2}\right) + (10)\left(\sum_{k=0}^{10^n-1} kf(k)\right) \\ &= \left(\frac{615}{2}+\frac{405}{2}n\right) \cdot 10^{2n} - \frac{45}{2} \cdot 10^n + 10\sum_{k=0}^{10^n-1} kf(k) \end{aligned}

If we define S n = ∑ k = 0 1 0 n − 1 k f ( k ) \displaystyle S_n = \sum_{k=0}^{10^n-1} kf(k) , then we have S n + 1 = ( 615 2 + 405 2 n ) ⋅ 1 0 2 n − 45 2 ⋅ 1 0 n + 10 S n , S 0 = 0 S_{n+1} = \left(\frac{615}{2}+\frac{405}{2}n\right) \cdot 10^{2n} - \frac{45}{2} \cdot 10^n + 10S_n, \qquad S_0 = 0 and therefore S n + 1 = ∑ k = 0 n ( ( 615 2 + 405 2 k ) ⋅ 1 0 n + k − 45 2 ⋅ 1 0 n ) + 1 0 n + 1 S 0 = 615 2 ⋅ 1 0 n ⋅ 1 0 n + 1 − 1 9 + 405 2 ⋅ 1 0 n ( ∑ k = 0 n k ( 1 0 k ) ) − 45 2 ( n + 1 ) 1 0 n = 1025 3 ⋅ 1 0 2 n − 170 3 ⋅ 1 0 n − 45 2 n 1 0 n + 405 2 ⋅ 1 0 n ( ∑ k = 0 n k ( 1 0 k ) ) \begin{aligned} S_{n+1} &= \sum_{k=0}^n \left(\left(\frac{615}{2}+\frac{405}{2}k\right) \cdot 10^{n+k} - \frac{45}{2} \cdot 10^n\right) + 10^{n+1}S_0 \\ &= \frac{615}{2}\cdot 10^n \cdot \frac{10^{n+1}-1}{9} + \frac{405}{2}\cdot 10^n \left(\sum_{k=0}^n k(10^k)\right) - \frac{45}{2}(n+1) 10^n \\ &= \frac{1025}{3}\cdot 10^{2n} - \frac{170}{3}\cdot 10^n - \frac{45}{2}n 10^n + \frac{405}{2}\cdot 10^n \left(\sum_{k=0}^n k(10^k)\right) \end{aligned}

To evaluate this last series, we can do the following: ∑ k = 0 n x k = x n + 1 − 1 x − 1 ∑ k = 0 n k x k − 1 = d d x x n + 1 − 1 x − 1 = n x n + 1 − ( n + 1 ) x n + 1 ( x − 1 ) 2 ∑ k = 0 n k x k = n x n + 2 − ( n + 1 ) x n + 1 + x ( x − 1 ) 2 ∑ k = 0 n k ( 1 0 k ) = n 1 0 n + 2 − ( n + 1 ) 1 0 n + 1 + 10 9 2 = 10 9 2 ( ( 9 n − 1 ) 1 0 n + 1 ) \sum_{k=0}^n x^k = \frac{x^{n+1}-1}{x-1} \\ \sum_{k=0}^n k x^{k-1} = \frac{d}{dx} \frac{x^{n+1}-1}{x-1} = \frac{n x^{n+1} - (n+1)x^n +1}{(x-1)^2} \\ \sum_{k=0}^n k x^k = \frac{n x^{n+2} - (n+1)x^{n+1} + x}{(x-1)^2} \\ \sum_{k=0}^n k(10^k) = \frac{n 10^{n+2} - (n+1) 10^{n+1} + 10}{9^2} = \frac{10}{9^2}\left((9n-1) 10^n + 1\right) so that S n + 1 = 1025 3 ⋅ 1 0 2 n − 170 3 ⋅ 1 0 n − 45 2 n 1 0 n + 405 2 ⋅ 1 0 n ⋅ 10 9 2 ( ( 9 n − 1 ) 1 0 n + 1 ) = 950 3 ⋅ 1 0 2 n − 95 3 ⋅ 1 0 n − 45 2 n 1 0 n + 225 n 1 0 2 n S n = 11 12 ⋅ 1 0 2 n − 11 12 ⋅ 1 0 n − 9 4 n 1 0 n + 9 4 n 1 0 2 n \begin{aligned} S_{n+1} &= \frac{1025}{3}\cdot 10^{2n} - \frac{170}{3}\cdot 10^n - \frac{45}{2}n 10^n + \frac{405}{2} \cdot 10^n \cdot \frac{10}{9^2}\left((9n-1) 10^n + 1\right) \\ &= \frac{950}{3}\cdot 10^{2n} - \frac{95}{3}\cdot 10^n - \frac{45}{2}n 10^n + 225n 10^{2n} \\ S_n &= \frac{11}{12}\cdot 10^{2n} - \frac{11}{12}\cdot 10^n - \frac{9}{4}n 10^n + \frac{9}{4}n 10^{2n} \end{aligned}

We are now equipped to answer the question, as ∑ k = 1 1 0 n k f ( k ) n 1 0 2 n = 1 0 n + S n n 1 0 2 n = 11 12 ⋅ 1 0 2 n + 1 12 ⋅ 1 0 n − 9 4 n 1 0 n + 9 4 n 1 0 2 n n 1 0 2 n = 11 12 n + 1 12 n 1 0 n − 9 4 ⋅ 1 0 n + 9 4 → n → ∞ 9 4 = 2.25 \begin{aligned} \frac{\sum_{k=1}^{10^n} k f(k)}{n10^{2n}} &= \frac{10^n + S_n}{n10^{2n}} \\ &= \frac{\frac{11}{12}\cdot 10^{2n} + \frac{1}{12}\cdot 10^n - \frac{9}{4}n 10^n + \frac{9}{4}n 10^{2n}}{n 10^{2n}} \\ &= \frac{11}{12n} + \frac{1}{12n10^n} - \frac{9}{4\cdot 10^n} + \frac{9}{4} \\ &\xrightarrow{n\to\infty} \boxed{\frac{9}{4} = 2.25} \end{aligned}

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...