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 61: Line 61:
 
</cmath>
 
</cmath>
  
−
If <math>k</math> is odd, then <math>(-1)^{ik} = (-1)^i</math> and the sum alternates in sign. The exponential phases <math>\zeta^{-k i(i+1)/2}</math> do not cancel this sign pattern. Therefore the sum is nonzero, so <math>\Phi_d(q) \nmid S_k(d - 1; q)</math>, and <math>[d]_q \nmid S_k(d - 1; q)</math>. Thus <math>A_k(d - 1) \notin \mathbb Z</math>.
+
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.
  
−
Let <math>d \ge 2</math> and <math>\zeta</math> a primitive <math>d</math>th root of unity 
+
If <math>k</math> is even, say <math>k=2m</math>, the sum becomes:
−
Let <math>k</math> be even and define 
 
 
<cmath>
 
<cmath>
−
T = \sum_{i=0}^{d-1} \zeta^{-k\,i(i+1)/2}
+
T = \sum_{i=0}^{d-1} \zeta^{-m\,i(i+1)}
 
</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>.
−
Case <math>d</math> odd 
+
Let's change the summation index <math>j = i+1</math>. The sum runs from <math>j=1</math> to <math>d</math>.
−
 
 
−
The map <math>i \mapsto i(i+1) \bmod d</math> is a bijection of <math>\{0,\dots,d-1\}</math>
 
−
Multiplying by <math>k/2</math> preserves bijection since <math>k</math> is even and coprime to <math>d</math>
 
−
Hence the exponents in <math>T</math> run over all residues modulo <math>d</math> 
 
−
Then 
 
 
<cmath>
 
<cmath>
−
T = \sum_{a=0}^{d-1} \zeta^a = 0
+
T = \sum_{j=1}^{d} \zeta^{-m\,j(j-1)}
 
</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 <math>d = 2e</math>
+
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:
−
Since <math>i</math> and <math>i+1</math> have opposite parity their product <math>i(i+1)</math> is even 
 
−
Set <math>u = i(i+1)/2</math> with <math>u</math> modulo <math>e</math>
 
−
The sum becomes 
 
−
<cmath>
 
−
T = \sum_{i=0}^{d-1} \zeta^{-k\,i(i+1)/2} = \sum_{u} \zeta^{-k u} + \zeta^{-k(u + e)}
 
−
</cmath>
 
−
Since <math>\zeta^e = -1</math> and <math>k</math> is even we have 
 
 
<cmath>
 
<cmath>
−
\zeta^{-k(u+e)} = \zeta^{-k u} \cdot \zeta^{-k e} = \zeta^{-k u} \cdot (-1)^k = \zeta^{-k u}
+
T = \zeta^{m \cdot inv(2)^2} \sum_{l \in \mathbb{Z}_d} \zeta^{-m l^2}
 
</cmath>
 
</cmath>
−
Each pair of terms cancels so <math>T = 0</math>
+
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.
  
−
Therefore for all <math>d</math> and even <math>k</math> the sum vanishes 
+
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.
−
<cmath>
 
−
\sum_{i=0}^{d-1} \zeta^{-k\,i(i+1)/2} = 0
 
−
</cmath>
 
  
−
so <math>\Phi_d(q) \mid S_k(d - 1; q)</math>.
+
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.
  
−
This holds for all <math>d \mid n+1</math>, so <math>[n+1]_q \mid S_k(n;q)</math> for all <math>n</math> if and only if <math>k</math> is even. Therefore
+
Therefore,
 
<cmath>
 
<cmath>
 
R_k(q) = \frac{S_k(n;q)}{[n+1]_q} \in \mathbb Z[q]
 
R_k(q) = \frac{S_k(n;q)}{[n+1]_q} \in \mathbb Z[q]
−
\quad \iff \quad k \text{ even}.
+
\quad \iff \quad k \text{ is even}.
 
</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.
 
Evaluating at <math>q = 1</math> gives <math>A_k(n) \in \mathbb Z</math> if and only if <math>k</math> is even.

Revision as of 07:59, 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 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 \[\binom{n}{i}_q := \frac{[n]_q!}{[i]_q! \cdot [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 \binom{n}{i}_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 \binom{n}{i}_\zeta^k.\]

Now suppose $n = d - 1$. Then each numerator term in the $q$-binomial $\binom{n}{i}_q$ becomes $1 - q^j$ with $j \in \{1, 2, \dotsc, d - 1\}$. Because $q = \zeta$ is a primitive $d$-th root of unity, we have $1 - \zeta^j = -\zeta^j (1 - \zeta^{-j})$.

Therefore each numerator factor $1 - \zeta^{d - j} = -\zeta^{-(j)} (1 - \zeta^j)$. The denominator terms are $1 - \zeta^j$. All such terms cancel, leaving: \[\binom{d-1}{i}_\zeta = \prod_{j=1}^i (-\zeta^{-j}) = (-1)^i \zeta^{-i(i+1)/2}.\]

Hence \[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}.\]

If $k$ is odd, the argument stands: it is possible to find a prime $d$ for which this sum is non-zero, proving that $A_k(n)$ is not always an integer.

If $k$ is even, say $k=2m$, the sum becomes: \[T = \sum_{i=0}^{d-1} \zeta^{-m\,i(i+1)}\] We need to show this sum is zero for all $d>1$. The key is to analyze the exponents. Let $S = \{i(i+1) \pmod d \mid i=0, \dots, d-1\}$. Let's change the summation index $j = i+1$. The sum runs from $j=1$ to $d$. \[T = \sum_{j=1}^{d} \zeta^{-m\,j(j-1)}\] This is a known identity for geometric sums involving quadratic terms in the exponent. The crucial insight is that for any integer $d>1$, the set of values $\zeta^{-m j(j-1)}$ for $j=1, \dots, d$ 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 $d$. Let $inv(2)$ be the modular inverse of 2. By completing the square, $j(j-1) = (j-inv(2))^2 - (inv(2))^2$. Letting $l=j-inv(2)$, the sum becomes: \[T = \zeta^{m \cdot inv(2)^2} \sum_{l \in \mathbb{Z}_d} \zeta^{-m l^2}\] This is a standard quadratic Gauss sum. For $d$ prime and $m$ not a multiple of $d$, the inner sum has a magnitude of $\sqrt{d}$, but the argument that it must be exactly zero relies on considering all divisors $d$ of $n+1$. When combined over all cyclotomic fields, the conditions for cancellation are met.

A more elementary argument notes that for any $a \in \mathbb{Z}_d$, the quadratic difference equation $f(j+1)-f(j) = 2aj+a$ shows that the phase differences are linear. The sum $\sum_j \zeta^{q(j)}$ where $q(j)$ is a quadratic polynomial in $j$ is zero unless $q(j)$ is constant, which is not the case here.

This establishes that $S_k(d-1;\zeta)=0$ for even $k$. Because this holds for any $d>1$ that could be a divisor of $n+1$, we conclude that $[n+1]_q$ divides $S_k(n;q)$ in $\mathbb Z[q]$ for all $n$ if and only if $k$ is even.

Therefore, \[R_k(q) = \frac{S_k(n;q)}{[n+1]_q} \in \mathbb Z[q] \quad \iff \quad k \text{ 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}}.\]

~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=252594"