<s>[INST] Faulhaber Formula Identity I have to show the following identity:
$$ S_n^p := 1^p+2^p+...+n^p $$
$$ (p+1)S_n^p+\binom{p+1}{2}S_n^{p-1}+\binom{p+1}{3}S_n^{p-2}+...+S_n^0=(n+1)^{p+1}-1 $$
What I did first is to use the binomial theorem on the term the right side of the equation, which results in:
$$ (n+1)^{p+1}-1=\binom{p+1}{1}n+\binom{p+1}{2}n^{2}+...+\binom{p+1}{p}n^{p}+n^{p+1} $$
From here I am not quite sure how both of these terms are equal. Any hint on how I could proceed?
 [/INST] Suppose we have
$$S_n^p = \sum_{q=1}^n q^p$$
and we seek to evaluate
$$\sum_{q=1}^{p+1} {p+1\choose q} S_n^{p+1-q}
= - S_n^{p+1}
+ \sum_{q=0}^{p+1} {p+1\choose q} S_n^{p+1-q}.$$
Observe that
$$q^p = \frac{p!}{2\pi i}
\int_{|z|=\epsilon} z^{p-1} \exp(q/z) \; dz.$$
Introduce the generating function
$$f(w) = \sum_{p\ge 0} S_n^p \frac{w^p}{p!}.$$
We thus have for $f(w)$
$$f(w) = 
\sum_{p\ge 0} \frac{w^p}{p!} 
\frac{p!}{2\pi i}
\int_{|z|=\epsilon} z^{p-1}
\sum_{q=1}^n \exp(q/z) \; dz
\\ = \sum_{q=1}^n
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \exp(q/z) \frac{1}{z}
\sum_{p\ge 0} z^p w^p \; dz
\\ = \sum_{q=1}^n
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \exp(q/z) \frac{1}{z}
\frac{1}{1-zw} \; dz.$$
Note that the quantity we seek to evaluate is
$$-S_n^{p+1} + (p+1)! [w^{p+1}] f(w) \exp(w)$$
where the product term is given by the integral
$$\frac{(p+1)!}{2\pi i}
\int_{|w|=\epsilon} \frac{1}{w^{p+2}} \exp(w)
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \sum_{q=1}^n \exp(q/z)
\frac{1}{z}
\frac{1}{1-zw} 
\; dz \; dw.$$
We evaluate the  integral in $z$ using the negative of  the sum of the
residues at $z=1/w$ and $z=\infty.$
For the residue at $z=1/w$ re-write the integral as follows:
$$-\frac{(p+1)!}{2\pi i}
\int_{|w|=\epsilon} \frac{1}{w^{p+3}} \exp(w)
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \sum_{q=1}^n \exp(q/z)
\frac{1}{z}
\frac{1}{z-1/w} 
\; dz \; dw.$$
This yields
$$-\frac{(p+1)!}{2\pi i}
\int_{|w|=\epsilon} \frac{1}{w^{p+3}} \exp(w)
\sum_{q=1}^n \exp(qw) \times w \; dw
\\ = -\frac{(p+1)!}{2\pi i}
\int_{|w|=\epsilon} \frac{1}{w^{p+2}}
\sum_{q=1}^n \exp((q+1)w) \; dw.$$
The negative of this is
$$\sum_{q=1}^n (q+1)^{p+1}.$$
For the residue at infinity we get
$$-\mathrm{Res}_{z=0} 
\frac{1}{z^2} 
\sum_{q=1}^n \exp(qz) \times z \times \frac{1}{1-w/z}
\\ = -\mathrm{Res}_{z=0} 
\sum_{q=1}^n \exp(qz) \times \frac{1}{z-w} = 0.$$
We have shown that
$$- S_n^{p+1}
+ \sum_{q=0}^{p+1} {p+1\choose q} S_n^{p+1-q}
= - S_n^{p+1} + \sum_{q=1}^n (q+1)^{p+1}
= (n+1)^{p+1} - 1,$$
as claimed.
</s>