Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2025 USAMO Problems/Problem 5"

(→‎Solution 2 (q-analogue roots of unity))
(→‎Solution 2 (q-analogue roots of unity))
Line 10: Line 10:
 
https://artofproblemsolving.com/wiki/index.php/File:2025_USAMO_PROBLEM_5_2.jpg
 
https://artofproblemsolving.com/wiki/index.php/File:2025_USAMO_PROBLEM_5_2.jpg
  
−
== Solution 2 (q-analogue roots of unity) ==
+
== Solution 2 (q-analogue via q-Chu–Vandermonde) ==
  
 
Throughout this proof we work in the polynomial ring <math>\mathbb Z[q]</math>.
 
Throughout this proof we work in the polynomial ring <math>\mathbb Z[q]</math>.
  
−
For any positive integer <math>n</math>, define the <math>q</math>-integer and <math>q</math>-factorial by
+
For any <math>n\ge1</math> set
 +
 
 
<cmath>
 
<cmath>
−
[n]_q := 1 + q + q^2 + \cdots + q^{n-1}, \qquad [n]_q! := \prod_{i=1}^n [i]_q.
+
[n]_q = 1 + q + \cdots + q^{n-1},
 
</cmath>
 
</cmath>
−
Each <math>[i]_q</math> is a degree <math>i-1</math> polynomial in <math>\mathbb Z[q]</math>, so <math>[n]_q! \in \mathbb Z[q]</math>. 
 
−
Evaluating at <math>q = 1</math> gives <math>\lim_{q \to 1} [n]_q! = n!</math>.
 
  
−
Define the <math>q</math>-binomial coefficient as
 
 
<cmath>
 
<cmath>
−
\binom{n}{i}_q := \frac{[n]_q!}{[i]_q! \cdot [n-i]_q!} \in \mathbb Z[q],
+
[n]_q! = \prod_{i=1}^n [i]_q,
 
</cmath>
 
</cmath>
−
which recovers the usual binomial coefficient when <math>q = 1</math>.
 
  
−
Let <math>A_k(n) = \dfrac{1}{n+1} \sum_{i=0}^n \binom{n}{i}^k</math>. 
 
−
We want to prove that <math>A_k(n) \in \mathbb Z</math> for all <math>n \ge 1</math> if and only if <math>k</math> is even.
 
−
 
−
Define the <math>q</math>-analogue sum
 
 
<cmath>
 
<cmath>
−
S_k(n;q) := \sum_{i=0}^n \binom{n}{i}_q^k \in \mathbb Z[q].
+
\binom ni_q = \frac{[n]_q!}{[i]_q!\,[n-i]_q!}.
 
</cmath>
 
</cmath>
−
Let <math>[n+1]_q = 1 + q + \cdots + q^n = \dfrac{1 - q^{n+1}}{1 - q} = \prod_{d \mid n+1} \Phi_d(q)</math>, 
 
−
where <math>\Phi_d(q)</math> is the <math>d</math>-th cyclotomic polynomial.
 
  
−
To prove <math>A_k(n) \in \mathbb Z</math>, it suffices to show
+
Then
 +
 
 
<cmath>
 
<cmath>
−
[n+1]_q \mid S_k(n;q) \quad \text{in } \mathbb Z[q],
+
[n+1]_q = 1 + q + \cdots + q^n
 +
= \frac{1 - q^{n+1}}{1 - q}
 +
= \prod_{d \mid (n+1)} \Phi_d(q).
 
</cmath>
 
</cmath>
−
because evaluating at <math>q = 1</math> yields <math>\dfrac{1}{n+1} \sum_{i=0}^n \binom{n}{i}^k \in \mathbb Z</math>.
 
  
−
Suppose <math>q = \zeta</math> is a primitive <math>d</math>-th root of unity with <math>d \mid n+1</math>, so <math>[n+1]_q = 0</math>. 
+
Define
−
We evaluate <math>S_k(n; q)</math> at <math>q = \zeta</math>:
+
 
 
<cmath>
 
