# How can I derive what is $1\cdot 2\cdot 3\cdot 4 + 2\cdot 3\cdot 4\cdot 5+ 3\cdot 4\cdot 5\cdot 6+\cdots + (n-3)(n-2)(n-1)(n)$ ??

I'd like to evaluate the series $$1\cdot 2\cdot 3\cdot 4 + 2\cdot 3\cdot 4\cdot 5+ 3\cdot 4\cdot 5\cdot 6+\cdots + (n-3)(n-2)(n-1)(n)$$

Since I am a high school student, I only know how to prove such formula's (By principal of mathematical induction). I don't know how to find result of such series.

Please help. I shall be thankful if you guys can provide me general solution (Since I have been told that there exist a general solution by my friend who gave me this question).

• How general? :D – Simply Beautiful Art Nov 19 '16 at 13:33
• @SimpleArt, I can't get you – I am Back Nov 19 '16 at 13:35
• @THELONEWOLF.: I think he was being cheeky/funny. In the math community "general" has a rather specific meaning. At times a "general solution" will give you a lot more than what you thought you asked for. – ReverseFlow Nov 19 '16 at 13:46
• @ReverseFlow, From general solution I mean that,give a formula of method which work not only for 1.2.3.4+2.3.4.5+........+n(n+1)(n+2)(n+3) but which work for all such sequences whether it is 1.2.3 + 2.3.4...... or 1.2.3.4.5 + 2.3.4.5.6... – I am Back Nov 19 '16 at 13:49
• @THELONEWOLF. If you are sooooo...... curious. My answer generalizes to all $p$. Even silly things like $p=1/2$, if you define the product using the gamma function. – Simply Beautiful Art Nov 19 '16 at 13:51

In general, we have

$$\sum_{k=1}^nk(k+1)(k+2)\dots(k+p)=\frac{n(n+1)(n+2)\dots(n+p+1)}{p+2}$$

Prove by induction,

