# Conjecture: $\sum\limits_{k=1}^nk^m=S_3(n)\times\frac{P_{m-3}(n)}{N_m}$ for odd $m>1 \ ;\ =S_2(n)\times\frac{P_{m-2}'(n)}{N_m}$ for even $m$.

When I was in high school, I was fascinated by $$\displaystyle\sum\limits_{k=1}^n k= \frac{n(n+1)}{2}$$ so I tried to find the general solution for $$\displaystyle\sum\limits_{k=1}^n k^m$$ s.t $$m \in \mathbb{N}$$. I used a similar approach to my answer here

My approach was turning $$n^m$$ to $$n(n-1)(n-2)\dots (n-m+1)+ f(n)$$ and to use the fact that $$\displaystyle\dbinom{n}{k}+\dbinom{n}{k+1}= \dbinom{n+1}{k+1}$$ $$f(n)$$ will be combination of sums $$\displaystyle\sum_{k=1}^n k^i$$ st $$i which I evaluated before

I was able to to find the sum up to $$m=6$$. Here, I tried to search for a pattern to find the general solution of $$\sum\limits_{k=1}^n k^m$$ s.t $$m \in \mathbb{N}$$ which I failed to do, but I noticed this pattern:
$$\\[3pt]$$ $$S_1(n):={\sum\limits_{k=1}^n k= \frac{n(n+1)}{2}}$$

$$S_2(n):={\sum\limits_{k=1}^n k^2= \color{blue}{\frac{n(2n+1)(n+1)}{6}}}$$

$$S_3(n):={\sum\limits_{k=1}^n k^3= \color{red}{\frac{\color{red}{n^2(n+1)^2}}{\color{red}{4}}}}$$

$$S_4(n):={\sum\limits_{k=1}^n k^4=\color{blue}{\frac{n(2n+1)(n+1)}{6}} \times \frac{3n^2+3n-1}{ 5}}$$

$$S_5(n):={\sum\limits_{k=1}^n k^5= \color{red}{\frac{\color{red}{n^2(n+1)^2}}{\color{red}{4}}} \times\frac{2n^2+2n-1}{ 3}}$$

$$S_6(n):={\sum\limits_{k=1}^n k^6= \color{blue}{\frac{n(2n+1)(n+1)}{6}} \times \frac{3n^4+6n^3-3n+1}{ 7 }}$$

$$S_7(n):={\sum\limits_{k=1}^n k^7= \color{red}{\frac{\color{red}{n^2(n+1)^2}}{\color{red}{4}} }\times\frac{3n^4+6n^3-n^2-4n+2}{ 6}}$$

$$S_8(n):={\sum\limits_{k=1}^n k^8= \color{blue}{\frac{n(2n+1)(n+1)}{6}} \times \frac{5n^6+15n^5+5n^4-15n^3-n^2+9n+3}{ 15}}$$

$$S_9(n):={\sum\limits_{k=1}^n k^9= \color{red}{\frac{\color{red}{n^2(n+1)^2}}{\color{red}{4}}} \times\frac{(n^2+n-1)(2n^4 +4n^3-n^3-3n^2+3)}{ 5}}$$

$$S_{10}(n):={\sum\limits_{k=1}^n k^{10}= \color{blue}{\frac{n(2n+1)(n+1)}{6}} \times \frac{ 3 n^8+ 12 n^7+ 8 n^6 - 18 n^5- 10 n^4+ 24 n^3 + 2 n^2 - 15 n +5}{ 11}}$$

$$S_{11}(n):={\sum\limits_{k=1}^n k^{11}= \color{red}{\frac{\color{red}{n^2(n+1)^2}}{\color{red}{4}}} \times\frac{2n^8 +8n^7+4n^6-16n^5-5n^4+26n^3-3n^2-20n+10}{ 6}}$$

$$\\[6pt]$$

I noticed that:

