It Doesn't Telescope

Algebra Level 3

S = 1 2 10 + 2 × 1 2 + 2 2 1 0 2 + 3 × 1 2 + 2 × 2 2 + 3 2 1 0 3 + S= \frac{1^{2}}{10}+\frac{2 \times 1^{2}+2^{2}}{10^{2}}+\frac{3 \times 1^{2}+2 \times 2^{2}+3^{2}}{10^{3}}+\cdots

The sum S S defined above is an infinite sum whose n th n^\text{th} term is n × 1 2 + ( n 1 ) × 2 2 + ( n 2 ) × 3 2 + + n 2 1 0 n \dfrac{n \times 1^{2}+(n-1) \times 2^{2}+(n-2) \times 3^{2} + \cdots + n^{2}}{10^{n}} for n = 1 , 2 , n=1,2,\ldots .

If S S can be expressed in the form a b \frac{a}{b} , where a a and b b are coprime positive integers, find a + b a+b .


Inspiration .


The answer is 70049.

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.

3 solutions

Mark Hennings
Jan 31, 2017

Note that A ( x ) = n = 1 ( j = 1 n ( n + 1 j ) j 2 ) x n = 1 12 n = 1 n ( n + 1 ) 2 ( n + 2 ) x n = 1 12 n = 1 n ( n + 1 ) ( n + 2 ) ( n + 3 ) x n 1 6 n = 1 n ( n + 1 ) ( n + 2 ) x n = 1 12 × 24 x ( 1 x ) 5 1 6 × 6 x ( 1 x ) 4 = x ( 1 + x ) ( 1 x ) 5 \begin{aligned} A(x) & = \; \sum_{n=1}^\infty \left(\sum_{j=1}^n (n+1-j)j^2\right)x^n \; = \; \tfrac1{12}\sum_{n=1}^\infty n(n+1)^2(n+2)x^n \\ & = \tfrac1{12}\sum_{n=1}^\infty n(n+1)(n+2)(n+3)x^n - \tfrac16\sum_{n=1}^\infty n(n+1)(n+2)x^n \\ & = \tfrac{1}{12} \times 24x(1-x)^{-5} - \tfrac16 \times 6x(1-x)^{-4} \; = \; \frac{x(1+x)}{(1-x)^5} \end{aligned} for all 1 < x < 1 -1 < x < 1 , using standard formulae for the Binomial expansions of negative powers of 1 x 1-x . Thus A ( 1 10 ) = 11000 59049 A\big(\tfrac{1}{10}\big) = \tfrac{11000}{59049} , making the answer 70049 \boxed{70049} .

Moderator note:

The ease of summing up n ( n + 1 ) ( n + 2 ) ( n + 3 ) x n \sum n(n+1)(n+2)(n+3) x^n can be seen in many areas of mathematics, and provides a glimpse into the linkages across these different areas:

Nice! What theorem did you use to break down the second line? I've never seen that before and I can't find where you got it from.

Brandon Monsen - 4 years, 4 months ago

Log in to reply

I would have done it this way:

It's easy to see that d 4 d x 4 x n + 3 = n ( n + 1 ) ( n + 2 ) ( n + 3 ) x n 1 \dfrac{d^4}{dx^4} x^{n+3} = n(n+1)(n+2)(n+3) x^{n-1} , then

n = 1 n ( n + 1 ) ( n + 2 ) ( n + 3 ) x n = x n = 1 n ( n + 1 ) ( n + 2 ) ( n + 3 ) x n 1 = x n = 1 d 4 d x 4 x n + 3 = x [ d 4 d x 4 n = 1 x n + 3 ] = x [ d 4 d x 4 x 4 1 x ] = 24 x ( 1 x ) 5 . \begin{aligned} \sum_{n=1}^\infty n(n+1)(n+2)(n+3)x^n &= & x \sum_{n=1}^\infty n(n+1)(n+2)(n+3)x^{n-1} \\ &=& x \sum_{n=1}^\infty \dfrac{ d^4}{dx^4} x^{n+3} \\ &=& x \cdot \left [ \dfrac{ d^4}{dx^4} \sum_{n=1}^\infty x^{n+3} \right ] \\ &=& x \cdot \left [ \dfrac{ d^4}{dx^4} \dfrac{x^4}{1-x} \right ] \\ &=& \dfrac{24x}{(1-x)^5} .\\ \end{aligned}

Likewise, we can evaulate the other series to get n = 1 n ( n + 1 ) ( n + 2 ) x n = 6 x ( 1 x ) 4 \displaystyle \sum_{n=1}^\infty n(n+1)(n+2)x^n = \dfrac{6x}{(1-x)^4} .

