Sum of $k$-th powers Given:
$$
P_k(n)=\sum_{i=1}^n i^k
$$
and $P_k(0)=0$, $P_k(x)-P_k(x-1) = x^k$ show that:
$$
P_{k+1}(x)=(k+1) \int^x_0P_k(t) \, dt + C_{k+1} \cdot x
$$
For $C_{k+1}$ constant.
I believe a proof by induction is the way to go here, and have shown the case for $k=0$. This is where I'm stuck. I have looked at the right hand side for the k+1 case:
$$
(k+2)\int^x_0P_{k+1}(t) \, dt + C_{k+2} \cdot x
$$
and I don't see how this reduces to $P_{k+2}(x)$. Even if we are assuming the kth case, replacing $P_{k+1}$ in the integrand of the $(k+1)$-st case just makes it more messy. I am not looking for the answer just a push in the right direction. I can see that each sum ends up as a polynomial since expressions like $P_1(x) = 1+2+\cdots+x=\frac{x(x+1)}{2}$, but I don't know how to do that for arbitrary powers, and I believe I don't need to in order to solve this problem.
 A: Since $P_k(x)-P_k(x-1)=x^k$, 
$$P_k'(x) - P_k'(x-1) = kx^{k-1} = k(P_{k-1}(x)-P_{k-1}(x-1))$$
Hence, integrating from $0$ to $x$, we find
$$P_k(x)-P_k(x-1) - P_k(-1) = I_k(x) - I_k(x-1)$$
where $I_k(x) = k\int_0^x P_{k-1}(t) dt$. Both $P_k(x)$ and $I_k(x)$ are polynomials.
Let $c_k = P_k(-1)$. Then we can rewrite the above as
$$(P_k(x) - c_k x) - (P_k(x-1)-c_k(x-1)) = I_k(x) - I_k(x-1)$$
Now we have the lemma:

Suppose that $f,g$ are two polynomials with coefficients in $\mathbb
 C$ such that $f(0)=g(0)$ and $$f(x)-f(x-1) = g(x)-g(x-1).$$
Then $f=g$.