$$\sum_{k=1}^{n+1}k(k+1)(k+2)\dots(k+p)\\=(n+1)(n+2)\dots(n+p+1)+\sum_{k=1}^nk(k+1)(k+2)\dots(k+p)\\=(n+1)(n+2)\dots(n+p+1)+\frac{n(n+1)(n+2)\dots(n+p+1)}{p+2}\\=\frac{\color{#034da3}{(p+2)}\color{#ee8844}{(n+1)(n+2)\dots(n+p+1)}+\color{#034da3}n\color{#ee8844}{(n+1)(n+2)\dots(n+p+1)}}5\\=\frac{\color{#ee8844}{(n+1)(n+2)\dots(n+p+1)}\color{#034da3}{(n+p+2)}}{p+2}$$

And easy enough to check for $n=1$ to see it is true.

$$1\times2\times3\times\ldots\times(1+p)=\frac{1\times2\times3\times\ldots\times(1+p)\times\require{cancel}\cancel{(2+p)}}{\cancel{p+2}}$$

This is slightly off, since my sum ends at $n(n+1)(n+2)(n+3)$, while you end off at $(n-3)(n-2)(n-1)n$. To readjust, have $n=p-3$ in my sum and it will become yours.

• But how will I prove the general case you mentioned first (In general) – I am Back Nov 19 '16 at 13:34
• @THELONEWOLF. In the exact same manner I proved for $p=3$. It's not too hard to do. – Simply Beautiful Art Nov 19 '16 at 13:36
• ∑k=1 to n, k(k+1)(k+2)…(k+p) = n(n+1)(n+2)…(n+p+1)p+2, How will I prove this one?? – I am Back Nov 19 '16 at 13:39
• @THELONEWOLF. Would you like me to change my induction proof to all $p$? – Simply Beautiful Art Nov 19 '16 at 13:39
• yes, @simple art – I am Back Nov 19 '16 at 13:41

Can you prove that $(n-3)(n-2)(n-1)(n) = \frac{(n-3)(n-2)(n-1)(n)(n+1)}{5} - \frac{(n-4)(n-3)(n-2)(n-1)(n)}{5}?$

From there you can substitute different values of $n$ and derive a formula for your expression, and the final summation will be given by

$$\frac{(n-3)(n-2)(n-1)(n)(n+1)}{5}$$

Following up from Yves Daoust's answer, assume that our sum is a polynomial. Clearly it must be a polynomial of degree $5$ with $1/5$ coefficient because

$$P(n)=\sum_{k=1}^nk(k+1)(k+2)(k+3)\sim\int_1^nx^4+\mathcal O(x^3)dx=\frac15x^5+\mathcal O(x^4)$$

Notice that if we have

$$P(1)=24\qquad P(n)=n(n+1)(n+2)(n+3)+P(n-1)$$

Then

$$P(-4)=P(-3)=P(-2)=P(-1)=P(0)=0$$

Meaning, by the fundamental theorem of algebra,

$$P(n)=\frac{n(n+1)(n+2)(n+3)(n+4)}5$$

The product can also be identified as parts of binomials, as $$\binom{n}4=\frac{n(n-1)(n-2)(n-3)}{4!}$$ From the Pascal triangle identity we know that $\binom{n+1}{k+1}=\binom{n}{k+1}+\binom{n}{k}$ where we can put the same denominors on one side $$\binom{n}{k}=\binom{n+1}{k+1}-\binom{n}{k+1}$$

so that finally $$\sum_{n=k}^N\binom{n}{k}=\sum_{n=k}^N\binom{n+1}{k+1}-\binom{n}{k+1}$$ is found to be a telescoping sum.

• Ah, the combinatorial type of proof. The first answer here is good reinforcement of the concept. – Simply Beautiful Art Nov 19 '16 at 14:26

$$\color{blue}{\sum_{r=4}^{n} (r-3)(r-2)(r-1)r}=4!\sum_{r=4}^{n}\binom r4=4!\binom {n+1}5=\color{red}{\frac{(n-3)(n-2)(n-1)n(n+1)}5}$$

Using the Pochhammer notation for the rising factorial, the above may be written as

$$\color{blue}{\sum_{r=4}^n (r-3)^{\overline{4}}}=\color{red}{\frac{(n-3)^\overline{5}}5}$$

It is interesting to note the similarity between this and the standard integral of a power

$$\int_0^n r^4 \;dr=\frac{n^5}5$$

General Case

The above can be generalized to

$$\sum_{r=m+1}^n (r-m)^{\overline{m+1}}=\frac{\;\;(n-m)^{\overline{m+2}}}{m+2\;\;\;}$$

• If you check my MathJax in my answer, you will notice customized color choices. I personally find them easier on the eyes. – Simply Beautiful Art Nov 20 '16 at 1:24

Let us conjugate freak_warrior's tip with a telescopic sum to find the closed formula.

Let us set $a_n = n(n+1)(n+2)(n+3)$

You want to find

$$\sum_{i = 1}^{k} a_i$$

Rewrite

$$a_n = \frac{n(n+1)(n+2)(n+3)(n+4)}{5} - \frac{(n-1)n(n+1)(n+2)(n+3)}{5}$$

One can prove this is true by factoring out $n(n+1)(n+2)(n+3)$.

Set $l_n = \frac{n(n+1)(n+2)(n+3)(n+4)}{5}$ and $r_n = \frac{(n-1)n(n+1)(n+2)(n+3)}{5}$. Now we have

$$a_n = l_n - r_n$$

But as you can see, $r_{n+1} = l_n$ thus

$$\sum_{i = 1}^{k} a_i = \sum_{i = 1}^{k} l_i - r_i = \sum_{i = 1}^{k} r_{i+1} - r_i$$

If you apply the telescopic sum, you get $r_{k+1} - r_1$

The telescopic sum is noticing that two adjacent terms always cancel:

$$\sum_{i = 1}^{k} r_{i+1} - r_i = (r_2 - r_1) + (r_3 - r_2) + \cdots + (r_k - r_{k-1}) + (r_{k+1} - r_k) = r_{k+1} - r_1$$

Now all you have to do is substitute the desired value of $k$.

• @SimpleArt thanks, I was on my phone and could not revert the edit. – RGS Nov 19 '16 at 13:42

The answer must be a quintic polynomial $P(n)$, because $P(n)-P(n-1)$ is a quartic polynomial.

Then it suffices to choose $5$ values of $n$, evaluate the corresponding sums and write the Lagrangian interpolation polynomial, which is guaranteed to be unique.

You can shorten the computation a little by noting that the coefficient of $n^5$ must be $1/5$ (as $n^5-(n-1)^5=5n^4+\cdots$), and by the shifting $m=n-3$ use the fact that $P(3)=0$ to get rid of the independent term.

• @THELONEWOLF. $\ddot~$ Can you even perform Lagrangian interpolation? – Simply Beautiful Art Nov 19 '16 at 14:00
• @SimpleArt No,but I did it by defining a polynomial which is equal to the sum and I then I defined another polynomial by replacing 'n' by 'n+1'..I think it is method of undetermined coefficients. I don't know it is same as Lagrangian interpolation or not. – I am Back Nov 19 '16 at 14:05
• The method of indeterminate coeffcients will give you the same answer (as the answer if unique !); it will require the resolution of a system of $5$ equations in $5$ unknowns. The Lagrangian interpolation is in fact a "precomputed" resolution of this system, which has a special form (a Vandermonde matrix). I don't know which method is the fastest for $5$ unknowns. But in fact, you can bring this down to $3$ unknowns by the tricks I gave. – Yves Daoust Nov 19 '16 at 14:08
• @THELONEWOLF. If you can recursively define a summation to negative numbers, you will quickly and easily find the roots of the said polynomial. Using the first coefficient as $1/5$ is then the last piece you need. – Simply Beautiful Art Nov 19 '16 at 14:11

There are several things you can do.

$1)$First of all, you might try the induction way. But as you know, in order to do that we first need to have the right side of the formula and we can guess the right side, which is the hard part and sometimes it is too hard to do. Let's do that!

Let $S(n)=\sum_{i=1}^n i(i+1)(i+2)(i+3)$. $S(1)=24$, $S(2)=144$, $S(3)=504$. Now, it looks impossible to guess. Therefore, we will try something simpler.

$2)$ This time we will use the formulae we already know such as

