Nested Summation

Algebra Level 3

$\sum _{ n=1 }^{ 2016 }{ \dfrac { 1+2+3+\dots +n }{ { 1 }^{ 3 }+{ 2 }^{ 3 }+{ 3 }^{ 3 }+\dots +{ n }^{ 3 } } }$

If the value of this sum is $\frac{A}{B}$ , where $A$ and $B$ are coprime positive integers, find $A + B.$

The answer is 6049.

2 solutions

Arulx Z
Feb 27, 2016

By referencing sum of n, n², or n³ , we have

$\begin{aligned} 1 + 2 + 3 + \cdots + n &= &\dfrac {n(n+1)}2 \\ 1^3 + 2^3 +3^3+ \cdots + n^3 &= &\dfrac {n^2 (n+1)^2}4 = \left( \dfrac{n(n+1)} 2\right)^2 \\ \end{aligned}$

Thus, taking the ratio of the two expressions gives

$\begin{aligned} \dfrac{1 + 2 + 3 + \cdots + n} {1^3 + 2^3 +3^3+ \cdots + n^3} & =& \dfrac {n(n+1)}2 \div \left( \dfrac{n(n+1)} 2\right)^2 \\ &=& \cancel{\dfrac {n(n+1)}2} \div \left( \dfrac{n(n+1)} 2\right)^{\cancel2} \\ &=& 1 \div \left( \dfrac{n(n+1)} 2\right) \\ &=& \dfrac{2}{n(n+1)} \end{aligned}$

By partial fractions - cover up rule , we have $\dfrac{2}{n(n+1)} = \dfrac2n - \dfrac2{n+1}$ .

Now let's evaluate the sum!

$\begin{aligned} && \sum_{n=1}^{2016} \dfrac{1 + 2 + 3 + \cdots + n} {1^3 + 2^3 +3^3+ \cdots + n^3} \\ &=& \sum_{n=1}^{2016} \dfrac{2}{n(n+1)} \\ &=& \sum_{n=1}^{2016} \left( \dfrac2n - \dfrac2{n+1} \right) \\ &=& 2 \sum_{n=1}^{2016} \left( \dfrac 1n - \dfrac1{n+1} \right) \\ &=& 2 \left [ \left( \dfrac11 - {\dfrac12} \right) + \left( {\dfrac12} - {\dfrac13} \right) + \left( {\dfrac13} -{\dfrac14} \right) + \cdots +\left( {\dfrac1{2015}} -{\dfrac1{2016}} \right) + \left({\dfrac1{2016}} - \dfrac1{2017} \right) \right ] \\ &=& 2 \left [ \left( \dfrac11 - \xcancel{\dfrac12} \right) + \left( \xcancel{\dfrac12} - \xcancel{\dfrac13} \right) + \left( \xcancel{\dfrac13} - \xcancel{\dfrac14} \right) + \cdots +\left( \xcancel{\dfrac1{2015}} - \xcancel{\dfrac1{2016}} \right) + \left( \xcancel{\dfrac1{2016}} - \dfrac1{2017} \right) \right ] \\ &=& 2 \left( 1 - \dfrac1{2017} \right) = 2 \left( \dfrac{2016}{2017} \right) = \dfrac{4032}{2017} \\ \end{aligned}$

In the penultimate steps, the terms cancel out in pairs (this is known as a telescoping sum ).

Since the summation is equal to $\dfrac{4032}{2017}$ and the fraction is already stated in its lowest form, then $A = 4032, B= 2017\Rightarrow A+B= \boxed{6049}$ .

Moderator note:

Great explanation!

