Finding a closed formula for $1\cdot2\cdot3\cdots k +\dots + n(n+1)(n+2)\cdots(k+n-1)$

Considering the following formulae:

(i) $1+2+3+..+n = n(n+1)/2$

(ii) $1\cdot2+2\cdot3+3\cdot4+…+n(n+1) = n(n+1)(n+2)/3$

(iii) $1\cdot2\cdot3+2\cdot3\cdot4+…+n(n+1)(n+2) = n(n+1)(n+2)(n+3)/4$

Find and prove a ‘closed formula’ for the sum

$1\cdot2\cdot3\cdot…\cdot k + 2\cdot3\cdot4\cdot…\cdot(k+1) + … + n(n+1)(n+2)\cdot…\cdot (k+n-1)$

generalizing the formulae above.

I have attempted to ‘put’ the first 3 formulae together but I am getting nowhere and wondered where to even start to finding a closed formula.

Solutions Collecting From Web of "Finding a closed formula for $1\cdot2\cdot3\cdots k +\dots + n(n+1)(n+2)\cdots(k+n-1)$"

The pattern looks pretty clear: you have

$$\begin{align*}
&\sum_{i=1}^ni=\frac12n(n+1)\\
&\sum_{i=1}^ni(i+1)=\frac13n(n+1)(n+2)\\
&\sum_{i=1}^ni(i+1)(i+2)=\frac14n(n+1)(n+2)(n+3)\;,
\end{align*}\tag{1}$$

where the righthand sides are closed formulas for the lefthand sides. Now you want

$$\sum_{i=1}^ni(i+1)(i+2)\dots(i+k-1)\;;$$

what’s the obvious extension of the pattern of $(1)$? Once you write it down, the proof will be by induction on $n$.

Added: The general result, of which the three in $(1)$ are special cases, is $$\sum_{i=1}^ni(i+1)(i+2)\dots(i+k-1)=\frac1{k+1}n(n+1)(n+2)\dots(n+k)\;.\tag{2}$$ For $n=1$ this is $$k!=\frac1{k+1}(k+1)!\;,$$ which is certainly true. Now suppose that $(2)$ holds. Then

$$\begin{align*}\sum_{i=1}^{n+1}i(i+1)&(i+2)\dots(i+k-1)\\
&\overset{(1)}=(n+1)(n+2)\dots(n+k)+\sum_{i=1}^ni(i+1)(i+2)\dots(i+k-1)\\
&\overset{(2)}=(n+1)(n+2)\dots(n+k)+\frac1{k+1}n(n+1)(n+2)\dots(n+k)\\
&\overset{(3)}=\left(1+\frac{n}{k+1}\right)(n+1)(n+2)\dots(n+k)\\
&=\frac{n+k+1}{k+1}(n+1)(n+2)\dots(n+k)\\
&=\frac1{k+1}(n+1)(n+2)\dots(n+k)(n+k+1)\;,
\end{align*}$$

exactly what we wanted, giving us the induction step. Here $(1)$ is just separating the last term of the summation from the first $n$, $(2)$ is applying the induction hypothesis, $(3)$ is pulling out the common factor of $(n+1)(n+2)\dots(n+k)$, and the rest is just algebra.

If you divide both sides by $k!$ you will get binomial coefficients and you are in fact trying to prove
$$\binom kk + \binom{k+1}k + \dots + \binom{k+n-1}k = \binom{k+n}{k+1}.$$
This is precisely the identity from this question.

The same argument for $k=3$ was used here.


Or you can look at your problem the other way round: If you prove this result about finite sums
$$\sum_{j=1}^n j(j+1)\dots(j+k-1)= \frac{n(n+1)\dots{n+k-1}}{k+1},$$
you also get a proof of the identity about binomial coefficients.

For a fixed non-negative $k$, let $$f(i)=\frac{1}{k+1}i(i+1)\ldots(i+k).$$
Then $$f(i)-f(i-1)=i(i+1)\ldots(i+k-1).$$
By telescoping,

$$\sum_{i=1}^ni(i+1)(i+2)\dots(i+k-1)=\sum_{i=1}^n\left(f(i)-f(i-1)\right)=f(n)-f(0)=f(n)$$

and we are done.

I asked exactly this question a couple of days ago, here:

Telescoping series of form $\sum (n+1)\cdot…\cdot(n+k)$

enter image description here

My favourite solution path so far is
to start with the hockey stick identity.

From (i), (ii) and (iii) it is reasonable to guess that your sum will be
$$n(n+1)\cdot…\cdot(n+k)/(k+1)$$
Try to prove this by induction.