Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Doodling in wolfram, I found that $$ \sum^{k}_{n=1}1=k $$ The formula is pretty obvious, but then you get $$ \sum^{k}_{n=1}n=\frac{k(k+1)}{2} $$ That is a very well known formula, but then it gets interesting when you calculate $$ \sum^{k}_{n=1}n(n+1)=\frac{k(k+1)(k+2)}{3}\\ \sum^{k}_{n=1}n(n+1)(n+2)=\frac{k(k+1)(k+2)(k+3)}{4} $$ And so on. There is an obvious pattern that I really doubt is a coincidence, but I have no idea how to prove it in the general case. Any ideas?

share|improve this question
Pascal's triangle comes to mind here –  Omnomnomnom Sep 4 '13 at 3:47
@Omnomnomnom I thought about it but I was unable to introduce binomials there. However, you can generalize the hypothesis using factorials, but usually working with factorials is harder than not doing so(At least I would have a very hard time trying to do so). –  chubakueno Sep 4 '13 at 3:51
These are essentially the sums for the general $d$ dimensional simplex. –  Jaycob Coleman Sep 4 '13 at 4:02
It's overkill, but you could expand and apply en.wikipedia.org/wiki/Faulhaber%27s_formula –  dls Sep 4 '13 at 4:11
@dls I think that in that case the interesting part would go backwards: That expanding and a applying Faulhaber´s yields such a regular and simple result :) –  chubakueno Sep 4 '13 at 4:22

5 Answers 5

up vote 3 down vote accepted

You can argue any given case by induction. I will take your last,$$\sum^{k}_{n=1}n(n+1)(n+2)=\frac{k(k+1)(k+2)(k+3)}{4}$$ for the example, but I think it is easy to see how it gets carried forward. The base case is simply $1\cdot 2\cdot 3=1\cdot 2\cdot 3\cdot \frac 44$ If it is true up to $k$, then $$\sum^{k+1}_{n=1}n(n+1)(n+2)\\=\sum^{k}_{n=1}n(n+1)(n+2)+(k+1)(k+2)(k+3)\\=\frac{k(k+1)(k+2)(k+3)}{4}+(k+1)(k+2)(k+3)\frac {k+4-k}4\\=\frac{(k+1)(k+2)(k+3)(k+4)}{4}$$

share|improve this answer
Thanks! Just changing the $2$, $3$ and $4$ by $x$,$x+1$ and $x+2$ does the work of generalizing it very nicely. –  chubakueno Sep 4 '13 at 3:59

The easy way to deal, for example, with $\sum_{i=1}^n i(i+1)(i+2)(i+3)$ is to let $F(i)=i(i+1)(i+2)(i+3)(i+4)$. We calculate $F(i)-F(i-1)$. We get $$i(i+1)(i+2)(i+3)(i+4)-(i-1)(i)(i+1)(i+2)(i+3).$$ There is a common factor of $i(i+1)(i+2)(i+3)$. When we "take it out" we are left with $(i+4)-(i-1)=5$.

Let $G(i)=\frac{F(i)}{5}$. Then by our calculation $i(i+1)(i+2)(i+3)=G(i)-G(i-1)$.

Now consider the sum $\sum_{i=1}^n i(i+1)(i+2)(i+3)$. This is $$(G(1)-G(0))+(G(2)-G(1))+G(3)-G(2)) +\cdots+(G(n)-G(n-1)).$$ Observe the telescoping. Since $G(0)=0$, the above sum is equal to $G(n)$. Thus $$\sum_{i=1}^n i(i+1)(i+2)(i+3)=G(n)=\frac{n(n+1)(n+2)(n+3)(n+4)}{5}.$$

Exactly the same idea works in general.

share|improve this answer

The hypothesized equality can be written as follows: for any $m$, we conjecture $$ \sum^{k}_{n=1}\frac{(n+m)!}{(n-1)!}=\frac{(k+m+1)!}{(m+2)(k-1)!} $$ Dividing both sides by $(m+1)!$, we have $$ \sum^{k}_{n=1}\frac{(n+m)!}{(n-1)!(m+1)!}=\frac{(k+m+1)!}{(m+2)!(k-1)!} $$ Or, in other words $$ \sum^{k}_{n=1}\binom{n+m}{m+1}=\binom{k+m+1}{m+2} $$ I'm not sure how to prove this (yet), but it seems very likely that there's a neat trick for all this.

share|improve this answer

