Prove that this is true

Question

$$\sum\limits_{i=1}^{n}i^x = P_{x+1}(n)$$ Let x be any nonnegative integer and show that there is a polynomial $P_{x+1}$ of degree $x+1$ for every $n$ greater than or equal to $1$.

Answer 1

Hint Prove that there exists a polynomial $Q_{x+1}(n)$ with the property that [ Q_{x+1}(n+1)-Q_{x+1}(n)=n^x \,. ]

You can prove this for example by observing that $n+1-n, (n+1)^2-n^2,.., (n+1)^{x+1}-n^{x+1}$ are linearly independent, thus a basis for the space of polynomials of degree at most $x$ in the variable $n$.

Once you do this, you can easily prove that for the right constant $C$, which can be obtained by setting $n=1$, the polynomial [ P_{x+1}(n)=Q_{x+1}(n)+C \,, ] works.

Second solution

$$(i+1)^{x+1}=i^{x+1}+(x+1)i^x +\sum_{j=2}^{x+1} \binom{x+1}{j} i^{k+1-j} \,.$$

Sum this from $i=1$ to $n$, cancel the common terms, and use induction by $x$.