Request for a proof that $\sum\limits_{i=1}^n i^{k+1}=(n+1)\sum\limits_{i=1}^n i^k-\sum\limits_{p=1}^n\sum\limits_{i=1}^p i^k$

Question

Prove $$\sum_{i=1}^n i^{k+1}=(n+1)\sum_{i=1}^n i^k-\sum_{p=1}^n\sum_{i=1}^p i^k \tag1$$ for every integer $k\ge0$.

By principle of induction,

$$\sum_{i=1}^n i = n(n+1)- \sum_{p=1}^n p$$ $$2\sum_{i=1}^n i = n(n+1)$$ $$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$ $\implies$$(1)$ is true for k equals to zero.

Assume $(1)$ is true. $$\sum_{i=1}^n i^{k+2}=(n+1)\sum_{i=1}^n i^{k+1}-\sum_{p=1}^n\sum_{i=1}^p i^{k+1}\tag2$$ We prove $(2)$ is true.

From $(2)$,

$$\begin{align} RHS & = (n+1)\left[(n+1)\sum_{i=1}^n i^k-\sum_{p=1}^n\sum_{i=1}^p i^k \right]-\sum_{p=1}^n\sum_{i=1}^p i^{k+1}\\ & = (n+1)^2\sum_{p=1}^n p^k-(n+1)\sum_{p=1}^n\sum_{i=1}^p i^k-\sum_{p=1}^n\sum_{i=1}^p i^{k+1}\\ & = \sum_{p=1}^n\left[(n+1)^2p^k-(n+1)\sum_{i=1}^p i^k-\sum_{i=1}^p i^{k+1}\right]\\ & = \sum_{p=1}^n\left[(n+1)^2p^k-\sum_{i=1}^p (n+1+i)i^k\right]\\ \end{align}$$

By examining $(2)$,

$$\sum_{p=1}^n\left[(n+1)^2p^k-\sum_{i=1}^p (n+1+i)i^k\right]=\sum_{p=1}^n p^{k+2}=LHS\tag3$$

We should be able to get $(3)$.

Anyone knows how to prove $(3)$?

Answer 1

Rather than proceed using induction, I thought it might be instructive to present a straightforward approach.

To that end we proceed by using the Newton Series for summation by parts with $f_i=i$ and $g_i=i^k$.

Then, we can write

$$\begin{align} \sum_{i=1}^n i^{k+1}&=\sum_{i=1}^n (i)(i)^k\\\\ &=n\sum_{i=1}^n i^k - \sum_{j=1}^{n-1}\sum_{i=1}^j i^k\\\\ &=n\sum_{i=1}^n i^k - \sum_{j=1}^{n}\sum_{i=1}^j i^k +\sum_{i=1}^n i^k\\\\ &=(n+1)\sum_{i=1}^n i^k - \sum_{j=1}^{n}\sum_{i=1}^j i^k \end{align}$$

as was to be shown!

Answer 2

You can also simply reverse the order of summation in the double sum:

$$\begin{align*} (n+1)\sum_{i=1}^ni^k-\sum_{p=1}^n\sum_{i=1}^pi^k&=(n+1)\sum_{i=1}^ni^k-\sum_{i=1}^n\sum_{p=i}^ni^k\\ &=\sum_{i=1}^n(n+1)i^k-\sum_{i=1}^n(n-i+1)i^k\\ &=\sum_{i=1}^n\big((n+1)-(n+1-i)\big)i^k\\ &=\sum_{i=1}^ni\cdot i^k\\ &=\sum_{i=1}^ni^{k+1} \end{align*}$$

Answer 3

In the RHS, a term $j^k$ is taken $n+1$ times in the first sum and $n-j+1$ times in the second, hence it contributes $(n+1-n+j-1)j^k=j^{k+1}$ to the total.

---

$$\left|\begin{matrix} 1\cdot1^k\\ 2\cdot2^k\\ 3\cdot3^k\\ 4\cdot4^k \end{matrix}\right|=\left|\begin{matrix} 1^k&1^k&1^k&1^k&1^k\\ 2^k&2^k&2^k&2^k&2^k\\ 3^k&3^k&3^k&3^k&3^k\\ 4^k&4^k&4^k&4^k&4^k \end{matrix}\right|-\left|\begin{matrix} 1^k&1^k&1^k&1^k\\ 2^k&2^k&2^k\\ 3^k&3^k\\ 4^k \end{matrix}\right|$$