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}\;.$$

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.

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}$$

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.

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)$.