Proving that $\frac {(n+1)n(n-1)...(n-i)}{i+1}$ can be used as the summ of $k^h$

Question

I have previously proved that $$\sum_{k=i}^{n} k(k-1)(k-2)\cdots(k-i+1) = \frac{(n+1)\cdot n\cdot (n-1)\cdots(n-i+1)}{i+1}$$

From here I am supposed to show that the formula above can be used to compute the sum of $k^h$, for example, $\sum_{k=1}^{n}k^2$ or $\sum_{k=1}^{n}k^3$, starting with $$\sum_{k=1}^{n}k=\frac{n(n+1)}{2}$$ I cannot figure out the connection between these and do not know where to start...

Answer 1

Yes, it can be used.

Example with $\sum_{k=1}^{n}k^2$

$\sum_{k=1}^{n}k^2$

$=\sum_{k=1}^{n}k(k-1+1)$

$=(\sum_{k=1}^{n}k(k-1)) + \sum_{k=1}^{n}k$

$=(\sum_{k=2}^{n}k(k-1)) + \sum_{k=1}^{n}k$ ( means that $i = 2$)

$=\frac{(n+1)n(n-1)}{3} + \frac{n(n+1)}{2}$

$=\frac{(n+1)n(2(n-1) + 3)}{6}$

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

---

Example with $\sum_{k=1}^{n}k^3$

$\sum_{k=1}^{n}k^3$

$=\sum_{k=1}^{n}k(k-1+1)(k-2+2)$

$=\sum_{k=1}^{n}k((k-1)(k-2) + 2(k-1)+(k-2)+2)$

$=\sum_{k=1}^{n}k((k-1)(k-2) + 3k-2)$

$=\sum_{k=1}^{n}k(k-1)(k-2) + 3\sum_{k=1}^{n}k^2 - 2\sum_{k=1}^{n}k$

$=\sum_{k=3}^{n}k(k-1)(k-2) + 3\sum_{k=1}^{n}k^2 - 2\sum_{k=1}^{n}k$ ( means that $i=3$)

$=\frac{(n+1)n(n-1)(n-2)}{4} + 3\frac{n(n+1)(2n+1)}{6} - 2\frac{n(n+1)}{2}$

$=\frac{n^2 (n + 1)^2}{4}$

---

Same way in higher power

Answer 2

It is convenient to use the falling factorial notation \begin{align*} k^{\underline{i}}:=k(k-1)\cdots (k-i+1) \end{align*}

With this notation OPs identity can be written as \begin{align*} \sum_{k=i}^nk^{\underline{i}}=\frac{(n+1)^{\underline{i+1}}}{i+1} \end{align*}

and since summands with $1\leq k<i$ are zero we can also write \begin{align*} \color{blue}{S_i(n):=\sum_{k=1}^nk^{\underline{i}}=\frac{(n+1)^{\underline{i+1}}}{i+1}}\tag{1} \end{align*} We can now iteratively use $S_i(n), i=1,2,3,\ldots $ to calculate \begin{align*} \sum_{k=1}^nk^i \end{align*}

Case $i=1$:

Since $k=k^{\underline{1}}$ we obtain from (1) \begin{align*} \color{blue}{\sum_{k=1}^n k}=S_1(n)=\frac{(n+1)^{\underline{2}}}{2} \color{blue}{=\frac{1}{2}\left(n+1\right)n}\tag{2} \end{align*}

Case $i=2$:

Since $k^2=k(k-1)+k=k^{\underline{2}}+k^{\underline{1}}$ we obtain from (1) and (2) \begin{align*} \color{blue}{\sum_{k=1}^n k^2}&=S_2(n)+S_ 1(n)=\frac{(n+1)^{\underline{3}}}{3}+\frac{(n+1)^{\underline{2}}}{2}\\ &=\frac{(n+1)n(n-1)}{3}+\frac{(n+1)n}{2}\\ &\,\,\color{blue}{=\frac{1}{6}\left(2n^2+3n^2+n\right)} \end{align*}

This way we can iteratively calculate $\sum_{k=1}^n k^i, i=3,4,\ldots$. Here it is useful to know that \begin{align*} k^i=\sum_{j=0}^i\begin{Bmatrix} i \\ j \end{Bmatrix} k^{\underline{j}} \end{align*} with $\begin{Bmatrix} i \\ j \end{Bmatrix}$ the Stirling numbers of the second kind.

Note: The sum formula (1) is a discrete analogon to \begin{align*} \int_{0}^xt^i\,dt=\frac{x^{i+1}}{i+1} \end{align*} which is a main theme in this answer .