Pi Han Goh - 4 years, 4 months ago

( 1 x ) k = n = 0 ( n + k 1 k 1 ) x n x ( 1 x ) k = n = 1 ( n + k 2 k 1 ) x n \begin{aligned} (1-x)^{-k} & = \; \sum_{n=0}^\infty \binom{n+k-1}{k-1}x^n \\ x(1-x)^{-k} & = \sum_{n=1}^\infty \binom{n+k-2}{k-1}x^n \end{aligned} for any k N k \in \mathbb{N} . Prove the first by induction on k k , differentiating the series term-by-term. The second is a simple rewrite of the first.

Mark Hennings - 4 years, 4 months ago

negative binomial theorem

Calvin Lin Staff - 4 years, 4 months ago

Log in to reply

It always strikes me as odd to call it the Negative Binomial Theorem, when the formula involved works for all real indices! OK, the formula is nicely expressible in terms of ordinary Binomial coefficients when the index is a negative integer, but that is just book-keeping.

Mark Hennings - 4 years, 4 months ago
Brandon Monsen
Jan 30, 2017

Although I'm not actually sure if the series telescopes, we can solve this problem fairly easily by iterating through several other progressively simpler series:

Let A = 1 2 10 + 1 2 + 2 2 1 0 2 + 1 2 + 2 2 + 3 2 1 0 3 + A=\frac{1^{2}}{10}+\frac{1^{2}+2^{2}}{10^{2}}+\frac{1^{2}+2^{2}+3^{2}}{10^{3}}+\ldots .

Then A + A 10 + A 1 0 2 + = S ( 10 9 ) A = S A+\frac{A}{10}+\frac{A}{10^{2}}+ \ldots = S \Rightarrow \left( \frac{10}{9} \right)A=S

Let B = 1 2 10 + 2 2 1 0 2 + 3 2 1 0 3 + B=\frac{1^{2}}{10}+\frac{2^{2}}{10^{2}}+\frac{3^{2}}{10^{3}}+ \ldots

We can see that A A 10 = B A = ( 10 9 ) B ( 10 9 ) 2 B = S A-\frac{A}{10}=B \Rightarrow A=\left( \frac{10}{9} \right)B \Rightarrow \left( \frac{10}{9} \right)^{2}B=S

Let C = 1 10 + 3 1 0 2 + 5 1 0 3 + 7 1 0 4 + C=\frac{1}{10}+\frac{3}{10^{2}}+\frac{5}{10^{3}}+\frac{7}{10^{4}} + \ldots

We can see that B B 10 = C B = ( 10 9 ) C ( 10 9 ) 3 C = S B-\frac{B}{10}=C \Rightarrow B=\left( \frac{10}{9} \right)C \Rightarrow \left( \frac{10}{9} \right)^{3}C=S

Let D = 2 1 0 2 + 2 1 0 3 + 2 1 0 4 + 2 1 0 5 + = 2 90 D=\frac{2}{10^{2}}+\frac{2}{10^{3}}+\frac{2}{10^{4}}+\frac{2}{10^{5}}+ \ldots = \frac{2}{90}

We can see that C C 10 = 1 10 + D = 11 90 C = 11 9 2 S = 11 × 1 0 3 9 5 = 11000 59049 C-\frac{C}{10}=\frac{1}{10}+D =\frac{11}{90} \Rightarrow C=\frac{11}{9^{2}} \Rightarrow S=\frac{11 \times 10^{3}}{9^{5}}=\frac{11000}{59049}

We see from the exponential form of the fraction that 11000 11000 and 59049 59049 are co-prime, and so our answer is 11000 + 59049 = 70049 11000+59049=\boxed{70049}

Note that this only holds true if S , A , B , C , D S,A,B,C,D are convergent. Since the system implies that S > A > B > C > D S>A>B>C>D , it will suffice to show that S S is convergent.

n × 1 2 + ( n 1 ) × 2 2 + ( n 2 ) × 3 2 + + n 2 1 0 n ( n + 1 ) n 3 2 × 1 0 n \frac{n \times 1^{2}+(n-1) \times 2^{2}+(n-2) \times 3^{2} + \ldots + n^{2}}{10^{n}} \leq \frac{(n+1)n^{3}}{2 \times 10^{n}} for all n = 1 , 2 , 3 , n=1,2,3, \ldots

Since the infinite series corresponding to a n = ( n + 1 ) n 3 2 × 1 0 n a_{n}=\frac{(n+1)n^{3}}{2 \times 10^{n}} converges by the ratio test, we can conclude that S , A , B , C , D S,A,B,C,D all converge.

For completeness, we should show that A, B, C, D are finite, since A = B = C = D = A = B=C=D=\infty also satisfies the system of equations.

