Sum of the first integer powers of $n$ up to k

The general result is called Faulhaber's Formula.

A hint in the general direction.

Let $f_i(x)=x(x+1)(x+2)\cdots(x+(i-1)),$ and $f_0(x)=1.$ We call $f_i$ the "rising factorial," and is sometimes written $x^{(i)}.$

Note the property that $f_{i+1}(x)-f_{i+1}(x-1)=(i+1)f_i(x).$

So, we can telescope the sum:

$$\sum_{n=1}^{k}f_i(n)=\frac{1}{i+1}\sum_{n=1}^{k}\left(f_{i+1}(n)-f_{i+1}(n-1)\right)= \frac{f_{i+1}(k)}{i+1}.$$

since $f_{i+1}(0)=0.$

Now, what you can see is that since $f_i(x)$ is of degree $i$ and monic (the lead coefficient is $1$) we can write:

$$x^i = f_i(x)+O(x^{i-1})$$

where the rest is a polynomial.

So $$\sum_{n=1}^{k} n^i =\frac{f_{i+1}(k)}{i+1}+O(k^{i})=\frac{k^{i+1}}{i+1}+O(k^{i}).$$

Now, your polynomial $$\frac{x(x+1)(2x+1)(3x+1)\cdots((ix+1)}{(i+1)!}=\frac{x^{i+1}}{i+1}+O(x^i)$$ too.

So these are generally going to grow similarly.

But if we look at the second term, then we get, for $i>0:$

$$x^{i}=f_i(x)-\frac{i(i-1)}{2}f_{i-1}(x)+O(x^{i-2})$$

So:

$$\sum_{n=0}^{k} n^i = \frac{f_{i+1}(k)}{i+1}-\frac{(i-1)f_{i}(k)}{2} +O(k^{i-1})$$

A little fiddling gives you that when $i>0$:

$$\sum_{n=1}^{k} n^i = \frac{k^{i+1}}{i+1} +\frac{k^i}{2}+O(k^{i-1})$$ for $i>0.$

The coefficient $k^{i}$ in your polynomial is $\frac{1}{i+1}\left(1+\frac{1}{2}+\cdots+\frac1{i}\right)\sim \frac{\log i}{i+1}.$ So your second coefficient goes to $0$ as $i\to\infty$, so the difference between the sum and your polynomial will approach $\frac{1}{2}x^i.$

Looking for the general solution is tricky, but we can find an approach for each $i$. For example, let $i=5.$

We can work out that $$x^5=f_5(x)-10f_4(x)+25f_3(x)-15f_2(x)+f_1(x),$$ so we get:

$$\sum_{n=1}^{k} n^5 = \frac{1}{6}f_6(k)-2f_5(k)+\frac{25}{4}f_4(k)-5f_3(k)+\frac{1}{2}f_2(k)$$

Then we can expand this out to get the final form.

Note that since $n^i$ is zero a $n=0$ when $i>0$, there is never an $f_0$ term in the expression for $n^i$ in terms of $f_j,$ and hence the result of the sum will only have terms $f_j$ with $j\geq 2$, and hence the resulting polynomial will be divisible by $k(k+1)$ when $i>0.$

We can use telescoping sums to find formula for $$\sum_1^n k^p $$ for $p\ge 1$

Note that $$ (k+1)^2 - k^2 =2k+1 \implies$$

$$ \sum_1^n \big[(k+1)^2 - k^2\big]=\sum_1^n (2k+1)\implies $$

$$ (n+1)^2 -1=2 \sum_1^n k + n\implies $$

$$\sum_1^n k = \frac {n(n+1)}{2}$$

Similarly we can find formula for $$\sum_1^n k^2 $$

by using $$(k+1)^3 - k^3 =3k^2+ 3k+1$$

and so forth.