Partial sums of sequences $a_n$ that can be expressed as polynomials in $n$ are easily found using discrete calculus.

We start with the discrete version of the Fundamental Theorem of Integral Calculus:

\begin{align*} \sum\limits_{n=1}^k a_n &= \sum\limits_{n=1}^k (\Delta b)_n \\ &= (b_2 - b_1)+(b_3 - b_2)+ \ldots + (b_k - b_{k-1}) + (b_{k+1} - b_k) \\ &= b_{k+1} - b_1 \end{align*}

where $(\Delta b)_n = b_{n+1} - b_n$ is the forward difference. Finding the partial sum has now been reduced to finding a sequence $b_n$ such that $(\Delta b)_n = a_n$.

We will find $b$, the antiderivative of $a$, using falling powers, which are defined by

$$ n^{\underline{k}} = n(n-1)(n-2)\ldots (n-k+1) $$

where $k$ is an integer and, by a second definition, $n^{\underline{0}}=1$. For example

$$ n^{\underline{3}} = n(n-1)(n-2). $$

We now need one more result: the discrete derivative of $n^{\underline{k}}$ is given by

\begin{align*} \Delta n^{\underline{k}} &= (n+1)^{\underline{k}} - n^{\underline{k}} \\ &= (n+1)n^{\underline{k-1}} - n^{\underline{k-1}}(n-k+1) \\ &= kn^{\underline{k-1}} \end{align*}

Let's now find the partial sum for a particular case:

\begin{align} \sum^{k}_{n=1}n(n+1)(n+2) &= \sum^{k}_{n=1} (n+2)^{\underline{3}} \\ &= \sum^{k}_{n=1} \Delta \left[\frac{1}{4} (n+2)^{\underline{4}}\right] \\ &= \frac{(k+3)(k+2)(k+1)k}{4} - \require{cancel}\cancelto{0}{\frac{(1+2)(1+1)(1-0)(1-1)}{4}} \end{align}

The general case:

\begin{align} \sum^{k}_{n=1} (n+p)^{\underline{p+1}} &= \sum^{k}_{n=1} \Delta \left[\frac{1}{p+2} (n+p)^{\underline{p+2}}\right] \\ &= \frac{(k+1+p)(k+p)\ldots [(k+1+p)-(p+2)+1)]}{p+2} \\ &= \frac{(k+1+p)(k+p)\ldots k}{p+2} \end{align}

where $p>0$ is an integer.

share|improve this answer

[I haven't finished yet. Will be gradually improved]

If we do it this way, then probably, it will become more insightful.

$$ \sum^{k}_{n=1}1=k $$

then we preserve everything from the right side exactly as it is. $$ \sum^{k}_{n=1}n=\frac{k(k+1)}{1 \cdot 2} $$ [there will be a picture of the right triangle]

Now again, preserve everything from the right side: $$ \sum^{k}_{n=1}\frac{n(n+1)}{1 \cdot 2}=\frac{k(k+1)(k+2)}{1 \cdot 2 \cdot 3} $$

[there will be a picture of the 6 pyramids composed into rectangular parallelepiped]

$$ \sum^{k}_{n=1}\frac{k(k+1)(k+2)}{1 \cdot 2 \cdot 3}=\frac{k(k+1)(k+2)(k + 3)}{1 \cdot 2 \cdot 3 \cdot 4} $$

[There should be a description of the connection between simple combinations and combinations with repetition]

$$ {n \choose k} = \frac{n \cdot (n - 1) \cdot \ldots \cdot (n - k + 1)}{k \cdot (k - 1) \cdot \ldots \cdot 1} = \frac{n^{\underline{k}}}{k!} $$ $$ \left(\!\middle(\genfrac{}{}{0pt}{}{n}{k}\middle)\!\right) = \frac{n \cdot (n + 1) \cdot \ldots \cdot (n + k - 1)}{k \cdot (k - 1) \cdot \ldots \cdot 1} = \frac{n^{\overline{k}}}{k!} $$

share|improve this answer
You should use the sandbox if you are part way through an answer. –  Michael Albanese 2 days ago
@Michael: Sorry, I don't understand how to use it. Probably, I just don't have the rights to use that post or I need to do something beforehand, but I don't see [Add answer] button there and I cannot edit them neither. –  Pixar 2 days ago
Ah, you might not have enough reputation yet. Oh well, keep it in mind for future use. –  Michael Albanese 2 days ago

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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