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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

We are trying to find the correction polynomial of degree p $$a(k,p)$$ where

$$ a(k,p)=\sum_{n=1}^k(n^p)-\frac{k}{(p+1)!}\prod_{n=1}^{p}(nk+1)=\sum_{f=0}^p(a_fx^f) $$

The correction polynomial was of degree three for the sum of cubes and degree four for the sum of tesseracts. Assuming that the polynomial degree is always p then, since we know what the polynomial's value should be at infinitely many points, we can turn the problem of finding the polynomial's coefficients into a p by p linear system. Maybe try to get some computer algebra system to solve the system and see if there is any obvious pattern.