2025 USAMO Problems/Problem 5

Problem

Determine, with proof, all positive integers $k$ such that $\frac{1}{n+1} \sum_{i=0}^n \binom{n}{i}^k$ is an integer for every positive integer $n.$

Solution 1

https://artofproblemsolving.com/wiki/index.php/File:2025_USAMO_PROBLEM_5_1.jpg

https://artofproblemsolving.com/wiki/index.php/File:2025_USAMO_PROBLEM_5_2.jpg

Solution 2 (q-analog roots of unity)

Throughout this proof we work in the polynomial ring $\mathbb Z[q]$ .

For any positive integer $n$ , define the $q$ -integer and $q$ -factorial by $[n]_q := 1 + q + q^2 + \cdots + q^{n-1}, \qquad [n]_q! := \prod_{i=1}^n [i]_q.$ Each $[i]_q$ is a degree $i-1$ polynomial in $\mathbb Z[q]$ , so $[n]_q! \in \mathbb Z[q]$ . Evaluating at $q = 1$ gives $\lim_{q \to 1} [n]_q! = n!$ .

Define the $q$ -binomial coefficient as $\left[ \begin{array}{c} n \\ i \end{array} \right]_q := \frac{[n]_q!}{[i]_q! [n-i]_q!} \in \mathbb Z[q],$ which recovers the usual binomial coefficient when $q = 1$ .

Let $A_k(n) = \dfrac{1}{n+1} \sum_{i=0}^n \binom{n}{i}^k$ . We want to prove that $A_k(n) \in \mathbb Z$ for all $n \ge 1$ if and only if $k$ is even.

Define the $q$ -analogue sum $S_k(n;q) := \sum_{i=0}^n \left[ \begin{array}{c} n \\ i \end{array} \right]_q^k \in \mathbb Z[q].$ Let $[n+1]_q = 1 + q + \cdots + q^n = \dfrac{1 - q^{n+1}}{1 - q} = \prod_{d \mid n+1} \Phi_d(q)$ , where $\Phi_d(q)$ is the $d$ -th cyclotomic polynomial.

To prove $A_k(n) \in \mathbb Z$ , it suffices to show $[n+1]_q \mid S_k(n;q) \quad \text{in } \mathbb Z[q],$ because evaluating at $q = 1$ yields $\dfrac{1}{n+1} \sum_{i=0}^n \binom{n}{i}^k \in \mathbb Z$ .

Suppose $q = \zeta$ is a primitive $d$ -th root of unity with $d \mid n+1$ , so $[n+1]_q = 0$ . We evaluate $S_k(n; q)$ at $q = \zeta$ : $T_k(n; \zeta) := S_k(n; \zeta) = \sum_{i=0}^n \left[ \begin{array}{c} n \\ i \end{array} \right]_\zeta^k.$

We now determine when $T_k(n; \zeta) = 0$ . Suppose $n = d - 1$ , the largest index where $\zeta^d = 1$ . It is known that $\left[ \begin{array}{c} d - 1 \\ i \end{array} \right]_{\zeta} = (-1)^i \zeta^{-i(i+1)/2}.$ Therefore, $T_k(d - 1; \zeta) = \sum_{i = 0}^{d - 1} (-1)^{ik} \zeta^{-k i(i+1)/2}.$

If $k$ is odd, then $(-1)^{ik} = (-1)^i$ , and the sum does not cancel. So $T_k(d - 1; \zeta) \ne 0$ , implying $\Phi_d(q) \nmid S_k(d - 1; q)$ , so $[d]_q \nmid S_k(d - 1; q)$ and $A_k(d - 1) \notin \mathbb Z$ .

If $k$ is even, then $(-1)^{ik} = 1$ for all $i$ , so $T_k(d - 1; \zeta) = \sum_{i = 0}^{d - 1} \zeta^{-k i(i+1)/2},$ which is a quadratic exponential sum over a full residue system modulo $d$ . It is known that such sums vanish when $k$ is even and $d$ is odd. Hence $T_k(d - 1; \zeta) = 0$ , so $\Phi_d(q) \mid S_k(n; q)$ .

Since this holds for all $d \mid n+1$ , the full factor $[n+1]_q = \prod_{d \mid n+1} \Phi_d(q)$ divides $S_k(n; q)$ for all $n$ if and only if $k$ is even.

Therefore, $R_k(q) = \dfrac{S_k(n; q)}{[n+1]_q} \in \mathbb Z[q]$ if and only if $k$ is even. Evaluating at $q = 1$ gives $A_k(n) \in \mathbb Z$ if and only if $k$ is even.

Thus, $\boxed{\frac{1}{n+1} \sum_{i=0}^n \binom{n}{i}^k \in \mathbb Z \quad \text{for all } n \ge 1 \iff k \text{ is even}}.$

2025 USAMO (Problems • Resources)
Preceded by Problem 4	Followed by Problem 6
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

2025 USAMO Problems/Problem 5

Contents

Problem

Solution 1

Solution 2 (q-analog roots of unity)

See Also