$1^p+..+n^p=\sum_{k=1}^{n}k^p$
Suppose I fix an $n$ and set $p=1$
Then one can prove by induction that
$1+2+...+n=\frac{1}{2}(n)(n+1)$
Now there is an identity and I am looking for a proof for it that
$(n+1)^{p+1}-1=(p+1)\sum_{k=1}^{n}k^p+\binom{p+1}{2}\sum_{k=1}^{n}k^{p-1}+\binom{p+1}{3}\sum_{k=1}^{n}k^{p-2}+...+\binom{p+1}{p+1}\sum_{k=1}^{n}k^0$
$\iff (n+1)^{p+1}-1= \sum_{j=1}^{p+1}\binom{p+1}{j}\sum_{k=1}^{n}k^{p+1-j}$
Hope somebody can explain how someone (according to the book La Place) could came up with something like that, i.e is there maybe a combinatorial thought behind the Formula? And also how can I prove it by induction?
Edit:
I am trying to understand if you have the Formula like $\frac{n^2+n}{2}$ how do you see the Connection with $(n+1)^2-1$?
I.e. that you only have to manipulate the first Formula a Little bit to get to the other Formula?And also that those manipulations can be generalized was it just coincidence? This Formula must be derived somehow from the binomial Theorem but I don't see how.
$\displaystyle (j+1)^{p+1}=\sum\limits_{k=0}^{p+1} {\binom {p+1} k} j^k$
$\displaystyle (j+1)^{p+1} - j^{p+1} =\sum\limits_{k=0}^p {\binom {p+1} k} j^k$
$\displaystyle \sum\limits_{j=1}^n \left((j+1)^{p+1} - j^{p+1}\right) = \sum\limits_{j=1}^n \sum\limits_{k=0}^p {\binom {p+1} k} j^k$
$\displaystyle (n+1)^{p+1} - 1 = \sum\limits_{k=0}^p {\binom {p+1} k} \sum\limits_{j=1}^n j^k$