For odd $$m>1$$, $$\displaystyle\sum\limits_{k=1}^n k^m= \color{red}{\frac{{n^2(n+1)^2}}{{4}}} \times \frac{P_{m-3}(n)}{N_m}$$ s.t $$P_{m-3}(n)$$ is an $$m-3$$ polynomial with integer coefficients $$\{a_{m-3},\dots a_1,a_0 \}$$ such that $$\gcd \{ a_{m-3},\dots a_1,a_0 \}=1$$, $$N_m\in \mathbb {N}$$.

For even $$m$$, $$\displaystyle\sum\limits_{k=1}^n k^m= \color{blue}{\frac{n(2n+1)(n+1)}{6}}\times \frac{P_{m-2}'(n)}{N_m}$$ s.t $$P_{m-2}'(n)$$ is an $$m-2$$ polynomial with integer coefficients $$\{ a_{m-2},\dots a_1,a_0 \}$$ such that $$\gcd \{ a_{m-2},\dots a_1,a_0 \}=1$$, $$N_m\in \mathbb {N}$$.

When I was in high school I couldn't prove this pattern, and this question reminded me of this observation that I had totally forgotten about. Now, after two years from my first attempt, I tried to prove this pattern again, but I couldn't.

## EDIT

This question has been partly answered in this MathOverflow answer (The answer shows that $$\displaystyle\sum\limits_{k=1}^n k^m$$ is divisible by $${n^2(n+1)^2}$$ for odd $$m>1$$ and $$\displaystyle\sum\limits_{k=1}^n k^m$$ is divisible by $${n(2n+1)(n+1)}$$ for even $$m$$) the only missing part is to show that the denominator is a multiple of $$4$$ if $$m\in 2\mathbb{N}+1$$, and the denominator is a multiple of $$6$$ if $$m \in 2\mathbb{N}$$.

Although this question has been almost solved before, I still would like to see if there is any other proofs or methods.

Update: I asked this question on MO here

• The second observation is discussed here.
– J.G.
Commented Dec 15, 2023 at 8:39
• Search for Faulhaber's formula. Commented Dec 15, 2023 at 8:39
• The pattern also includes the denominators of $\,S_1\,$ and $\,S_2.\,$ below. The pattern continued in a spreadsheet I used with Pascal's triangle and Cramer's rule to $\,S_{31}.$ \begin{align*} S_1=\sum_{x=1}^n x^1 &= \dfrac{n(n+1)}{2}\\ S_2=\sum_{x=1}^n x^2 &=S_1\dfrac{(n+2)}{3}\\ S_3=\sum_{x=1}^n x^3 &= S_1^2\\ S_4=\sum_{x=1}^n x^4 &=S_2\dfrac{(3n^2+3n-1)}{5}\\ S_5=\sum_{x=1}^n x^5 &=S_1^2\dfrac{(2n^2+2n-1)}{3}\\ S_6=\sum_{x=1}^n x^6 &=S_2\dfrac{(3n^4+6n^3-3n+1)}{7}\\ S_7=\sum_{x=1}^n x^7 &=S_1^2\dfrac{(3n^4+6n^3-n^2-4n+2)}{6}\\ \end{align*} Commented Dec 15, 2023 at 20:40
• @pie I'm sorry I do not have proof. I only found that the pattern continues at east thru $\,S_{31}$. Commented Dec 16, 2023 at 3:17
• Re your EDIT: the integer dominators $4$ and $6$ are not missing parts as they do not affect polynomial divisibility. For example, if you have $P(n)=n^2(n+1)^2Q(n)$, you can always give $Q$ an extra factor of $4$ so $P(n)=\frac{n^2(n+1)^2}{4} (4Q(n))$. Commented Dec 19, 2023 at 17:35

Not an answer but an observation. We can rewrite these sums as follows:

$$S_4 = {\sum\limits_{k=1}^n k^4=\frac{n(2n+1)(n+1)}{6}} \times \frac{3n^2+3n-1}{ 5} = \frac{6}{5} \left(\sum\limits_{k=1}^n k^2\right)\left(\sum\limits_{k=1}^n k\right) - \frac{1}{5}\left(\sum\limits_{k=1}^n k^2\right)$$

$$S_5 = \sum\limits_{k=1}^n k^5 = \frac{4}{3} \left(\sum\limits_{k=1}^n k\right)^3 - \frac{1}{3}\left(\sum\limits_{k=1}^n k^3\right)$$

$$S_6 = \sum\limits_{k=1}^n k^6= \frac{n(2n+1)(n+1)}{6} \times \frac{3n^4+6n^3-3n+1}{ 7 } = \frac{12}{7} \left(\sum\limits_{k=1}^n k^2\right)\left(\sum\limits_{k=1}^n k^3\right) - \frac{5}{7}\left(\sum\limits_{k=1}^n k^4\right)$$

$$S_7 = \sum\limits_{k=1}^n k^7= \frac{n^2(n+1)^2}{4} \times\frac{3n^4+6n^3-n^2-4n+2}{ 6} = 2\left(\sum\limits_{k=1}^n k\right)^4 - \left(\sum\limits_{k=1}^n k^5\right)$$

and so on.

• Nice idea. As far as odd indices, generally we have simply $$2^{m-1} S_1^m = \sum_{j>0} \binom{m}{2j-1} S_{2m-2j+1}.$$ For even indices, it appears that $S_{k-1}S_k$ is a (rational) linear combination of $S_{2k},S_{2k-2},...,S_k$ (that is, of $S_{2k},S_{2k-2},...,S_{k+1}$ for $k$ odd). But the coefficients are much less straightforward here. Commented Dec 25, 2023 at 11:02
• For even indices, in fact Bernoulli numbers are involved. Written most economically: $$m(m+1)(S_mS_{m-1}-B_mS_m)=\sum_{j=0}^{\lfloor\frac{m-1}2\rfloor}B_{2j}\binom{m+1}{2j}(2m-2j+1)S_{2m-2j}$$ Note that for odd $m$, the term with $B_m$ on the LHS vanishes. Commented Dec 25, 2023 at 20:10

Two notes, 1) neither of the terms divide the explicit formula, as you are left with a fraction that is not guaranteed to be an integer 2) when $$i=4$$, it should be $$\sum_{k=0}^n k^i = \frac{n(n+1)(2n+1)(3n^2+3n-1)}{6\cdot 5}$$ As $$+1$$ gives you a little bit over. Now, you want a pattern to appear, meaning you want to solve for $$a_i$$ ( I am only going to do when i is even) if $$\sum_{k=0}^n k^{2i} = a_i \sum_{k=0}^n k^2 \\ \frac{\sum_{k=0}^n k^{2i}}{ \sum_{k=0}^n k^2} = a_i \\$$ Thus, for our arbitary $$a_i$$, we can now calculate our sum. Using Faulhaber's formula: $$\sum_{k=0}^n k^i = \frac{1}{i+1} \sum_{k=0}^i {i + 1 \choose k} B_k n^{i+1-k}$$bernoulli number. Then, our final equation can become:

$$a_i = \frac{3}{2i+1}\frac{ \sum_{k=0}^i {i + 1 \choose k} B_k n^{i+1-k}}{ \sum_{k=0}^2 {3 \choose k} B_k n^{3-k}}$$

This may be something, it may not. The way you achieved these explicity formulas is likely very important, as you could be arbitrarily introducing the $$i=2$$ term and thus $$a_i$$ is some pseudo-random number. At the same time, it may something very interesting. Either way, if you wanted to find a non-arbitrary pattern between these, you would want to find the value of $$a_i$$ in explicit terms, however as $$a_i$$ is non-linear by a long-shot, this is likely impossible. Hence, the reason the $$i=2$$ term shows up constantly is probably just how you've defined it. But, if you are still hopeful there is a chance! Good luck.

Also the first terms (simplified in terms of the $$i=1$$ term) are: \begin{align} a_0 &= 1 \\ a_1 &= \frac{6 \sum_{k=0}^n k-1}{5} \\ a_2 &= \frac{(6 \sum_{k=0}^n k)(n^2+n-1) - 1}{7} \end{align} Which is intriguing especially since $$x^2 + x -1$$ is the polynomial used to derive Binet's formula for the exact value of any fibonacci number.

The first part of the question was answered here (The answer shows that $$\displaystyle\sum\limits_{k=1}^n k^m$$ is divisible by $${n^2(n+1)^2}$$ for odd $$m>1$$ and $$\displaystyle\sum\limits_{k=1}^n k^m$$ is divisible by $${n(2n+1)(n+1)}$$ for even $$m$$)

