26
$\begingroup$

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

7 Answers 7

38

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

  • 0
    @BrianM.Scott: Great, thanks again! Now I understand it very clearly. This is a very interesting method indeed.2012-11-12
29

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.

  • 1
    Yes, just like repeated integration of $x$ will yield $x^2\over 2$, $x^3 \over 6$ and so on.2017-12-25
8

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

  • 0
    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! :)2012-11-10
5

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.

  • 0
    @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).2012-11-12
3

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.

2

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

  • 0
    In the second one factor out (n+1)(n+2)(n+3) and notice what happens2012-11-10
1

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