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$

Question

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.

Answer 1

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.