<s>[INST] Prove that $\sum _{i=0}^{p} \left( \binom {p+1}{i+1} \times \sum _{j=1}^{n} j^{p-i} \right)=(n+1)^{p+1}-1$ Problem as follows:
Let $S^p_n := 1^p+2^p+3^p+...n^p$ 
Prove that $$\binom {p+1}{1}S^{p}_n+\binom {p+1}{2}S^{p-1}_n+\binom {p+1}{3}S^{p-2}_n+...+\binom {p+1}{p+1}S^{0}_n=(n+1)^{p+1}-1$$
Or, condensed in the capital sigma notation, prove that
$$\sum _{i=0}^{p} \left( \binom {p+1}{i+1} \times \sum _{j=1}^{n} j^{p-i} \right)=(n+1)^{p+1}-1$$
I tried induction on $p$ and got stuck on the inductive step: 
Assume that
$\binom {p+1}{1}S^{p}_n+\binom {p+1}{2}S^{p-1}_n+\binom {p+1}{3}S^{p-2}_n+...+\binom {p+1}{p+1}S^{0}_n=(n+1)^{p+1}-1$, then show that 
$\binom {p+2}{1}S^{p+1}_n+\binom {p+2}{2}S^{p}_n+\binom {p+2}{3}S^{p-1}_n+...+\binom {p+2}{p+2}S^{0}_n=(n+1)^{p+2}-1$.
I tried subtracting the first sum from the second by subtracting alike $S^x_n$'s and using Pascal's identity, and got 
$$\binom {p+2}{1}S^{p+1}_n+\binom {p+1}{2}S^{p}_n+\binom {p+1}{3}S^{p-1}_n+...+\binom {p+1}{p+1}S^{1}_n=n(n+1)^{p+1}$$ 
I have no idea where to go from here. I also tried subtracting the two sums by subtracting alike coefficients, but didn't get anything sensible either. 
 [/INST] Firstly it should be a bit easier to use induction in $n$ instead of $p$, since you have $S_{n+1}^p = S_{n}^p + (n+1)^p$ in the induction step.
Secondly, this can be proven directly without using induction if you consider binomial expansions of $2^p$, $3^p$, ..., $(n+1)^p$ as shown in this table:
\begin{array}{ccc}
2^{p+1}&=&\binom{p+1}{0}1^{p+1}&+&\binom{p+1}{1}1^{p}&+&\ldots&+&\binom{p+1}{p}1^{1}&+&\binom{p+1}{p+1}1^{0}\\
3^{p+1}&=&\binom{p+1}{0}2^{p+1}&+&\binom{p+1}{1}2^{p}&+&\ldots&+&\binom{p+1}{p}2^{1}&+&\binom{p+1}{p+1}2^{0}\\
\vdots&&&&&&&&\\ 
(n+1)^{p+1}&=&\binom{p+1}{0}n^{p+1}&+&\binom{p+1}{1}n^{p}&+&\ldots&+&\binom{p+1}{p}n^{1}&+&\binom{p+1}{p+1}n^{0}\\\hline
S_{n+1}^{p+1}-1^{p+1}&=&\binom{p+1}{0}S_{n}^{p+1}&+&\binom{p+1}{1}S_n^{p}&+&\ldots&+&\binom{p+1}{p}S_{n}^{1}&+&\binom{p+1}{p+1}S_{n}^{0}
\end{array}
Now just subtract $S_{n}^{p+1}$ from last line and notice that $S_{n+1}^{p+1} - S_{n}^{p+1} = (n+1)^{p+1}$, and the identity follows.
</s>