How could I go about proving this summation of a rising factorial?

Question

$$\sum_{r=1}^{n}r(r+1)(r+2)...(r+p-1) = \frac{1}{p+1}n(n+1)(n+2)...(n+p)$$

So I get how to do this with limited terms, like r(r+1) just ends up with some summations of r, r^2 and onward, but how could I prove this generalization? I tried doing something with induction, but I got lost on how would the p increment for the n+1 case.

Answer 1

Induction step: Suppose true for $n$. Then $$\begin{aligned}\sum_{r=1}^{n+1}r(r+1)\ldots(r+p-1)&=\sum_{r=1}^nr(r+1)\ldots(r+p-1)+(n+1)(n+2)\ldots(n+p)\\ &=\frac{1}{p+1}n(n+1)\ldots(n+p)+(n+1)(n+2)\ldots(n+p)\\&=\frac{1}{p+1}\left(n(n+1)\ldots(n+p)+(p+1)(n+1)(n+2)\ldots(n+p)\right)\\ &=\frac{1}{p+1}\left((n+1)\ldots(n+p)\right)(n+(p+1))\\ &=\frac{1}{p+1}(n+1)\ldots(n+p)(n+1+p) \end{aligned}$$

Answer 2

For $n=1$ it is true. Suppose it is true for $n$. Then \begin{align} \sum_{r\le n+1}r(r+1)\cdots (r+p-1)&=\frac{n(n+1)\cdots (n+p)}{p+1}+(n+1)(n+2)\cdots (n+p) \\ &=\frac{(n+1)\cdots (n+p+1)}{p+1},\\ \end{align} which completes the induction.

Answer 3

A good candidate for induction I think.

If you can show $\frac 1{p+1} n(n+1)....(n+p) + (n+1)(n+2)....(n+p) = \frac 1{p+1}(n+1)(n+2)....(n+p+1)$ you are done[$*$].

And that's just a matter of factoring.

And $\frac 1{p+1} n(n+1)....(n+p) + (n+1)(n+2)....(n+p)= (\frac 1{p+1}*n + 1)[(n+1)...(n+p)]=$

$(\frac {n+(p+1)}{p+1})[(n+1)...(n+p)]$

$\frac 1{p+1}[(n+1)...(n+p)](n+p+1)$

$\frac 1{p+1}(n+1).....(n+p+1)$

====

[$*$] Formally: Let $f(r) = r(r_1)....(r+ p + 1)$.

Let $h(n) = \frac 1{p+1}n(n+1)....(n+p)$

We need to prove $\sum\limits_{r=1}^n f(r) = h(n)$.

Step 1: Prove $\sum\limits_{r=1}^1 f(r) =f(1) = h(1)$

in other words $1*2*3....p = \frac 1{p+1}1*2*.....*p*(p+1)$.

That's very easy.

Step 2: Prove $\sum\limits_{r=1}^{n+1} f(r)= \sum\limits_{r=1}^{n}f(r) + f(n+1)=$

$h(n) + f(n+1) = h(n+1)$.

.... which is ...

$\frac 1{p+1} n(n+1)....(n+p) + (n+1)(n+2)....(n+p) = \frac 1{p+1}(n+1)(n+2)....(n+p+1)$

Which is done above. It's just a matter of factoring.

Answer 4

We claim that $$ \sum_{i=0}^n\binom{i}{k}=\binom{n+1}{k+1}\tag{1}. $$ Indeed the RHS counts the number of $k+1$ element subsets of $\{0,1\dotsc,n\}$. The LHS counts the same thing by classifying the subsets based on their maximum element. For $0\leq i\leq n$, there are $\binom{i}{k}$ subsets of $\{0,1\dotsc,n\}$ whose maximum element is $i$.

Now observe that $$ \sum_{r=1}^{n}r(r+1)(r+2)...(r+p-1)=p!\sum_{r=1}^n\binom{r+p-1}{p}=p!\sum_{u=p}^{n+p-1}\binom{u}{p}=p!\binom{n+p}{p+1} $$ where in the last equality we used (1). But $$ p!\binom{n+p}{p+1}=p!\times\frac{n(n+1)\dotsb(n+p)}{(p+1)!}=\frac{n(n+1)\dotsb(n+p)}{p+1} $$ as desired.

Answer 5

Since you were also open to other methods than induction, we can try telescoping method of sums.

Our original sum is something like

$$S = \sum_{r=1}^{n} \prod_{k=0}^{p-1} (r+k)$$

Let us define new terms in the following manner:

$$\begin{align} T_r &= \prod_{k=0}^{p}(r+k) \\ T_{r+1}-T_r &= \prod_{k=0}^{p}(r+1+k)-\prod_{k=0}^{p}(r+k) \\ T_{r+1}-T_r &= (p+1)\prod_{k=0}^{p-1}(r+1+k) \end{align}$$

Now sum from $r=-1$ to $n-1$ and on left side we get terms cancelling. On right side we get our required sum. Also note that $T_{-1} = 0$:

$$T_n - T_{-1} = (p+1)S \\ \implies S = \frac{T_n}{p+1}=\frac{\prod_{k=0}^{p}(n+k)}{p+1}$$

Answer 6

Note that the result can be stated quite neatly using notation for rising factorials as follows:

$$\sum_{r=1}^n r^{\overline{p}}=\frac {\;\;\;n^{\overline{p+1}}}{p+1}$$

which is analogous to the standard integral

$$\int_0^n r^p\;\text dr=\frac {\;\;n^{\ p+1}}{p+1}$$

The summation can be proven using the Hockey-Stick Identity, written in this case as $$p!\sum_{r=1}^n\binom {r+p-1}p=p!\binom {n+p}{p+1}$$