$\sum_{i=1}^n i=\frac{n(n+1)}{2}$, $\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}$, $\sum_{i=1}^n i^3=\frac{n(n+1)}{2}^2$ , and $\sum_{i=1}^n i^4=\frac{n^5}{5}+\frac{n^4}{2}+\frac{n^3}{3}-\frac{n}{30}$. $$S(n)=\sum_{i=1}^n i(i+1)(i+2)(i+3)=\sum_{i=1}^n (i^4+6i^3+11i^2+6i)=\sum_{i=1}^n i^4+ \quad 6\sum_{i=1}^n i^3+11\sum_{i=1}^n i^2+6\sum_{i=1}^n i$$ By using the formulae above we can conclude that $\sum_{i=1}^n i(i+1)(i+2)(i+3)=\frac{1}{5}n(n+1)(n+2)(n+3)(n+4)$ In fact, now i can see that first method can be used as well.( The formula does not look so complex, one can guess, apparently not me!).

As a result, when we have a polynomial we can use the formulae as we have done for this particular example. You can find the formulae here http://math2.org/math/expansion/power.htm. These formulae are easy to prove(by induction), also you might want to derive them as well, which is a little bit harder but something you can try.

• Nicely written, thanks.+1 – I am Back Nov 19 '16 at 14:11

Using finite calculus we have that

$$\sum k^{\underline 4}\delta k=\frac{k^{\underline 5}}{5}+C$$

where $k^{\underline 4}=k(k-1)(k-2)(k-3)$ is a falling factorial. Then taking limits

$$\sum_{k=m}^nk^{\underline 4}=\sum\nolimits_m^{n+1}k^{\underline 4}\delta k=\frac{k^{\underline 5}}{5}\bigg|_m^{n+1}$$

The standard case is

$$\sum_{k=4}^{n+4}k^{\underline 4}=\frac15(n+5)^{\underline 5}$$

• I really ought to learn finite calculus... – Simply Beautiful Art Nov 19 '16 at 14:01