Inspired by Ikkyu San

Evaluate

1 1 3 + 2 2 9 + 3 3 27 + + 9 9 19683 11_{3} + 22_{9} + 33_{27} + \ldots + 99_{19683}

Note: 19683 = 3 9 19683 = 3^{9} . You are allowed a calculator for the final computation.


The answer is 251004.

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

Jake Lai
Jun 9, 2015

First, let's convert our sum into sigma form for convenience's sake:

1 1 3 + 2 2 9 + 3 3 27 + + 9 9 19683 = k = 1 9 k 3 k + k = k = 1 9 k 3 k + k = 1 9 k 11_{3} + 22_{9} + 33_{27} + \ldots + 99_{19683} = \sum_{k=1}^{9} k3^{k}+k = \sum_{k=1}^{9} k3^{k} + \sum_{k=1}^{9} k

The latter part of the above sum is clearly easy to handle; the former, not so much. We recall that

k = 1 n x k = x n + 1 1 x 1 (1) \sum_{k=1}^{n} x^{k} = \frac{x^{n+1}-1}{x-1} \tag{1}

To obtain a closed form for k = 1 n k x k \displaystyle \sum_{k=1}^{n} kx^{k} , we have to enlist the assistance of an unlikely piece of mathematics: calculus. (You could prove this by induction, but calculus seems more intuitive than bashing out a closed form for the sum in the dark and then inducting.)

We differentiate equation 1:

k = 1 n k x k 1 = d d x x n + 1 1 x 1 = ( n + 1 ) x n ( x 1 ) ( x n + 1 1 ) ( x 1 ) 2 \sum_{k=1}^{n} kx^{k-1} = \frac{d}{dx} \frac{x^{n+1}-1}{x-1} = \frac{(n+1)x^{n}(x-1)-(x^{n+1}-1)}{(x-1)^{2}}

To get k x k \sum kx^{k} all I need is to multiply by x x and thus we get

k = 1 n k x k = x ( n + 1 ) x n ( x 1 ) ( x n + 1 1 ) ( x 1 ) 2 = x ( n x n 1 ) x n + 1 ( x 1 ) 2 \sum_{k=1}^{n} kx^{k} = x\frac{(n+1)x^{n}(x-1)-(x^{n+1}-1)}{(x-1)^{2}} = x\frac{(nx-n-1)x^{n}+1}{(x-1)^{2}}

That was some quality magic right there, I reckon. Quality .

We have to deal with x = 3 x = 3 , and so we obtain

k = 1 n k 3 k = 3 4 ( ( 2 n 1 ) 3 n + 1 ) \sum_{k=1}^{n} k3^{k} = \frac{3}{4} \left( (2n-1)3^{n}+1 \right)

Now, putting it all together:

k = 1 9 k 3 k + k = 1 9 k = 3 4 ( ( 2 × 9 1 ) 3 9 + 1 ) + 9 ( 9 + 1 ) 2 = 251004 \sum_{k=1}^{9} k3^{k} + \sum_{k=1}^{9} k = \frac{3}{4} \left( (2 \times 9-1)3^{9}+1 \right) + \frac{9(9+1)}{2} = \boxed{251004}

Moderator note:

It would be simpler if you applied the formula for Arithmetic-Geometric Sum.

Challenge Master:

I derived k x k \sum kx^{k} for completeness's sake, but perhaps it is unnecessary. Maybe I'll do a k 2 x k \sum k^{2}x^{k} extension.

Jake Lai - 6 years ago

Log in to reply

I think you are over-complicating. S = k = 1 9 k 3 k S=\sum_{k=1}^9k3^k 3 S = k = 1 9 k 3 k + 1 3S=\sum_{k=1}^9k3^{k+1} subtracting one from the other: 2 S = 9 3 10 k = 1 9 3 k 2S=9\cdot 3^{10}-\sum_{k=1}^93^k Geometric series formula: 2 S = 9 3 10 3 10 3 2 2S=9\cdot 3^{10}-\dfrac{3^{10}-3}{2} Simplify: S = 9 3 10 2 3 10 3 4 = 251004 S=\dfrac{9\cdot 3^{10}}{2}-\dfrac{3^{10}-3}{4}=\boxed{251004}

Daniel Liu - 5 years, 11 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...