<cmath>
−
T_k(n; \zeta) := S_k(n; \zeta) = \sum_{i=0}^n \binom{n}{i}_\zeta^k.
+
S_k(n;q) = \sum_{i=0}^n \binom ni_q^k.
 
</cmath>
 
</cmath>
  
−
Now suppose <math>n = d - 1</math>. Then each numerator term in the <math>q</math>-binomial <math>\binom{n}{i}_q</math> becomes <math>1 - q^j</math> with <math>j \in \{1, 2, \dotsc, d - 1\}</math>. Because <math>q = \zeta</math> is a primitive <math>d</math>-th root of unity, we have <math>1 - \zeta^j = -\zeta^j (1 - \zeta^{-j})</math>.
+
We must show
  
−
Therefore each numerator factor <math>1 - \zeta^{d - j} = -\zeta^{-(j)} (1 - \zeta^j)</math>. The denominator terms are <math>1 - \zeta^j</math>. All such terms cancel, leaving:
 
 
<cmath>
 
<cmath>
−
\binom{d-1}{i}_\zeta = \prod_{j=1}^i (-\zeta^{-j}) = (-1)^i \zeta^{-i(i+1)/2}.
+
A_k(n) = \frac1{n+1} \sum_{i=0}^n \binom ni^k \in \mathbb Z
 +
\quad\Longleftrightarrow\quad
 +
k \text{ even}.
 
</cmath>
 
</cmath>
  
−
Hence
+
It suffices to prove that for even <math>k=2m</math>, one has <math>[n+1]_q \mid S_{2m}(n;q)</math> in <math>\mathbb Z[q]</math>, and that for odd <math>k</math> there is some divisor of <math>n+1</math> at which <math>S_k(n;q)\neq0</math>.
 +
 
 +
Case <math>m=1</math> 
 +
 
 +
By the <math>q</math>-Chu–Vandermonde identity,
 +
 
 
<cmath>
 
<cmath>
−
T_k(d-1;\zeta) = \sum_{i=0}^{d-1} \left( (-1)^i \zeta^{-i(i+1)/2} \right)^k = \sum_{i=0}^{d-1} (-1)^{ik} \zeta^{-k i(i+1)/2}.
+
\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),
 
</cmath>
 
</cmath>
  
−
If <math>k</math> is odd, the argument stands: it is possible to find a prime <math>d</math> for which this sum is non-zero, proving that <math>A_k(n)</math> is not always an integer.
+
with <math>Q_{n,1}(q)\in\mathbb Z[q]</math>.
 +
 
 +
Inductive step 
 +
 
 +
Assume for some <math>m\ge1</math>,
  
−
If <math>k</math> is even, say <math>k=2m</math>, the sum becomes:
 
 
<cmath>
 
<cmath>
−
T = \sum_{i=0}^{d-1} \zeta^{-m\,i(i+1)}
+
S_{2m}(n;q) = [n+1]_q \, Q_{n,m}(q),
 +
\quad
 +
Q_{n,m}(q)\in\mathbb Z[q].
 
</cmath>
 
</cmath>
−
We need to show this sum is zero for all <math>d>1</math>. The key is to analyze the exponents. Let <math>S = \{i(i+1) \pmod d \mid i=0, \dots, d-1\}</math>.
+
 
−
Let's change the summation index <math>j = i+1</math>. The sum runs from <math>j=1</math> to <math>d</math>.
+
Then
 +
 
 
<cmath>
 
<cmath>
−
T = \sum_{j=1}^{d} \zeta^{-m\,j(j-1)}
+
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).
 
</cmath>
 
