POTM January 2023 Solution

Problem of the Month
Solution to Problem 4: January 2023

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} + \dots + (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 (\binom{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 $(\binom{n + 1}{2})$ triples in $S$ with two distinct integers in them.

Therefore, the number of elements in $S$ is $(\binom{n + 1}{2}) + 2 (\binom{n + 1}{3})$ .

From part (a), $\begin{aligned} p_{2} (n) & = (\binom{n + 1}{2}) + 2 (\binom{n + 1}{3}) \\ = \frac{(n + 1)!}{2! (n - 1)!} + 2 \frac{(n + 1)!}{3! (n - 2)!} \\ = \frac{(n + 1) n}{2} + \frac{2 (n + 1) n (n - 1)}{6} \\ = n (n + 1) (\frac{1}{2} + \frac{n - 1}{3}) \\ = n (n + 1) (\frac{3}{6} + \frac{2 (n - 1)}{6}) \\ = \frac{n (n + 1) (3 + 2 n - 2)}{6} \\ = \frac{n (n + 1) (2 n + 1)}{6} \end{aligned}$

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} + \dots + (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 (\binom{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 $(\binom{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}) + \dots + 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 $(\binom{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} (\binom{n + 1}{4}) = a_{4} (\binom{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 $(\binom{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{aligned} 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{aligned}$ and so $a_{2} = 1$ . With $n = 2$ , we have $p_{3} (2) = 1^{3} + 2^{3} = 9$ , so $\begin{aligned} 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{aligned}$ and so $a_{3} = 6$ . Finally, using $n = 3$ , we have $p_{3} (3) = 1^{3} + 2^{3} + 3^{3} = 36$ , so $\begin{aligned} 36 & = p_{3} (3) \\ = (\binom{4}{2}) + 6 (\binom{4}{3}) + a_{4} (\binom{4}{4}) \\ = 6 + 6 \times 4 + a_{4} \end{aligned}$ 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{aligned} p_{3} (n) & = (\binom{n + 1}{2}) + 6 (\binom{n + 1}{3}) + 6 (\binom{n + 1}{4}) \\ = \frac{(n + 1) n}{2} + \frac{6 (n + 1) n (n - 1)}{6} + \frac{6 (n + 1) n (n - 1) (n - 2)}{24} \end{aligned}$ and after some simplification, we get that $p_{3} (n) = \frac{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{aligned} 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) (2 n + 1) (3 n^{2} + 3 n - 1)}{30} \end{aligned}$

Using 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}$ , we can find a general expression for $p_{5} (n) - p_{5} (n - 1)$ . $\begin{aligned} n^{5} & = p_{5} (n) - p_{5} (n - 1) \\ = 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} \\ - (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}) \\ = 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} \\ - c_{0} - c_{1} (n - 1) - c_{2} (n^{2} - 2 n + 1) - c_{3} (n^{3} - 3 n^{2} + 3 n - 1) \\ - c_{4} (n^{4} - 4 n^{3} + 6 n^{2} - 4 n + 1) - c_{5} (n^{5} - 5 n^{4} + 10 n^{3} - 10 n^{2} + 5 n - 1) \\ - c_{6} (n^{6} - 6 n^{5} + 15 n^{4} - 20 n^{3} + 15 n^{2} - 6 n + 1) \end{aligned}$ and after collecting like terms, we get $\begin{aligned} n^{5} & = (c_{1} - c_{2} + c_{3} - c_{4} + c_{5} - c_{6}) + (2 c_{2} - 3 c_{3} + 4 c_{4} - 5 c_{5} + 6 c_{6}) n \\ + (3 c_{3} - 6 c_{4} + 10 c_{5} - 15 c_{6}) n^{2} + (4 c_{4} - 10 c_{5} + 20 c_{6}) n^{3} \\ + (5 c_{5} - 15 c_{6}) n^{4} + 6 c_{6} n^{5} \end{aligned}$ We can now equate coefficients to get the system of equations $\begin{aligned} 6 c_{6} & = 1 \\ 5 c_{5} - 15 c_{6} & = 0 \\ 4 c_{4} - 10 c_{5} + 20 c_{6} & = 0 \\ 3 c_{3} - 6 c_{4} + 10 c_{5} - 15 c_{6} & = 0 \\ 2 c_{2} - 3 c_{3} + 4 c_{4} - 5 c_{5} + 6 c_{6} & = 0 \\ c_{1} - c_{2} + c_{3} - c_{4} + c_{5} - c_{6} & = 0 \end{aligned}$ From the first equation, we get $c_{6} = \frac{1}{6}$ . Substituting this into the second equation gives $5 c_{5} - 15 \times \frac{1}{6} = 0$ so $c_{5} = \frac{1}{2}$ . Continuing this way, we get that $c_{4} = \frac{5}{12}$ , $c_{3} = 0$ , $c_{2} = - \frac{1}{12}$ , and $c_{1} = 0$ . Therefore $p_{5} (n) = c_{0} - \frac{1}{12} n^{2} + \frac{5}{12} n^{4} + \frac{1}{2} n^{5} + \frac{1}{6} n^{6}$ To solve for $c_{0}$ , we can use that $p_{5} (1) = 1$ to get the equation $1 = c_{0} - \frac{1}{12} + \frac{5}{12} + \frac{1}{2} + \frac{1}{6} = c_{0} + 1$ which means $c_{0} = 0$ . Finally, we can rearrange $p_{5} (n)$ into a nicer form $\begin{aligned} p_{5} (n) & = - \frac{1}{12} n^{2} + \frac{5}{12} n^{4} + \frac{1}{2} n^{5} + \frac{1}{6} n^{6} \\ = \frac{- n^{2} + 5 n^{4} + 6 n^{5} + 2 n^{6}}{12} \\ = \frac{n^{2} (n + 1)^{2} (2 n^{2} + 2 n - 1)}{12} \end{aligned}$

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} + \dots + 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} (\frac{1}{4})$ does not have the same meaning as $p_{1} (n)$ when $n$ is a positive integer (we cannot "add together the first $\frac{1}{4}$ positive integers"), we can still substitute $\frac{1}{4}$ into the formula for $p_{1}$ to get $p_{1} (\frac{1}{4}) = \frac{\frac{1}{4} \times \frac{5}{4}}{2} = \frac{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 = \frac{1}{2}$ , we get $p_{k} (- \frac{1}{2}) + p_{k} (\frac{1}{2} - 1) = 0$ which simplifies to $2 p_{k} (- \frac{1}{2}) = 0$ . Therefore, $- \frac{1}{2}$ is a root of $p_{k} (n)$ when $k$ is even. Thus, $p_{k} (n)$ has a factor of $n + \frac{1}{2}$ , which is equivalent to having a factor of $2 n + 1 = 2 (n + \frac{1}{2})$ .

Problem of the Month Solution to Problem 4: January 2023

Problem of the Month
Solution to Problem 4: January 2023