Calvin Lin Staff - 4 years, 4 months ago

Log in to reply

Yes, good point. Would it suffice to show that since;

n × 1 2 + ( n 1 ) × 2 2 + ( n 2 ) × 3 2 + + n 2 1 0 n ( n + 1 ) n 3 2 × 1 0 n \frac{n \times 1^{2}+(n-1) \times 2^{2}+ (n-2) \times 3^{2}+ \ldots +n^{2}}{10^{n}} \leq \frac{(n+1)n^{3}}{2 \times 10^{n}} for all n = 1 , 2 , . . . n=1,2,...

whose infinite sum converges by the ratio tests, then S S must converge.

We can then work through partial sums and see that S > A > B > C > D S>A>B>C>D and so A , B , C , D A,B,C,D must also converge?

Brandon Monsen - 4 years, 4 months ago

Log in to reply

It is sufficient to show that A is finite, from which it follows through this system of equations that the rest are finite.

Calvin Lin Staff - 4 years, 4 months ago

Log in to reply

@Calvin Lin I added that to the solution. Why would it not suffice to show that S S is finite, since the system shows that S > A > B > C > D S>A>B>C>D ?

Brandon Monsen - 4 years, 4 months ago

Log in to reply

@Brandon Monsen I misread your comment. I thought you were asking if we also needed to show that S converges, after we've shown that A converges.

Calvin Lin Staff - 4 years, 4 months ago

I want to thank you for the problem. I spent the better part of two days working through it with little background in infinite sums, recognizing as many underlying trends going from term to term, and organizing them into a neat little self referential equation in terms of S, and I'm very proud to have come to the right answer. This kind of brain stretching is exactly what I want out of a website like this. More please.

Max Montiel - 3 years, 3 months ago

Log in to reply

Well done discovering all of these things for yourself, that's no small feat! You must've been so satisfied when it all finally came together :)

Brandon Monsen - 3 years, 3 months ago

First we find the sum n × 1 2 + ( n 1 ) × 2 2 + ( n 2 ) × 3 2 + + 1 × n 2 = k = 1 n ( n k + 1 ) k 2 n\times 1^2+(n-1)\times 2^2+(n-2)\times 3^2+\cdots+1\times n^2=\sum\limits_{k=1}^n (n-k+1)k^2 . To do this, we start with the sum k = 1 n ( n k + 1 ) ( ( k + 1 ) 3 k 3 ) = 1 3 + 2 3 + + n 3 + n ( n + 1 ) ( n + 2 ) = 1 4 n ( n + 1 ) ( n 2 + 5 n + 8 ) \sum\limits_{k=1}^n(n-k+1)((k+1)^3-k^3)=1^3+2^3+\cdots+n^3+n(n+1)(n+2)=\frac14 n(n+1)(n^2+5n+8) . On the other hand k = 1 n ( n k + 1 ) ( 3 k 2 + 3 k + 1 ) = 3 k = 1 n ( n k + 1 ) k 2 + 3 k = 1 n ( n k + 1 ) k + k = 1 n ( n k + 1 ) \sum\limits_{k=1}^n (n-k+1)(3k^2+3k+1)=3\sum\limits_{k=1}^n (n-k+1)k^2+3\sum\limits_{k=1}^n (n-k+1)k+\sum\limits_{k=1}^n (n-k+1) . So, we obtain k = 1 n ( n k + 1 ) k 2 = 1 3 ( 1 4 n ( n + 1 ) ( n 2 + 5 n + 8 ) 1 2 n ( n + 1 ) ( n + 2 ) 1 2 n ( n + 1 ) ) = 1 12 n ( n + 1 ) 2 ( n + 2 ) \sum_{k=1}^n (n-k+1)k^2=\frac13\Big(\frac14 n(n+1)(n^2+5n+8)-\frac12n(n+1)(n+2)-\frac12n(n+1)\Big)=\frac1{12}n(n+1)^2(n+2)