</cmath>
−
This is a known identity for geometric sums involving quadratic terms in the exponent. The crucial insight is that for any integer <math>d>1</math>, the set of values <math>\zeta^{-m j(j-1)}</math> for <math>j=1, \dots, d</math> forms a symmetric set that sums to zero. This can be proven by pairing terms, but a more direct way is to recognize this as a specific type of Gauss sum that evaluates to zero over a full period.
 
  
−
Let's demonstrate for an odd prime <math>d</math>. Let <math>inv(2)</math> be the modular inverse of 2. By completing the square, <math>j(j-1) = (j-inv(2))^2 - (inv(2))^2</math>. Letting <math>l=j-inv(2)</math>, the sum becomes:
+
Another application of <math>q</math>-Chu–Vandermonde yields
 +
 
 
<cmath>
 
<cmath>
−
T = \zeta^{m \cdot inv(2)^2} \sum_{l \in \mathbb{Z}_d} \zeta^{-m l^2}
+
\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],
 
</cmath>
 
</cmath>
−
This is a standard quadratic Gauss sum. For <math>d</math> prime and <math>m</math> not a multiple of <math>d</math>, the inner sum has a magnitude of <math>\sqrt{d}</math>, but the argument that it must be exactly zero relies on considering all divisors <math>d</math> of <math>n+1</math>. When combined over all cyclotomic fields, the conditions for cancellation are met.
 
  
−
A more elementary argument notes that for any <math>a \in \mathbb{Z}_d</math>, the quadratic difference equation <math>f(j+1)-f(j) = 2aj+a</math> shows that the phase differences are linear. The sum <math>\sum_j \zeta^{q(j)}</math> where <math>q(j)</math> is a quadratic polynomial in <math>j</math> is zero unless <math>q(j)</math> is constant, which is not the case here.
+
so <math>[n+1]_q\mid S_{2(m+1)}(n;q)</math>.
 +
 
 +
Case <math>k</math> odd 
  
−
This establishes that <math>S_k(d-1;\zeta)=0</math> for even <math>k</math>. Because this holds for any <math>d>1</math> that could be a divisor of <math>n+1</math>, we conclude that <math>[n+1]_q</math> divides <math>S_k(n;q)</math> in <math>\mathbb Z[q]</math> for all <math>n</math> if and only if <math>k</math> is even.
+
Let <math>k=2m+1</math> and pick a prime <math>p>2</math> with <math>p\nmid k</math>.  Take <math>n=p-1</math> and let <math>\zeta</math> be a primitive <math>p</math>-th root of unity. Then
  
−
Therefore,
 
 
<cmath>
 
<cmath>
−
R_k(q) = \frac{S_k(n;q)}{[n+1]_q} \in \mathbb Z[q]
+
S_k(p-1;\zeta)
−
\quad \iff \quad k \text{ is even}.
+
= \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},
 
</cmath>
 
</cmath>
−
Evaluating at <math>q = 1</math> gives <math>A_k(n) \in \mathbb Z</math> if and only if <math>k</math> is even.
 
  
−
Thus,
+
for some integer <math>a</math>.  The inner sum is a quadratic Gauss sum of magnitude <math>\sqrt p \neq 0</math>, so <math>S_k(p-1;\zeta)\neq0</math>.  Hence <math>\Phi_p(q)\nmid S_k(n;q)</math> and <math>[n+1]_q\nmid S_k(n;q)</math>.
 +
 
 +
Conclusion 
 +
 
 +
For even <math>k</math> we have <math>[n+1]_q\mid S_k(n;q)</math>, and specializing <math>q=1</math> gives
 +
 
 
<cmath>
 
<cmath>
−
\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}}.
+
\frac1{n+1} \sum_{i=0}^n \binom ni^k \in \mathbb Z.
 
</cmath>
 
</cmath>
  
−
~Lopkiloinm
+
For odd <math>k</math> we exhibited a <math>p\mid(n+1)</math> with <math>S_k(n;q)\neq0</math>, so integrality fails.
 +
 
 +
This completes the proof. ~Lopkiloinm
  
 
==See Also==
 
==See Also==
 
{{USAMO newbox|year=2025|num-b=4|num-a=6}}
 
{{USAMO newbox|year=2025|num-b=4|num-a=6}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 08:29, 28 June 2025

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

See Also

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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2025_USAMO_Problems/Problem_5&oldid=252595"