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)=\dfrac{n(n+1)}{2}\).
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\).
With \(S\) as in part (a), show that there are \(\dbinom{n+1}{2}+2\dbinom{n+1}{3}\) elements in \(S\) and use this to show that \[p_2(n)=\dfrac{n(n+1)(2n+1)}{6}\]
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\binom{n+1}{2}+a_3\binom{n+1}{3}+\cdots+a_k\binom{n+1}{k}+a_{k+1}\binom{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.
Use part (c) to show that \(p_3(n) = \dfrac{n^2(n+1)^2}{4}\) and \(p_4(n) = \dfrac{n(n+1)(2n+1)(3n^2+3n-1)}{30}\).
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_1n+c_2n^2+c_3n^3+c_4n^4+c_5n^5+c_6n^6\] Use the fact that \(p_5(1) = 1\) and \(p_5(n)-p_5(n-1)=n^5\) for all \(n\geq 2\) to determine \(c_0\) through \(c_6\), and hence, derive a formula for \(p_5(n)\).
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\).