Proof: By telescoping, it follows that $f(x) - f(x-m) = g(x)-g(x-m)$ for every integer $m$. Taking $x=m$, we have $f(m)-f(0) = g(m)-g(0)$, hence $f(m)=g(m)$ for all integers $m$. It follows that $f=g$.
Now, it follows with $f(x)=P_k(x)-c_kx$ and $g(x) = I_k(x)$ that
$$P_k(x)-c_kx = k \int_0^x P_{k-1}(t)dt.$$
A: From the definition of $P_k(n)$ we get
$$
P_k(n) = \sum_{i=1}^n i^k \Rightarrow 
P_0(n) = \sum_{i=1}^n 1 = n.
$$
We now use complete induction over $k$ to proof the statement $S(k)$
$$
P_k(x) = k \int\limits_0^x P_{k-1}(t) \, dt + C_k \, x \quad (*)
$$
Base case
For $k=1$ we have $S(1)$:
$$
1 \int\limits_0^x P_0(t) \, dt + C_1 \, x 
=
\int\limits_0^x t \, dt + C_1 \, x
=
\frac{1}{2} x^2 + C_1 \, x 
$$
which corresponds to the well known Gauss summation formula $P_1(n)$, if $C_1 = 1/2$.
Inductive step
Assuming equation $(*)$ is true for $\{ 1, \ldots, k \}$ we perform the recursion by starting with $S(k)$ and then applying $S(k-1), S(k-2), \ldots$ until we hit the bottom with $S(1)$ and get $P_0 = \mbox{id}$. That integrand is then simple enough to perform the the $k$ iterated integrations:
\begin{align}
P_k(x) 
&= 
k \int\limits_0^x P_{k-1}(t_k) \, dt_k + C_k \, x \\
&=
k \int\limits_0^x \left( (k-1) \int\limits_0^{t_k} 
P_{k-2}(t_{k-1}) \, dt_{k-1} + C_{k-1} \, t_k \right) \, dt_k + C_k \, x  \\
&=
k (k-1) \int\limits_0^x \int\limits_0^{t_k} 
P_{k-2}(t_{k-1}) \, dt_{k-1} \, dt_k + \frac{k}{2} C_{k-1} \, x^2 + C_k \, x  \\
&=
k! \int\limits_0^x \cdots \int\limits_0^{t_2} 
P_0(t_1) \, dt_1 \cdots \,dt_k
+ \sum_{j=1}^k C_{k-j+1} \frac{k!}{(k-j+1)!j!} x^j \\
&=
k! \int\limits_0^x \cdots \int\limits_0^{t_2} 
t_1 \, dt_1 \cdots \,dt_k
+ \sum_{j=1}^k \binom{k}{j} \frac{C_{k-j+1}}{k-j+1} x^j \\
&=
k! \int\limits_0^x \cdots \int\limits_0^{t_3}
\frac{1}{2}t_2^2 \, dt_2 \cdots \,dt_k
+ \sum_{j=1}^k \binom{k}{j} \frac{C_{k-j+1}}{k-j+1} x^j \\
&=
k! \int\limits_0^x
\frac{1}{k!}t_k^k \,dt_k
+ \sum_{j=1}^k \binom{k}{j} \frac{C_{k-j+1}}{k-j+1} x^j \\
&=
\frac{1}{k+1}x^{k+1} 
+ \sum_{j=1}^k \binom{k}{j} \frac{C_{k-j+1}}{k-j+1} x^j \\
\end{align}
Then we try to arrive at $S(k+1)$:
\begin{align}
(k+1) \int\limits_0^x P_k(t) \, dt + C_{k+1} \, x
&=
(k+1) \int\limits_0^x \left(
\frac{1}{k+1}t^{k+1} + 
\sum_{j=1}^k \binom{k}{j} \frac{C_{k-j+1}}{k-j+1} t^j \right)
\, dt \\
& + C_{k+1} \, x \\
&=
(k+1) \left(
\frac{1}{(k+1)(k+2)}x^{k+2} 
+ \right. \\
& \left. \sum_{j=1}^k \binom{k}{j} \frac{C_{k-j+1}}{(k-j+1)(j+1)} x^{j+1}
\right) + C_{k+1} \, x \\
&=
\frac{1}{k+2}x^{k+2} 
+ \sum_{j=1}^k \binom{k}{j} \frac{(k+1)C_{k-j+1}}{(k-j+1)(j+1)} x^{j+1}
+ C_{k+1} \, x \\
&=
\frac{1}{k+2}x^{k+2} 
+ \sum_{j=1}^k \binom{k+1}{j+1} \frac{C_{k-j+1}}{k-j+1} x^{j+1}
+ C_{k+1} \, x \\
&=
\frac{1}{k+2}x^{k+2} 
+ \sum_{j=2}^{k+1} \binom{k+1}{j} \frac{C_{k+1-j+1}}{k+1-j+1} x^j
+ C_{k+1} \, x \\
&=
\frac{1}{k+2}x^{k+2} 
+ \sum_{j=1}^{k+1} \binom{k+1}{j} \frac{C_{k+1-j+1}}{k+1-j+1} x^j \\
&=
P_{k+1}(x)
\end{align}
Thus $S(k+1)$ follows.
By the principle of induction $(*)$ holds for all $k \in \mathbb{N} \setminus \{ 0\}$.
A: Hm. This problem is weird, in that as defined $P_k(n)$ is only defined on the naturals. Although as you noted, you can find a closed form and evaluate it at an arbitrary point.
Have you tried taking the derivative of both sides and using Fundamental Thm of Calculus? That would get rid of the integral, and turns the $C_{k+1}\cdot x$ term to just a constant, which looks more appealing.