Now, we consider the power series 1 12 n = 1 n ( n + 1 ) 2 ( n + 2 ) x n . \frac1{12}\sum_{n=1}^\infty n(n+1)^2(n+2)x^n. Its radius of convergence is 1 1 . We use derivative 1 12 n = 1 n ( n + 1 ) ( x n + 2 ) = 1 12 ( n = 1 n ( n + 1 ) x n + 2 ) = 1 12 ( x 3 n = 1 n ( n + 1 ) x n 1 ) = 1 12 ( x 3 n = 1 ( x n + 1 ) ) = 1 12 ( x 3 ( n = 1 x n + 1 ) ) = 1 12 ( x 3 ( x 2 n = 1 x n 1 ) ) = 1 12 ( x 3 ( x 2 1 x ) ) = 1 12 ( 2 x 3 ( 1 x ) 3 ) = x ( x + 1 ) ( 1 x ) 5 . \begin{aligned}\frac1{12}\sum_{n=1}^\infty n(n+1)(x^{n+2})'' &=\:\frac1{12}\Big(\sum_{n=1}^\infty n(n+1)x^{n+2}\Big)''=\frac1{12}\Big(x^3\sum_{n=1}^\infty n(n+1)x^{n-1}\Big)''=\frac1{12}\Big(x^3\sum_{n=1}^\infty (x^{n+1})''\Big)''\\ &=\:\frac1{12}\Big(x^3\Big(\sum_{n=1}^\infty x^{n+1}\Big)''\Big)''=\frac1{12}\Big(x^3\Big(x^2\sum_{n=1}^\infty x^{n-1}\Big)''\Big)''=\frac1{12}\Big(x^3\Big(\frac{x^2}{1-x}\Big)''\Big)''\\ &=\:\frac1{12}\Big(\frac{2x^3}{(1-x)^3}\Big)''=\frac{x(x+1)}{(1-x)^5}.\end{aligned} Replacing x = 1 10 x=\dfrac1{10} in the last expression yields result 11000 59049 \dfrac{11000}{59049} , meaning 11000 + 59049 = 70049. 11000+59049=70049.

With binomial coefficients the formula gets even easier. By induction, show

k = 0 ( k + m m ) q k = 1 ( 1 q ) m + 1 , q < 1 , m N k = 0 n k 2 = n ( n + 1 ) ( 2 n + 1 ) 6 , n N k = 0 n k 3 = n 2 ( n + 1 ) 2 4 , n N \begin{aligned} \sum_{k=0}^\infty\binom{k+m}{m}q^k&=\frac{1}{(1-q)^{m+1}},&|q|&<1,\quad m\in\mathbb{N}\\\\ \sum_{k=0}^nk^2&=\frac{n(n+1)(2n+1)}{6},&n&\in\mathbb{N}\\\\ \sum_{k=0}^nk^3&=\frac{n^2(n+1)^2}{4},&n&\in\mathbb{N} \end{aligned}

You can use ( k + m m ) q k < C 1 + q 2 k = : b k \left|\binom{k+m}{m}q^k\right|<C\left|\frac{1+|q|}{2}\right|^k=:b_k as convergent upper estimate if in doubt of convergence. Now, the last two well known summation formulae yield

S = k = 1 a k q k , a k = i = 1 k i 2 ( k + 1 i ) = ( k + 1 ) k ( k + 1 ) ( 2 k + 1 ) 6 k 2 ( k + 1 ) 2 4 = 1 12 k ( k + 1 ) 2 ( k + 2 ) = 1 12 ( k ( k + 1 ) ( k + 2 ) ( k + 3 ) 2 k ( k + 1 ) ( k + 2 ) ) k k + 1 S = k = 0 a k + 1 q k + 1 = q 12 k = 0 ( 24 ( k + 4 4 ) 2 6 ( k + 3 3 ) ) q k \begin{aligned} S=\sum_{k=1}^\infty a_kq^k,\qquad a_k&=\sum_{i=1}^ki^2(k+1-i)=(k+1)\cdot\frac{k(k+1)(2k+1)}{6}-\frac{k^2(k+1)^2}{4}=\frac{1}{12}k(k+1)^2(k+2)\\\\ &=\frac{1}{12}\left(k(k+1)(k+2)(k+3)-2k(k+1)(k+2)\right)\\\\ \underset{k\rightarrow k+1}{\Rightarrow}\quad S&=\sum_{k=0}^\infty a_{k+1}q^{k+1}=\frac{q}{12}\sum_{k=0}^\infty \left(24\binom{k+4}{4}-2\cdot6\binom{k+3}{3}\right)q^k \end{aligned}

In the last step, we eliminate the sums over binomials using the first equation with m = 3 ; 4 m=3;\:4 :

S = q ( 2 ( 1 q ) 5 1 ( 1 q ) 4 ) = q 2 ( 1 q ) ( 1 q ) 5 = q ( 1 + q ) ( 1 q ) 5 = q = 0.1 11000 59049 q.e.d. \begin{aligned} S = q\left(\frac{2}{(1-q)^5}-\frac{1}{(1-q)^4}\right)=q\frac{ 2-(1-q) }{(1-q)^5}=\frac{q(1+q)}{(1-q)^5}\underset{q=0.1}{=}\frac{11000}{59049}\quad\text{q.e.d.} \end{aligned}

Carsten Meyer - 2 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...