<s>[INST] Sum of the first integer powers of $n$ up to k Pascal's triangle has a lot of interesting patterns in it; one of which is the triangular numbers and their extensions. Mathematically:
$$\sum_{n=1}^k1=\frac{k}{1}$$
$$\sum_{n=1}^kn=\frac{k}{1}\cdot\frac{k+1}{2}$$
$$\sum_{n=1}^kn^2=\frac{k}{1}\cdot\frac{k+1}{2}\cdot\frac{2k+1}{3}$$
At first, we could guess that the next summation is:
$$\sum_{n=1}^kn^3 ?=\frac{k}{1}\cdot\frac{k+1}{2}\cdot\frac{2k+1}{3}\cdot\frac{3k+1}{4}$$
Yet this is off. However, it is off geometrically. Notice:
$$\left(\sum_{n=1}^kn^3\right)-\frac{k}{1}\cdot\frac{k+1}{2}\cdot\frac{2k+1}{3}\cdot\frac{3k+1}{4}=error$$
$$k=1, r=0$$
$$k=2, r=0.25$$
$$k=3, r=1$$
$$k=4, r=2.5$$
$$k=5, r=5$$
$$k=6, r=8.75$$
...
Consider the ratios of the errors:
$$er(k)=\frac{r(k+1)}{r(k)}$$
$$k=1, r=udf$$
$$k=2, r=4$$
$$k=3, r=2.5$$
$$k=4, r=2$$
$$k=5, r=1.75$$
$$k=6, r=1.6$$
Then, rewriting the error as a function of n starting at k = 5:
$$1.75=2.5-\frac{1.5}{2}$$
$$1.6=2.5-\frac{1.5}{2}-\frac{1.5}{10}$$
$$1.5=2.5-\frac{1.5}{2}-\frac{1.5}{10}-\frac{1.5}{15}$$
$$1.42857=2.5-\frac{1.5}{2}-\frac{1.5}{10}-\frac{1.5}{15}-\frac{1.5}{21}$$
The denominators in the series are from pascals triangle: (3rd columns, or dependent again on the triangular numbers)
Then the total formula for equating the two is:
$$\left(\frac{k}{1}\cdot\frac{\left(k+1\right)}{2}\cdot\frac{\left(2k+1\right)}{3}\cdot\frac{\left(3k+1\right)}{4}\right)-\left(\sum_{n=1}^kn^3\right)+\frac{1}{24}\left(k-1\right)k\left(k+1\right)=0$$
Super interesting!
At least, I thought it was interesting how this the error is related back to the previous power's formula. Am I missing something obvious? Any input is greatly appreciated. (I'm not smart, so in the likely event I missed something obvious try not to be too harsh)
Update:
For the next power (4), I found the formula with trial and error:
$$\left(\frac{k}{1}\cdot\frac{\left(k+1\right)}{2}\cdot\frac{\left(2k+1\right)}{3}\cdot\frac{\left(3k+1\right)}{4}\cdot\frac{\left(4k+1\right)}{5}\right)+\frac{1}{24}\left(k-1\right)k\left(k+1\right)+\frac{1}{12}\left(k-1\right)k\left(k+1\right)k$$
Any ideas on power (5) and so on? I'll continue to try and generalize it.
 [/INST] 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.$
</s>