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

|cite|improve this question
$\endgroup$
38
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Yep! I don't know much about binomial coefficients, but I think I understand it clearly! Thanks! $\endgroup$ – rubik Nov 10 '12 at 17:50
  • $\begingroup$ Shouldn't the identity be the sum from k = 1 instead k = m? $\endgroup$ – rubik Nov 10 '12 at 17:53
  • 2
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Nov 10 '12 at 17:53
  • $\begingroup$ That is a very interesting method. $\endgroup$ – GregRos Nov 11 '12 at 1:54
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Nov 11 '12 at 2:05
29
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Wow this is too advanced for me as for now! Thanks anyway and thanks as well for the document, I saved it. $\endgroup$ – rubik Nov 10 '12 at 18:57
  • $\begingroup$ 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 $\endgroup$ – Thaina Dec 25 '17 at 4:06
  • 1
    $\begingroup$ Yes, just like repeated integration of $x$ will yield $x^2\over 2$, $x^3 \over 6$ and so on. $\endgroup$ – GregRos Dec 25 '17 at 23:58
8
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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! :) $\endgroup$ – rubik Nov 10 '12 at 17:57
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – rubik Nov 12 '12 at 10:35
  • $\begingroup$ @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). $\endgroup$ – Nabb Nov 12 '12 at 13:02
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Interesting, I wonder how you can get those differences, they look quite complicated to deduce from the LHS. $\endgroup$ – rubik Nov 10 '12 at 19:04
  • $\begingroup$ In the first one, factor out (n+1)(n+2) and notice what happens. $\endgroup$ – Amr Nov 10 '12 at 19:27
  • $\begingroup$ In the second one factor out (n+1)(n+2)(n+3) and notice what happens $\endgroup$ – Amr Nov 10 '12 at 19:28
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.