Thanks to Sam Hopkins and Sil for recommending this paper.

$$S_m(n)=\frac{P_{m+1}}{d_m}$$, where $$P_{m+1}(n)$$ is an $$m+1$$ polynomial with integer coefficients $$\{ a_{m+1},\dots a_1,a_0 \}$$ such that $$\gcd \{ a_{m+1},\dots a_1,a_0 \}=1$$.

Theorem $$1$$ The paper proved that $$(m+1)\bigg|d_m$$, let $$q_m :=\frac{d_m}{m+1}$$ st $$q_m$$ is an integer.

$$M_m := \begin{cases} \frac{m+2}{2}, & \text{if m is even} \\[2ex] \frac{m+2}{3}, & \text{if m is odd} \end{cases}$$

Theorem $$3$$ Proves that $$q_m = \prod\limits_{p\le M_m}p^{\varepsilon_p}$$ for prime number $$p$$,

$$\varepsilon_2 := \begin{cases} 0, & \text{if m=2^r-1 for some r,} \\[2ex] 1, & \text{otherwise,} \end{cases}$$

$$\varepsilon_p := \begin{cases} 0, & \text{if \displaystyle p \not \bigg| (m+2) and \displaystyle p \bigg| \dbinom{m+1}{(p-1)j} for all j =2,3,\dots , \lfloor\frac{m}{p-1} \rfloor-1,} \\[2ex] 1, & \text{otherwise,} \end{cases}$$

## For odd $$m>1$$:

If $$m$$ can be expressed as $$2^r-1$$ for some $$r\in \mathbb{N}$$, since $$m>1$$ the $$r\ge 2$$ so $$d_m = (2^r) q_n$$, So $$\color{red}{4}\bigg|d_m$$.

If $$m$$ can't be expressed as $$2^r-1$$ for any $$r \in \mathbb{N}$$, then $$\varepsilon_2=1$$ and since $$m$$ is odd number $$m+1$$ is even, so $$\color{red}{4}\bigg| d_m$$.

Which implies that for all odd $$m>1$$ the denominator $$d_m$$ is always divisble by $$\color{red}4$$.

## For even $$m$$:

It is clear that $$\varepsilon_2=1$$.

Any positive integer $$m$$ can be expressed as $$3a$$ or $$3a+1$$ , or $$3a+2$$ for some non negative integer $$a$$.

If $$m$$ can be expressed as $$3a+1$$ for some non negative integer $$a$$ It follows that $$\varepsilon_3=1$$ which implies that he denominator $$d_m$$ is divisble by $$\color{blue}6$$.

If $$m$$ can be expressed as $$3a+2$$ for some non negative integer $$a$$ It follows that $$3|M+1$$ (There is no need to evaluate $$\varepsilon_3$$) which implies that he denominator $$d_m$$ is divisble by $$\color{blue}6$$.

If $$m$$ can be expressed as $$6a$$ for some non negative integer $$a$$, we need to prove that $$\varepsilon_3=1$$ it is sufficient to find a $$l \in \{2,4,6,\dots 6a-2 \}$$ such that $$3\not |\dbinom{6a+1}{l}$$. Since $$6a+1$$ is odd then we can choose $$l$$ form $$\{2,3,4,5,\dots,6a-2 \}$$. Choose the largest $$b\in\mathbb{N}$$ such that $$3^b|6a$$,let $$l= 3^b$$. It is clear that $$3\not\bigg|\dbinom{6a+1}{3^b}$$.

Which implies that he denominator $$d_m$$ is divisble by $$\color{blue}6$$ for all even $$m$$.

## Remark

For odd $$p$$:

$$\varepsilon_p=0$$ only when $$m+1$$ is a power of $$p$$ see this for proof.