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.

Solution 1:

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.$$

Solution 2:

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\}$.