Proving the recurrence of this sequence

Question

My apologies for the title, it would be too long otherwise.

Let $$S_1(n) = \frac{n(n+1)}{2}$$ and for any $n, k \geq 1$ let $$S_{k+1}(n)= \sum_{i=1}^n i^{k+1}$$ Prove the recurrence in terms of $k$: $$S_{k+1}(n) = nS_{k}(n)-\sum_{i=1}^{n-1} S_{k}(i)$$

First, I decided to split it into a double sum and prove $$S_{k+1}(n) = \sum_{j=1}^n \sum_{i=j}^n i^k$$ I wrote this as a table of $i$ and $j$ and summed the rows, getting $$(n\cdot n^k)+((n-1\cdot n^k)+((n-2)\cdot n^k)+\dots+n^k$$ but I'm very confused on how to proceed from here.

Any advice and explanation would be thoroughly appreciated.

Answer 1

$$S_{k+1}(n)=\sum i\cdot i^k=\sum (n-(n-i))i^k$$ $$=nS_k(n)-\sum (n-i)i^k$$

So you need $$\sum S_k(n)=\sum (n-i)i^k$$ Can you see this last equation ? $i^k$ only begins to appear after the first $i$ terms.

Answer 2

\begin{eqnarray*} \sum_{i=1}^{n-1} S_k(i) = \sum_{i=1}^{n-1} \sum_{j=1}^{i} j^k =\sum_{j=1}^{n-1} \sum_{i=j}^{n-1} j^k =\sum_{j=1}^{n-1} (n-j) j^k = n\sum_{j=1}^{n-1} j^k -\sum_{j=1}^{n-1} j^{k+1} \\= n\sum_{j=1}^{n} j^k -\sum_{j=1}^{n} j^{k+1}=nS_k(n)-S_{k+1}(n). \end{eqnarray*}