# 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. – Mathematician 42 Mar 29 '18 at 18:23
• oops, I'll fix that! – Robbie Mar 29 '18 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. – Thomas Andrews Mar 29 '18 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. – Max Mar 29 '18 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. – JavaMan Mar 29 '18 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) – Robbie Mar 29 '18 at 20:25
• Yeah, I'm not sure you can make some broad argument like that. – Thomas Andrews Mar 29 '18 at 20:29
• Thanks! Although I wish I found something unique :) – Robbie Mar 30 '18 at 20:44
• Did Faulhabar discover them similarly to how I did, or is it not known? – Robbie Mar 30 '18 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.