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 exists some $n$ for which $\tfrac1{n+1}\sum_i\binom ni^k\notin\mathbb Z$ .

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

Take $n=2$ . Then

$A_k(2) = \frac{1 + 2^k + 1}{3} = \frac{2 + 2^k}{3}.$

If $k$ is odd then $2^k \equiv 2 \pmod 3$ , so $2+2^k \equiv 4 \equiv 1\pmod3$ and hence $3\nmid(2+2^k)$ . Thus $A_k(2)\notin\mathbb Z$ .

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$ the example $n=2$ yields a noninteger, so integrality fails.

This completes the proof.

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