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

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.