# Sums of rising factorial powers

Doodling in wolfram, I found that $$\sum^{k}_{n=1}1=k$$ The formula is pretty obvious, but then you get $$\sum^{k}_{n=1}n=\frac{k(k+1)}{2}$$ That is a very well known formula, but then it gets interesting when you calculate $$\sum^{k}_{n=1}n(n+1)=\frac{k(k+1)(k+2)}{3}\\ \sum^{k}_{n=1}n(n+1)(n+2)=\frac{k(k+1)(k+2)(k+3)}{4}$$ And so on. There is an obvious pattern that I really doubt is a coincidence, but I have no idea how to prove it in the general case. Any ideas?

-
Pascal's triangle comes to mind here –  Omnomnomnom Sep 4 '13 at 3:47
@Omnomnomnom I thought about it but I was unable to introduce binomials there. However, you can generalize the hypothesis using factorials, but usually working with factorials is harder than not doing so(At least I would have a very hard time trying to do so). –  chubakueno Sep 4 '13 at 3:51
These are essentially the sums for the general $d$ dimensional simplex. –  Jaycob Coleman Sep 4 '13 at 4:02
It's overkill, but you could expand and apply en.wikipedia.org/wiki/Faulhaber%27s_formula –  dls Sep 4 '13 at 4:11
@dls I think that in that case the interesting part would go backwards: That expanding and a applying Faulhaber´s yields such a regular and simple result :) –  chubakueno Sep 4 '13 at 4:22
show 1 more comment

You can argue any given case by induction. I will take your last,$$\sum^{k}_{n=1}n(n+1)(n+2)=\frac{k(k+1)(k+2)(k+3)}{4}$$ for the example, but I think it is easy to see how it gets carried forward. The base case is simply $1\cdot 2\cdot 3=1\cdot 2\cdot 3\cdot \frac 44$ If it is true up to $k$, then $$\sum^{k+1}_{n=1}n(n+1)(n+2)\\=\sum^{k}_{n=1}n(n+1)(n+2)+(k+1)(k+2)(k+3)\\=\frac{k(k+1)(k+2)(k+3)}{4}+(k+1)(k+2)(k+3)\frac {k+4-k}4\\=\frac{(k+1)(k+2)(k+3)(k+4)}{4}$$

-
Thanks! Just changing the $2$, $3$ and $4$ by $x$,$x+1$ and $x+2$ does the work of generalizing it very nicely. –  chubakueno Sep 4 '13 at 3:59

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.