Problem of the Month
Problem 4: January 2023

For each positive integer $k$, define a function $p_k(n)=1^k+2^k+3^k+\cdots +n^k$ for each integer $n$. That is, $p_k(n)$ is the sum of the first $n$ perfect $k$^th powers. It is well known that $p_1(n)={\displaystyle \frac{n(n+1)}{2}}$.

1. Fix a positive integer $n$. Let $S$ be the set of ordered triples $(a,b,c)$ of integers between $1$ and $n+1$, inclusive, that also satisfy $a<c$ and $b<c$. Show that there are exactly $p_2(n)$ elements in the set $S$.

2. With $S$ as in part (a), show that there are ${\displaystyle (\genfrac{}{}{0ex}{}{n+1}{2})}+2{\displaystyle (\genfrac{}{}{0ex}{}{n+1}{3})}$ elements in $S$ and use this to show that $$p_2(n)={\displaystyle \frac{n(n+1)(2n+1)}{6}}$$

3. For each $k$, show that there are constants $a_2,a_3,\dots ,a_k,a_{k+1}$ such that $$p_k(n)=a_2(\genfrac{}{}{0ex}{}{n+1}{2})+a_3(\genfrac{}{}{0ex}{}{n+1}{3})+\cdots +a_k(\genfrac{}{}{0ex}{}{n+1}{k})+a_{k+1}(\genfrac{}{}{0ex}{}{n+1}{k+1})$$ for all $n$.

   Note: Actually computing the constants gets more and more difficult as $k$ gets larger. While you might want to compute them for some small $k$, in this problem we only intend that you argue that the constants always exist, not that you deduce exactly what they are.

4. Use part (c) to show that $p_3(n)={\displaystyle \frac{n^2(n+1{)}^2}{4}}$ and $p_4(n)={\displaystyle \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}}$.

5. It follows from the fact in part (c) that $p_k(n)$ is a polynomial of degree $k+1$. With $k=5$, this means there are constants $c_0,c_1,c_2,c_3,c_4,c_5,$ and $c_6$ such that $$p_5(n)=c_0+c_{1}n+c_2{n}^2+c_3{n}^3+c_4{n}^4+c_5{n}^5+c_6{n}^6$$ Use the fact that $p_5(1)=1$ and $p_5(n)-p_5(n-1)=n^5$ for all $n\ge 2$ to determine $c_0$ through $c_6$, and hence, derive a formula for $p_5(n)$.

6. Show that $n(n+1)$ is a factor of $p_k(n)$ for every positive integer $k$ and that $2n+1$ is a factor of $p_k(n)$ for every even positive integer $k$.