I have this problem:
Let $S_{1}(n) = \sum_{i=1}^n = 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) = n S_k(n) - \sum_{i=1}^{n-1} S_k(i)$.
I was also given a hint in that:
Prove first that $S_{k+1}(n) = \sum_{j=1}^n \sum_{i=j}^n i^k$.
I was also suggested to make a table but I am unsure what I am actually using as variables ($i$, $j$, or $n$?). I understand that if I make a table I could sum the rows to find the difference between the two sums. I am also unaware of what the "hint" is suggesting and how it helps with the overall question.
The formula in the hint can be proved by just splitting $i^{k+1}$ is $i$ times $i^{k}$, writing $i$ as $\sum_{j=1} ^{i} 1$ and then interchanging the order of summation. The constraint $j \leq i$ is same as $i \geq j$ so the sum w.r.t. $i$ goes from $j$ to $n$. Now to prove result using the hint simply write $\sum_{i=j}^{n} i^{k}$ as $\sum_{i=1}^{n} i^{k} -\sum_{i=1}^{j-1} i^{k}$. when you sum the first term over j you get $nS_k (n)$. Now complete the proof!