# Sum of the sum of the sum of the first $n$ natural numbers

I have here another problem of mine, which I couldn't manage to solve.

Given that: $$x_n = 1 + 2 + \dots + n \\ y_n = x_1 + x_2 + \dots + x_n \\ z_n = y_1 + y_2 + \dots + y_n$$

Find $z_{20}$.

I know the answer but I'm having a hard time reaching it. I recognized that $x_n$ is obviously $\dfrac{n(n + 1)}{2}$, but how to express the other two in a closed form to allow the calculation? I even tried writing the relations in a recursive way, without success. Is there an easy way to solve this one? I was not allowed to use calculators.

Thanks,
rubik

There’s a very easy way if you know some basic facts about binomial coefficients. You have $x_n=\binom{n+1}2$, so

$$y_n=\sum_{k=1}^nx_k=\sum_{k=1}^n\binom{k+1}2=\binom{n+2}3$$

and

$$z_n=\sum_{k=1}^ny_n=\sum_{k=1}^n\binom{k+2}3=\binom{n+3}4\;,$$

and $$z_{20}=\binom{23}4=\frac{23\cdot22\cdot21\cdot20}{4\cdot3\cdot2}=23\cdot11\cdot7\cdot5=253\cdot7\cdot5=1771\cdot5=8855$$

(where the arithmetic was done in my head as I was typing).

Without that knowledge (or something comparable, like the formulas for the sums of consecutive squares and cubes) it would appear to be a pretty hard problem. The specific identity that I’m using is

$$\sum_{k=m}^n\binom{k}m=\binom{n+1}{m+1}\;.$$

• Yep! I don't know much about binomial coefficients, but I think I understand it clearly! Thanks! Nov 10, 2012 at 17:50
• Shouldn't the identity be the sum from k = 1 instead k = m? Nov 10, 2012 at 17:53
• @rubik: You’re welcome! The identity can be expressed in several equivalent ways, but the way that I chose actually does fit this problem: notice that in $\sum_{k=1}^n\binom{k+2}3$, for instance, the upper number, $k+2$, really does run from $3$ to $n+2$, even though $k$ has a different range. Nov 10, 2012 at 17:53
• That is a very interesting method. Nov 11, 2012 at 1:54
• @Greg: It can be seen as a direct consequence of the finite calculus approach that you used (and which I also like): those falling-power-rule summations are one way to prove the identity that I used. Nov 11, 2012 at 2:05

Using finite calculus, it would be an analog of the repeated integral of a polynomial:

$$\sum_{i=1}^{n}{\sum_{j=1}^{i}{\sum_{k=1}^{j}{k}}}=\sum_{i=1}^{n}{\sum_{j=1}^{i}{\frac{1}{2}j^{\underline{2}}}}=\sum_{i=1}^{n}{\frac{1}{6}{i^{\underline{3}}}}=\frac{1}{24}n^{\underline{4}}=\frac{1}{24}n(n+1)(n+2)(n+3)$$ It's actually that short.

• Wow this is too advanced for me as for now! Thanks anyway and thanks as well for the document, I saved it. Nov 10, 2012 at 18:57
• Is this progression expand to any number of repeated sigma? I mean it seem 4 sigma will end up with n(n+1)...(n+4)/120 then n(n+1)...(n+5)/720 Dec 25, 2017 at 4:06
• Yes, just like repeated integration of $x$ will yield $x^2\over 2$, $x^3 \over 6$ and so on. Dec 25, 2017 at 23:58
• Can you kindly explain what you did? I don't have knowledge about this falling/ rising factorials. You can also suggest formal way to read it so that I can understand this kind of things. Thanks 😊 It's completely a new stuff to me ,so I upvoted. Jan 2, 2021 at 9:26

Here is a slightly longer method than Brian M. Scott's, relying on knowing closed forms for $n$, $n^{2}$ and $n^{3}$.

You have: $$x_{n}=\frac{n(n+1)}{2}=\frac{1}{2}n^{2}+\frac{1}{2}n$$

Therefore: \begin{align}y_{n}&=\sum_{i=1}^{n}{\left(\frac{1}{2}i^{2}+\frac{1}{2}i\right)}=\frac{1}{2}\left(\sum_{i=1}^{n}i^{2}+\sum_{i=1}^{n}{i}\right)=\frac{1}{2}\left(\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}\right) \\ &= \frac{1}{2}\left(\frac{1}{3}n^{3}+n^{2}+\frac{2}{3}n\right) \end{align}

Therefore:

\begin{align}z_{n}&=\sum_{i=1}^{n}{\left(\frac{1}{6}n^{3}+\frac{1}{2}n^{2}+\frac{1}{3}n\right)}=\frac{1}{6}\sum_{i=1}^{n}n^{3}+\frac{1}{2}\sum_{i=1}^{n}n^{2}+\frac{1}{3}\sum_{i=1}^{n}{n} \\ &= \frac{1}{6}\cdot\frac{n^{2}(n+1)^{2}}{4}+\frac{1}{2}\cdot\frac{n(n+1)(2n+1)}{6}+\frac{1}{3}\cdot\frac{n(n+1)}{2} \\ &= \frac{1}{24}n(n+1)(n+2)(n+3)\end{align}

