Since \(a\) and \(b\) are positive integers and \(c\) is larger than both of them, the smallest value that \(c\) can take is \(c=2\). The possible values of \(c\) are therefore \(c=2\), \(c=3\), and so on up to \(c=n+1\).
The only triple in \(S\) with the property that \(c=2\) is \((1,1,2)\), so there is one triple with \(c=2\). The triples in \(S\) with \(c=3\) are \((1,1,3)\), \((1,2,3)\), \((2,1,3)\), and \((2,2,3)\), so there are four triples with \(c=3.\)
In general, if \(c=r\), then \(a\) and \(b\) can both be any integer from \(1\) through \(r-1\) inclusive. Thus, there are \((r-1)\times(r-1)=(r-1)^2\) triples in \(S\) with \(c=r\). Since \(r\) ranges from \(2\) through \(n+1\), there are exactly \[1^2+2^2+3^2+4^2+\cdots+(n-1)^2+n^2=p_2(n)\] triples in \(S\).
We will now count the triples in \(S\) by considering them according to the number of distinct integers that occur in the triple. For example, there are two distinct integers in \((1,1,2)\) and three distinct integers in \((1,5,7)\).
If \((a,b,c)\) is in \(S\), then there are at most three distinct integers in the triple (since there are only three integers in total). As well, since \(a<c\), the integers cannot all be equal. Therefore, there are either two distinct integers or three distinct integers in \((a,b,c)\).
Suppose \(x\), \(y\), and \(z\) are three distinct integers between \(1\) and \(n+1\) inclusive. Since they are distinct, one of them is the largest. Assuming \(z\) is the largest, the triples \((x,y,z)\) and \((y,x,z)\) are both in \(S\), and these are the only triples in \(S\) that contain the integers \(x\), \(y\), and \(z\). Therefore, for every way to choose three distinct integers between \(1\) and \(n+1\) inclusive, there are two triples in \(S\). This observation means there are \(2\dbinom{n+1}{3}\) triples in \(S\) with three distinct integers in them.
Now suppose that \(x\) and \(y\) are two distinct integers with \(x<y\). Then the only triple in \(S\) that contains exactly the integers \(x\) and \(y\) is \((x,x,y)\). Thus, for every two distinct integers between \(1\) and \(n+1\) inclusive, there is exactly one triple in \(S\) that contains exactly those two integers. Therefore, there are \(\dbinom{n+1}{2}\) triples in \(S\) with two distinct integers in them.
Therefore, the number of elements in \(S\) is \(\dbinom{n+1}{2}+2\dbinom{n+1}{3}\).
From part (a), \[\begin{align*} p_2(n) &= \binom{n+1}{2}+2\binom{n+1}{3} \\ &= \dfrac{(n+1)!}{2!(n-1)!}+2\dfrac{(n+1)!}{3!(n-2)!} \\ &= \frac{(n+1)n}{2}+\frac{2(n+1)n(n-1)}{6} \\ &= n(n+1)\left(\frac{1}{2}+\frac{n-1}{3}\right) \\ &= n(n+1)\left(\frac{3}{6}+\frac{2(n-1)}{6}\right) \\ &= \frac{n(n+1)(3+2n-2)}{6} \\ &= \frac{n(n+1)(2n+1)}{6}\end{align*}\]
Fix a positive integer \(n\). Using the idea from parts (a) and (b), we let \(S_k\) be the set of ordered lists of \(k+1\) positive integers \((x_1,x_2,x_3,\dots,x_k,x_{k+1})\) with the property that each integer \(x_i\) is between \(1\) and \(n+1\) inclusive and \(x_{k+1}\) is larger than every other integer in the list. A list of the form \((x_1,x_2,x_3,\dots,x_k,x_{k+1})\) is called a \((k+1)\)-tuple.
As in the case with \(k=2\), it is not possible for a \((k+1)\)-tuple in \(S_k\) to have \(x_{k+1}=1\). This is because the other integers are positive and \(x_{k+1}\) must be the largest integer in the list (it cannot be "tied" for the largest). The possible values of \(x_{k+1}\) are \(2\) through \(n+1\).
For a fixed value of \(x_{k+1}\), say \(x_{k+1}=r\), if \((x_1,x_2,x_3,\dots,x_k,x_{k+1})\) is in \(S_k\), then \(x_1\) through \(x_k\) can each be any positive integer less than \(r\), of which there are \(r-1\). Therefore, the number of \((k+1)\)-tuples in \(S_k\) with \(x_{k+1}=r\) is \((r-1)^2\). The possible values of \(r\) are \(2\) through \(n+1\), so we have that the number of elements in \(S_k\) is \[1^k+2^k+3^k+\cdots+(n-1)^k+n^k=p_k(n)\]
Following the reasoning of part (b), we now want to count the elements in \(S_k\) a different way. Since \(x_{k+1}\) is the largest integer in the \((k+1)\)-tuple, there are at least two distinct integers in every \((k+1)\)-tuple in \(S_k\). As well, there are at most \(k+1\) distinct integers in every \((k+1)\)-tuple. Suppose we have chosen \(r\) distinct positive integers between \(1\) and \(n+1\) inclusive with \(2\leq r\leq k+1\). We would like to count the \((k+1)\)-tuples in \(S_k\) that contain exactly those \(r\) integers. For example, suppose \(k=4\) and \(r=3\). We need to count the number of \(5\)-tuples that use exactly three given integers with the largest integer occurring only in the rightmost position. Suppose the largest integer is \(C\) and the other two are \(A\) and \(B\). The \(5\)-tuples in \(S_k\) are
\((A,A,A,B,C)\), \((A,A,B,A,C)\), \((A,B,A,A,C)\), \((B,A,A,A,C)\), \((B,B,B,A,C)\), \((B,B,A,B,C)\), \((B,A,B,B,C)\), \((A,B,B,B,C)\), \((A,A,B,B,C)\), \((A,B,A,B,C)\), \((A,B,B,A,C)\), \((B,A,A,B,C)\), \((B,A,B,A,C)\), \((B,B,A,A,C)\)
and so there are \(14\) \(5\)-tuples in \(S_k\) with exactly those three integers. This means that there are \(14\dbinom{n+1}{3}\) \(5\)-tuples in \(S_k\) that have exactly three distinct integers in them. The important thing to notice here is that the constant \(14\) does not depend on \(n\). We could do a similar count to see how many \(9\)-tuples there are in \(S_8\) with exactly five distinct integers. The combinatorics might be a bit tedious, but in the end, we would find that the number of \(9\)-tuples in \(S_8\) with exactly five distinct integers is some multiple of \(\dbinom{n+1}{5}\) where the multiplier does not depend on \(n\).
Putting this together, there must be some constants \(a_2,\dots,a_{k+1}\) so 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}\] where each coefficient \(a_r\) is equal to the number of \((k+1)\)-tuples in \(S_k\) that contain exactly a fixed set of \(r\) distinct integers.
Put differently, suppose \(R\) is a set of \(r\) distinct positive integers. Then \(a_r\) is the number of \((k+1)\)-tuples that satisfy the following three conditions: every integer in the \((k+1)\)-tuple comes from \(R\), every integer in \(R\) occurs at least once in the \((k+1)\)-tuple, and the largest integer in \(R\) occurs exactly once and is in the rightmost position.
Before moving on, we make one final observation. With the convention that \(\dbinom{u}{v}=0\) when \(u<v\), the equation above makes sense even when \(n+1\) is smaller than the bottom number in the binomial coefficient. For example, if \(k=5\) and \(n=2\), then the term \(a_4\dbinom{n+1}{4}=a_4\dbinom{3}{4}\) is counting the number of \(6\)-tuples consisting of four distinct integers between \(1\) and \(n+1=3\) inclusive. There is no way to choose four distinct integers from the list \(1\), \(2\), \(3\), so there should be zero such \(6\)-tuples, and the fact that \(\dbinom{3}{4}=0\) records this observation.
From part (c), we have that \[p_3(n) = a_2\binom{n+1}{2}+a_3\binom{n+1}{3}+a_4\binom{n+1}{4}\] for some constants \(a_2\), \(a_3\), and \(a_4\). Using that \(p_3(1)=1^3=1\), we have that \[\begin{align*} 1 &= p_3(1) \\ &= a_2\binom{1+1}{2}+a_3\binom{1+1}{3}+a_4\binom{1+1}{4} \\ &= a_2\binom{2}{2} +a_3\binom{2}{3}+a_4\binom{2}{4} \\ &= a_2+0+0\end{align*}\] and so \(a_2=1\). With \(n=2\), we have \(p_3(2)=1^3+2^3=9\), so \[\begin{align*} 9 &= p_2(2) \\ &= \binom{2+1}{2}+a_3\binom{2+1}{3}+a_4\binom{2+1}{4} \\ &= \binom{3}{2}+a_3\binom{3}{3}+a_4\binom{3}{4} \\ &= 3+a_3+0\end{align*}\] and so \(a_3=6\). Finally, using \(n=3\), we have \(p_3(3)=1^3+2^3+3^3=36\), so \[\begin{align*} 36 &= p_3(3) \\ &= \binom{4}{2}+6\binom{4}{3}+a_4\binom{4}{4} \\ &= 6+6\times 4+a_4\end{align*}\] from which it follows that \(a_4=6\). Recall that \(a_4\) is equal to the number of four-tuples in \(S_3\) consisting of a fixed set of four distinct integers. Indeed, the largest integer must go in the rightmost position, and there are \(6\) ways to arrange the other three integers, so \(a_4=6\) makes sense from a combinatorial perspective.
We now have shown that \[\begin{align*} p_3(n) &= \binom{n+1}{2}+6\binom{n+1}{3}+6\binom{n+1}{4} \\ &= \dfrac{(n+1)n}{2}+\dfrac{6(n+1)n(n-1)}{6}+\frac{6(n+1)n(n-1)(n-2)}{24}\end{align*}\] and after some simplification, we get that \[p_3(n)=\dfrac{n^2(n+1)^2}{4}\]
We can approach \(p_4(n)\) similar to how \(p_3(n)\) was approached above. We start with \[p_4(n)=a_2\binom{n+1}{2}+a_3\binom{n+1}{3}+a_4\binom{n+1}{4}+a_5\binom{n+1}{5}\] and then use that \(p_4(1)=1\), \(p_4(2)=1^4+2^4=17\), \(p_4(3) = 1^4+2^4+3^4=98\), and \(p_4(4)=1^4+2^4+3^4+4^4=354\) to solve for \(a_2\), \(a_3\), \(a_4\), and \(a_5\). After doing this, we find that \(a_2=1\), \(a_3=14\), \(a_4=36\), and \(a_5=24\). Therefore, after some simplification, we get
\[\begin{align*} p_4(n) &= \binom{n+1}{2}+14\binom{n+1}{3}+36\binom{n+1}{4}+24\binom{n+1}{5} \\ &= \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}\end{align*}\]
Using that \(p_5(n) = c_0+c_1n+c_2n^2+c_3n^3+c_4n^4+c_5n^5+c_6n^6\), we can find a general expression for \(p_5(n)-p_5(n-1)\). \[\begin{align*} n^5 &= p_5(n)-p_5(n-1) \\ &= c_0+c_1n+c_2n^2+c_3n^3+c_4n^4+c_5n^5+c_6n^6 \\ & \hspace{5mm}-\left(c_0+c_1(n-1)+c_2(n-1)^2+c_3(n-1)^3+c_4(n-1)^4+c_5(n-1)^5+c_6(n-1)^6\right) \\ &= c_0+c_1n+c_2n^2+c_3n^3+c_4n^4+c_5n^5+c_6n^6 \\ & \hspace{5mm}-c_0 - c_1(n-1) - c_2(n^2-2n+1) - c_3(n^3-3n^2+3n-1) \\ & \hspace{5mm}-c_4(n^4-4n^3+6n^2-4n+1) - c_5(n^5-5n^4+10n^3-10n^2+5n-1) \\ & \hspace{5mm}-c_6(n^6-6n^5+15n^4-20n^3+15n^2-6n+1)\end{align*}\] and after collecting like terms, we get \[\begin{align*} n^5 &= (c_1-c_2+c_3-c_4+c_5-c_6) + (2c_2-3c_3+4c_4-5c_5+6c_6)n \\ & \hspace{5mm} +(3c_3-6c_4+10c_5-15c_6)n^2 + (4c_4-10c_5+20c_6)n^3 \\ & \hspace{5mm} +(5c_5-15c_6)n^4 + 6c_6n^5 \\\end{align*}\] We can now equate coefficients to get the system of equations \[\begin{align*} 6c_6 &= 1 \\ 5c_5-15c_6 &= 0 \\ 4c_4-10c_5+20c_6 &= 0 \\ 3c_3-6c_4+10c_5-15c_6 &= 0 \\ 2c_2-3c_3+4c_4-\hspace{3mm}5c_5+\hspace{3mm}6c_6 &= 0 \\ c_1-\hspace{3mm}c_2+\hspace{3mm}c_3-\hspace{3mm}c_4+\hspace{7mm}c_5-\hspace{6mm}c_6 &= 0\end{align*}\] From the first equation, we get \(c_6=\dfrac{1}{6}\). Substituting this into the second equation gives \(5c_5-15\times\dfrac{1}{6}=0\) so \(c_5=\dfrac{1}{2}\). Continuing this way, we get that \(c_4=\dfrac{5}{12}\), \(c_3=0\), \(c_2=-\dfrac{1}{12}\), and \(c_1=0\). Therefore \[p_5(n) = c_0-\dfrac{1}{12}n^2+\dfrac{5}{12}n^4+\dfrac{1}{2}n^5+\dfrac{1}{6}n^6\] To solve for \(c_0\), we can use that \(p_5(1)=1\) to get the equation \[1 = c_0-\dfrac{1}{12}+\dfrac{5}{12}+\dfrac{1}{2}+\dfrac{1}{6}=c_0+1\] which means \(c_0=0\). Finally, we can rearrange \(p_5(n)\) into a nicer form \[\begin{align*} p_5(n) &= -\dfrac{1}{12}n^2+\dfrac{5}{12}n^4+\dfrac{1}{2}n^5+\dfrac{1}{6}n^6 \\ &= \frac{-n^2+5n^4+6n^5+2n^6}{12} \\ &= \frac{n^2(n+1)^2(2n^2+2n-1)}{12}\end{align*}\]
Fix a positive integer \(k\) and consider the function \(p_k(n)\). We observed earlier that \(p_k(n)\) is a polynomial in \(n\). While \(p_k(n)\) is designed to output \(1^k+2^k+\cdots+n^k\) when \(n\) is a positive integer, there is nothing to stop us from "symbolically" evaluating \(p_k(n)\) when \(n\) is not an integer. For example, even though \(p_1\left(\dfrac{1}{4}\right)\) does not have the same meaning as \(p_1(n)\) when \(n\) is a positive integer (we cannot "add together the first \(\dfrac{1}{4}\) positive integers"), we can still substitute \(\dfrac{1}{4}\) into the formula for \(p_1\) to get \(p_1\left(\dfrac{1}{4}\right)=\dfrac{\frac{1}{4}\times\frac{5}{4}}{2}=\dfrac{5}{32}\).
Now consider the function \(f_k(n) = p_k(n)-p_k(n-1)-n^k\) where \(n\) is allowed to be any real number. The function \(f_k(n)\) is the sum/difference of three polynomials, so it is itself a polynomial. Since \(p_k(n)-p_k(n-1)=n^k\) for all positive integers \(n\), \(n\) is a root of \(f_k(n)\) for all positive integers \(n\). By the fact in the hint, a polynomial with infinitely many roots must be the constant zero function, so \(p_k(n)-p_k(n-1)-n^k=0\) for all real numbers \(n\).
With \(n=1\), we get that \(p_k(1)-p_k(0)=1^k=1\), but since \(p_k(1)=1\), we have that \(1-p_k(0)=1\), so \(p_k(0)=0\). Similarly, by considering \(n=0\), we get that \(p_k(0)-p_k(-1)=0^k\), and since \(p_k(0)=0\), we have \(0-p_k(-1)=0\), so \(p_k(-1)=0\) as well. We have shown that \(0\) and \(-1\) are roots of the polynomial \(p_k(n)\), which shows that \(n\) and \(n+1\) are factors of \(p_k(n)\). This means \(n(n+1)\) is a factor of \(p_k(n)\).
We now suppose that \(k\) is even, which means \(n^k=(-n)^k\) for all real numbers \(n\). From above, we have that \(p_k(0)=p_k(-1)=0\). Considering \(p_k(n)-p_k(n-1)=n^k\) at \(n=-1\), we have that \(p_k(-1)-p_k(-2)=(-1)^k\), and since \(k\) is even and \(p_k(-1)=0\), we have \(-p_k(-2)=1^k\) or \(p_k(-2)=-1^k\).
Next, we use \(p_k(n)-p_k(n-1)=n^k\) with \(n=-2\) to get \(p_k(-2)-p_k(-3)=(-2)^k=2^k\), and since \(p_k(-2)=-1^k\), this means \(-p_k(-3)=1^k+2^k\) or \(p_k(-3)=-(1^k+2^k)\).
Continuing this way, we have \(p_k(-3)-p_k(-4)=(-3)^k=3^k\), so \(-1^k-2^k-p_k(-4)=3^k\), and so \(p_k(-4)=-(1^k+2^k+3^k)\). We have now shown that \(p_k(-n)=-p_k(n-1)\) for the positive integers \(n=0\), \(n=1\), \(n=2\), \(n=3\), and \(n=4\). This pattern continues. It can be proven using mathematical induction that \(p_k(-n)=-p_k(n-1)\) for all positive integers \(n\).
This means that \(p_k(-n)+p_k(n-1)=0\) for every non-negative integer. Therefore, the polynomial \(p_k(-n)+p_k(n-1)\) has infinitely many roots, and so must be equal to \(0\) for every real number \(n\).
Taking \(n=\dfrac{1}{2}\), we get \(p_k\left(-\dfrac{1}{2}\right)+p_k\left(\dfrac{1}{2}-1\right)=0\) which simplifies to \(2p_k\left(-\dfrac{1}{2}\right)=0\). Therefore, \(-\dfrac{1}{2}\) is a root of \(p_k(n)\) when \(k\) is even. Thus, \(p_k(n)\) has a factor of \(n+\dfrac{1}{2}\), which is equivalent to having a factor of \(2n+1=2\left(n+\dfrac{1}{2}\right)\).