Sums of rising factorial powers

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.

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.

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.