# How to find the sum of $i(i+1)\cdots(i+k)$ for fixed $k$ between $i = 1$ and $n$?

I learned that $$\sum \limits_{i=1}^n i(i+1) = \frac{n(n+1)(n+2)}{3}$$ or in general $$\sum \limits_{i = 1}^n i(i+1)(i+2) \dots (i + k) = \frac{n(n+1)\dots (n+k+1)}{k+2}$$ From a mathematical standpoint why is this true? I'm not asking for inductive proof. I am asking if you only given the left hand side, how would you go about writing a closed form expression for the sum?

-
I suggest you change the $i$'s on the rhs by $n$'s. –  Claude Leibovici Mar 11 at 7:17
Your right hand sides should contain $n$s, right? Are you looking for a similar reasoning as one does for $\sum_{i=1}^n i = \frac{n(n+1)}{2}$, where one can argue that we have $n/2$ summands which each sum to $n+1$, namely $1$ and $n$, $2$ and $n-1$, and so on? –  Roland Mar 11 at 7:19
Thanks for the fix. In this case though, the pairs approach doesnt work since the terms dont grow linearly –  asdfasdf Mar 11 at 7:23
Try a combinatorial argument. Start by dividing both sides by $(k+1)!$, and recognize the resulting terms as binomial coefficients. –  Andres Caicedo Mar 11 at 7:25
$$i(i+1)\cdots(i+k) = \color{red}{\frac{(i+k+1)-(i-1)}{k+2}}i(i+1)\cdots(i+k)\\ = \frac{\big(i(i+1)\cdots(i+k)\color{red}{(i+k+1)}\big) - \big(\color{red}{(i-1)}i(i+1)\cdots(i+k)\big)}{\color{red}{k+2}}$$ and telesoping... –  achille hui Mar 11 at 7:52

$$S=\sum \limits_{i = 1}^n i(i+1)(i+2) \dots (i + k) = \sum_{i=1}^{n}\frac{(i+k)!}{(i-1)!}$$

$$\frac{S}{(k+1)!}=\sum_{i=1}^{n}\frac{(i+k)!}{(i-1)!(k+1)!}=\sum_{i=0}^{n-1}\binom{i+k+1}{i}$$

$$\frac{S}{(k+1)!}=\binom{k+1}{0} + \binom{k+2}{1} + \dots + \binom{n+k}{n-1} \\ =\binom{k+2}{0} + \binom{k+2}{1} + \dots + \binom{n+k}{n-1} \\ =\binom{k+3}{1} + \binom{k+3}{2} + \dots + \binom{n+k}{n-1} \\ =\binom{n+k+1}{n-1}$$

the above uses $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$

$$S=\binom{n+k+1}{n-1}*(k+1)!=\frac{(n+k+1)!(k+1)!}{(n-1)!(k+2)!}= \frac{n(n+1)\dots (n+k+1)}{k+2}$$

-

There is a combinatorial argument (used several times in this site) which explains these identities: $$\sum \limits_{i = 1}^n i(i+1)(i+2) \cdots (i + k) = \frac{n(n+1)\dots (n+k+1)}{k+2}$$ Rather it explains THESE equivalent identities: $$\sum \limits_{i = 1}^n \binom{i+k}{k+1}=\frac{1}{(k+1)!}\sum \limits_{i = 1}^n i(i+1)(i+2) \cdots (i + k) = \frac{n(n+1)\dots (n+k+1)}{(k+2)!}=\binom{n+k+1}{k+2}$$

So, the right-hand side of the above is the number $N$ of ways (or combinations) we can pick $k+2$ elements from the set $\{1,2,\ldots,n+k+1\}$. This number $N$ can be split as $$N=N_{k+2}+N_{k+3}+\cdots+N_{n+k+1},$$ where $N_{k+i}$ is the number of those previous combinations where the largest number in the combination is $k+i$, and hence $N_{k+i}$ is equal to the number of ways we pick $k+1$ elements from the set $\{1,2,\ldots,k+i-1\}$, and thus $$N_{k+i}=\binom{k+i-1}{k+1}.$$ Thus $$\binom{k+1}{k+1}+\binom{k+2}{k+1}+\cdots+\binom{n+k}{k+1}=\binom{n+k+1}{k+2}.$$

-

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle #1 \right\rangle} \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace} \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left( #1 \right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ $\ds{\sum_{i = 1}^{n}i\pars{i + 1}\pars{i + 2}\ldots\pars{i + k} ={n\pars{n + 1}\ldots\pars{n + k + 1} \over k + 2}:\ {\large ?}}$

\begin{align} &\sum_{\ell = 1}^{n}\ell\pars{\ell + 1}\pars{\ell + 2}\ldots\pars{\ell + k}= \sum_{i = 1}^{n}{\pars{\ell + k}! \over \pars{\ell - 1}!} =\pars{k + 1}!\sum_{\ell = 1}^{n}{\ell + k \choose k + 1} \\[3mm]&=\pars{k + 1}!\sum_{\ell = 1}^{n} \int_{\verts{z} = 1}{\pars{1 + z}^{\ell + k} \over z^{k + 2}}\,{\dd z \over 2\pi\ic} =\pars{k + 1}!\int_{\verts{z} = 1}{\pars{1 + z}^{k} \over z^{k + 2}} \sum_{\ell = 1}^{n}\pars{1 + z}^{\ell}\,{\dd z \over 2\pi\ic} \\[3mm]&=\pars{k + 1}!\int_{\verts{z} = 1}{\pars{1 + z}^{k} \over z^{k + 2}}\, {\pars{1 + z}\bracks{\pars{1 + z}^{n} - 1} \over \pars{1 + z} - 1} \,{\dd z \over 2\pi\ic} \\[3mm]&=\pars{k + 1}!\ \overbrace{\int_{\verts{z} = 1} {\pars{1 + z}^{k + 1 + n} \over z^{k + 3}}\,{\dd z \over 2\pi\ic}} ^{\ds{=\ {n + k + 1 \choose k + 2}}}\ -\ \pars{k + 1}!\ \overbrace{\int_{\verts{z} = 1}{\pars{1 + z}^{k + 1} \over z^{k + 3}}\,{\dd z \over 2\pi\ic}}^{\ds{=\ 0}} \\[3mm]&=\pars{k + 1}!\,{\pars{n + k + 1}! \over \pars{k + 2}!\pars{n - 1}!} =\color{#f00}{% \pars{k + 1}!}\,{\pars{n + k + 1}\ldots\pars{n + 1}n\,\color{#f00}{\pars{n - 1}!} \over \pars{k + 2}\color{#f00}{\pars{k + 1}!}\,\color{#f00}{\pars{n - 1}!}} \end{align}

$$\color{#00f}{\large\sum_{i = 1}^{n}i\pars{i + 1}\pars{i + 2}\ldots\pars{i + k} ={n\pars{n + 1}\ldots\pars{n + k + 1} \over k + 2}}$$

-
Amusing: the integral $$\int_{0}^{1}t^{\xi + 1}\pars{1 - t}^{-\xi - 3}\,\dd t,$$ which appears in the fourth line of the computation of ${\cal I}\pars{\xi}$, exists for NO VALUE of $\xi$ whatsoever. –  Did Mar 11 at 10:28