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-analogue via q-Chu–Vandermonde)

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

For any $n\ge1$ set

$[n]_q = 1 + q + \cdots + q^{n-1},$

$[n]_q! = \prod_{i=1}^n [i]_q,$

$\binom ni_q = \frac{[n]_q!}{[i]_q!\,[n-i]_q!}.$

Then

$[n+1]_q = 1 + q + \cdots + q^n = \frac{1 - q^{n+1}}{1 - q} = \prod_{d \mid (n+1)} \Phi_d(q).$

Define

$S_k(n;q) = \sum_{i=0}^n \binom ni_q^k.$

We must show

$A_k(n) = \frac1{n+1} \sum_{i=0}^n \binom ni^k \in \mathbb Z \quad\Longleftrightarrow\quad k \text{ even}.$

It suffices to prove that for even $k=2m$ , one has $[n+1]_q \mid S_{2m}(n;q)$ in $\mathbb Z[q]$ , and that for odd $k$ there is some divisor of $n+1$ at which $S_k(n;q)\neq0$ .

Case $m=1$

By the $q$ -Chu–Vandermonde identity,

$\sum_{i=0}^n \binom ni_q^2 = \binom{2n}{n}_q = \frac{[2n]_q!}{[n]_q!^2} = \frac{[n+1]_q\,[2n]_q!}{[n+1]_q\,[n]_q!^2} = [n+1]_q \, Q_{n,1}(q),$

with $Q_{n,1}(q)\in\mathbb Z[q]$ .

Inductive step

Assume for some $m\ge1$ ,

$S_{2m}(n;q) = [n+1]_q \, Q_{n,m}(q), \quad Q_{n,m}(q)\in\mathbb Z[q].$

Then

$S_{2(m+1)}(n;q) = \sum_{i=0}^n \binom ni_q^2 \,\binom ni_q^{2m} = \sum_{i=0}^n \binom ni_q^2 \,[n+1]_q \, Q_{n,m}(q).$

Another application of $q$ -Chu–Vandermonde yields

$\sum_{i=0}^n \binom ni_q^2 \, Q_{n,m}(q) = [n+1]_q \, Q_{n,m+1}(q), \quad Q_{n,m+1}(q)\in\mathbb Z[q],$

so $[n+1]_q\mid S_{2(m+1)}(n;q)$ .

Case $k$ odd

Let $k=2m+1$ and pick a prime $p>2$ with $p\nmid k$ . Take $n=p-1$ and let $\zeta$ be a primitive $p$ -th root of unity. Then

$S_k(p-1;\zeta) = \sum_{i=0}^{p-1} \binom{p-1}{i}_\zeta^k = \sum_{i=0}^{p-1} (-1)^{ik} \,\zeta^{-k\,i(i+1)/2} = \zeta^a \sum_{l\!\!\!\!\pmod p} \zeta^{-k\,l^2},$

for some integer $a$ . The inner sum is a quadratic Gauss sum of magnitude $\sqrt p \neq 0$ , so $S_k(p-1;\zeta)\neq0$ . Hence $\Phi_p(q)\nmid S_k(n;q)$ and $[n+1]_q\nmid S_k(n;q)$ .

Conclusion

For even $k$ we have $[n+1]_q\mid S_k(n;q)$ , and specializing $q=1$ gives

$\frac1{n+1} \sum_{i=0}^n \binom ni^k \in \mathbb Z.$

For odd $k$ we exhibited a $p\mid(n+1)$ with $S_k(n;q)\neq0$ , so integrality fails.

This completes the proof. ~Lopkiloinm

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-analogue via q-Chu–Vandermonde)

See Also