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

• You can't write $\sum_{n=1}^k1=n$ as $n$ is not defined on the right-hand side. It's $\sum_{n=1}^k1=k$. You made this error several times in your post. Mar 29, 2018 at 18:23
• oops, I'll fix that! Mar 29, 2018 at 18:23
• More generally $$\sum_{n=1}^k n^i=\frac{k^{i+1}}{i+1} + O(k^i).$$ Also, it is a polynomial. Mar 29, 2018 at 18:30
• I think it is great that you get your hands dirty and look deeper into things. That's how you become "smart" mathematics-$wise$. You could compute the formula of your error $r$ with respect to $k$ to understand why you get such results. Mar 29, 2018 at 18:34
• Another approach (possibly overkill) is to use recurrence relations: Fix $k > 1$. Define $a_0 = 1$ and $a_n = a_{n-1} + n^k$. You can then show that $a_n = \frac{n^{k+1}}{k+1} + O_k(n^k)$ as @ThomasAndrews mentions above. Mar 29, 2018 at 19:11

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

• This may be a stupid question, and is somewhat unrelated, but does it make sense to say that the pattern breaks down at the cube step because higher dimensional things break down? (Also, I'm still thinking about what you've replied) Mar 29, 2018 at 20:25
• Yeah, I'm not sure you can make some broad argument like that. Mar 29, 2018 at 20:29
• Thanks! Although I wish I found something unique :) Mar 30, 2018 at 20:44
• Did Faulhabar discover them similarly to how I did, or is it not known? Mar 30, 2018 at 22:14

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.

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.