Bonus:( Slightly tougher ;-) $\lim_{n\rightarrow\infty}\dfrac{(1^2+2^2+\cdots+n^2)(1^4+2^4+\cdots+n^4)}{(1^7+2^7+\cdots+n^7)}=\dfrac{k+1}{15}$ $\color{#D61F06}{\large k=?}$

Rishabh Jain - 5 years, 3 months ago

Six. Hint : Apply riemann sums .

Pi Han Goh - 5 years, 3 months ago

Yeah .. Exactly $\dfrac{(\int_0^1x^2 dx)(\int_0^1x^4 dx)}{(\int_0^1x^7 dx)}$ $=\dfrac{(\frac 13)(\frac 15)}{(\frac 18)}$ $=\dfrac{8}{15}\implies k=\boxed 7$

Rishabh Jain - 5 years, 3 months ago

@Rishabh Jain – Nope. You made a mistake. Try again, think about taking out a power from the denominator.

Pi Han Goh - 5 years, 3 months ago

@Pi Han Goh – Summation can be represented as: $\lim_{n\to \infty}\dfrac{1}{n}\left(\dfrac{\left(\displaystyle\sum_{r=1}^{\infty}\left(\frac rn\right)^2\right)\left(\displaystyle\sum_{r=1}^{\infty}\left(\frac rn\right)^4\right)}{\displaystyle\sum_{r=1}^{\infty}\left(\frac rn\right)^7 }\right)$ and hence the above form.. Isn't it right??

Rishabh Jain - 5 years, 3 months ago

@Rishabh Jain – (r/n)^6, and not (r/n)^7

Pi Han Goh - 5 years, 3 months ago

@Pi Han Goh – Then that $\frac 1n$ will not come. And the required form will not be generated.!!

Rishabh Jain - 5 years, 3 months ago

@Rishabh Jain – Oh wait ...silly me. I thought of some other theorem and got messed up. Yup you're right! You should this as a problem!! =D

Pi Han Goh - 5 years, 3 months ago

@Pi Han Goh – Surely... I'll post it after modification and making it a bit scary ;-) ..(after my exams!!)

Rishabh Jain - 5 years, 3 months ago

@Pi Han Goh – There's a typo in your comment :P

"You should post this as a problem!! =D"

Mehul Arora - 5 years, 3 months ago

Can you help me in this too?? $\lim_{n\to\infty}\dfrac{1}{n}\ln\left(\dfrac{(2n)!}{n^nn!}\right)$ I wrote it as : $\lim_{n\to\infty}\dfrac{1}{n}\ln\left(\dfrac{(2n)(2n-1)(2n-2)\cdots(2n-(n-1))}{\underbrace{n\cdot n\cdot n\cdots n}_{\text{n times }}}\right)$ $=\lim_{n\to\infty}\dfrac{1}{n}\displaystyle\sum_{r=0}^{n-1} \ln\left(2-\dfrac{r}{n}\right)$ $=\int_{0}^1 \ln (2-x)\, dx$ $=\ln4-1$ Have I done correct or have I commited some mistake??

Rishabh Jain - 5 years, 2 months ago

@Rishabh Jain – Yes, your work is correct.

Tirthankar Mazumder - 1 year, 6 months ago

Those cross things made it look perfect.

Mehul Arora - 5 years, 3 months ago

Same way dude!!! An easy problem.

abc xyz - 5 years, 3 months ago

Is not the summation simply 1/2033136? So A +B = 2033137

Greg Grapsas - 4 years, 7 months ago

Please elaborate

Arulx Z - 4 years, 7 months ago

@Arulx Z I think Greg means you directly sub n=2016 into the simplified equation 2/n(n+1), which will give you 1/2033136. Why is that wrong?

Teng Chou Nathan Mar - 4 years, 2 months ago

@Teng Chou Nathan Mar – The answer is actually $\frac{2}{1\cdot 2} + \frac{2}{2\cdot 3} + \frac{2}{3\cdot 4} + \dots + \frac{2}{2016 \cdot 2017}$ . So simply substituting 2016 won't help.

Arulx Z - 4 years, 2 months ago

Greg is right here . Arul don't you think the summation of this series will be less then one ? Denominator >> numerator . The part you did wrong was , you took summation (2÷(n)(n+1)) as the nth term and started added it , hence you got a number > 1

Aditya Dungrani - 1 year, 6 months ago

Great use of telescoping! I was fool enough to do the whole induction shenanigan.

Eduardo Gomes Bonilha Gonçalves - 3 years, 6 months ago

import numpy as np
from fractions import Fraction

sum_ = 0
sum_cubed = 0
X = 0.
denom_range = 100000

for i in range(1,2017):
    for j in range(1,i+1):
        sum_ += np.float64(j)
        sum_cubed += np.float64(j**3)
        #print sum_, sum_cubed
    X += np.float64(sum_/sum_cubed)
    sum_ = 0
    sum_cubed = 0

A = Fraction(X).limit_denominator(denom_range).numerator
B = Fraction(X).limit_denominator(denom_range).denominator 
print 'Summation = %s' %(Fraction(X).limit_denominator(denom_range))
print  'A + B = %d' % (A+B)

1 2	`Summation = 4032/2017 A + B = 6049`

Michael Fitzgerald - 3 years, 1 month ago

Richard Levine
Oct 21, 2016

The summation amounts to 1/1+(1+2)/(1+2)^2+(1+2+3)/(1+2+3)^2+...(1+2+3+...+n)/(1+2+3+...+n)^2 = 1+1/3+1/6+...+1/(n(n+1)/2). Notice that for increasing values of n there is a pattern in the sum: 1, 4/3, 6/4, 8/5, ..., 2n/(n+1). Therefore, the sum to n=2016 is 2(2016)/(2016+1) = 4032/2017. 4032+2017 = 6049.

The pattern I saw was 1, 4/3, 9/6, 16/10, ..., n^2/(1+2+...+n) which equals n^2/(n(n+1)/2) = 2n^2/(n(n+1) = 2n/(n+1)

Ashley Reavis - 3 years, 9 months ago