• This is a nice method as well, but it requires to remember the closed forms for the sums of squares and cubes, which I always forget! :) Nov 10, 2012 at 17:57

As someone who usually doesn't remember formulas for sums of binomial coefficients (although the sum here is simple to notice given Pascal's triangle), the presence of partial sums in the problem suggests using generating functions.

Note that if we have a function

$$f(x)=c_0+c_1 x+c_2 x^2+...+c_n x^n+... ,$$

then by multiplying by $\frac{1}{1-x}$ we get a new series where the coefficients are the partial sums of the $c_n$'s.

$$\frac{f(x)}{1-x} = f(x) \cdot (1 + x + x^2 + ...) = c_0 + (c_0+c_1)x + ... + \sum_{i=0}^n c_i x^n + ...$$

By using this, we can construct a few functions to find the desired value (careful here, we've changed from 0-indexing to 1-indexing):

\begin{align} f_1(x) = (1-x)^{-1} &= 1+x+x^2+...\\ f_2(x) = (1-x)^{-2} &= 1+2x+3x^2+...\\ f_3(x) = (1-x)^{-3} &= x_1+x_2 x+x_3x^2+...\\ f_4(x) = (1-x)^{-4} &= y_1+y_2 x+y_3x^2+...\\ f_5(x) = (1-x)^{-5} &= z_1+z_2 x+z_3x^2+... \end{align}

Note that $\frac{d}{dx} f_n(x) = n f_{n+1}(x)$. In particular, this gives that:

$$x_n = \frac{1}{2} n(n+1)$$ $$y_n = \frac{1}{3} n \cdot x_{n+1} = \frac{1}{6} n(n+1)(n+2)$$ $$z_n = \frac{1}{4} n \cdot y_{n+1} = \frac{1}{24} n(n+1)(n+2)(n+3)$$

from which $z_{20}$ can be easily computed.

• This is quite obscure to me, but don't worry: it's my fault. I haven't studied generating functions yet, and I don't understand the first part of the post... Nov 12, 2012 at 10:35
• @rubik: Which part specifically? From the second line of math, the first equality is since $\frac{1}{1-x}$ equals the infinite geometric series $\sum_{i=0}^{\infty} x^i$, the second equality is by expanding the product of the two infinite series (maybe try doing a few terms manually here to work this out).
– Nabb
Nov 12, 2012 at 13:02

Hint 1: Note that $$\frac{n(n+1)}2=\frac13\left(\frac{(n+1)(n+2)(n+3)}2 - \frac{n(n+1)(n+2)}2\right).$$ Now use the method of differences to find $y(n)$.

Hint 2: Note that $$\frac{n(n+1)(n+2)}6=\frac16\left(\frac{(n+1)(n+2)(n+3)(n+4)}4-\frac{n(n+1)(n+2)(n+3)}4\right).$$ Now use the method of differences to find $z(n)$.

• Interesting, I wonder how you can get those differences, they look quite complicated to deduce from the LHS. Nov 10, 2012 at 19:04
• In the first one, factor out (n+1)(n+2) and notice what happens.
– Amr
Nov 10, 2012 at 19:27
• In the second one factor out (n+1)(n+2)(n+3) and notice what happens
– Amr
Nov 10, 2012 at 19:28

It is easy to see by induction that $$\sum_{k=1}^{n}k\cdot(k+1)\cdot\ldots\cdot(k+l)=\frac{n\cdot(n+1)\cdot\ldots\cdot(n+l+1)}{l+2}$$ for all $\ l\geq 0$. Consequently using this identity for $\ l=0,1,2\$gives the sought for closed formula.

$$2y_n=2\sum_{1\le r\le n}x_1=\sum_{1\le r\le n}(r^2+r)=\frac{n(n+1)(2n+1)}6+\frac{n(n+1)}2=\frac{n(n+1)(n+2)}3$$

$\implies 6y_n=n^3+3n^2+2n$

$$6z_n=6\sum_{1\le r\le n}y_r=\sum_{1\le r\le n}(r^3+3r^2+2r)$$ $$=\left(\frac{n(n+1)}2\right)^2+3\frac{n(n+1)(2n+1)}6+2\frac{n(n+1)}2$$

$$=\frac{n(n+1)\{3n(n+1)+6(2n+1)+12\}}{12}=\frac{n(n+1)\{3n^2+15n+18\}}{12}=\frac{n(n+1)(n+2)(n+3)}4$$

So, $$z_n=\frac{n(n+1)(n+2)(n+3)}{24}$$

So, $$z_{20}=\frac{20(20+1)(20+2)(20+3)}{24}=5\cdot7\cdot11\cdot 23$$