Stay ahead of learning milestones! Enroll in a class over the summer!

Contests & Programs AMC and other contests, summer programs, etc.
AMC and other contests, summer programs, etc.
3 M G
BBookmark  VNew Topic kLocked
Contests & Programs AMC and other contests, summer programs, etc.
AMC and other contests, summer programs, etc.
3 M G
BBookmark  VNew Topic kLocked
G
Topic
First Poster
Last Poster
k a May Highlights and 2025 AoPS Online Class Information
jlacosta   0
May 1, 2025
May is an exciting month! National MATHCOUNTS is the second week of May in Washington D.C. and our Founder, Richard Rusczyk will be presenting a seminar, Preparing Strong Math Students for College and Careers, on May 11th.

Are you interested in working towards MATHCOUNTS and don’t know where to start? We have you covered! If you have taken Prealgebra, then you are ready for MATHCOUNTS/AMC 8 Basics. Already aiming for State or National MATHCOUNTS and harder AMC 8 problems? Then our MATHCOUNTS/AMC 8 Advanced course is for you.

Summer camps are starting next month at the Virtual Campus in math and language arts that are 2 - to 4 - weeks in duration. Spaces are still available - don’t miss your chance to have an enriching summer experience. There are middle and high school competition math camps as well as Math Beasts camps that review key topics coupled with fun explorations covering areas such as graph theory (Math Beasts Camp 6), cryptography (Math Beasts Camp 7-8), and topology (Math Beasts Camp 8-9)!

Be sure to mark your calendars for the following upcoming events:
[list][*]May 9th, 4:30pm PT/7:30pm ET, Casework 2: Overwhelming Evidence — A Text Adventure, a game where participants will work together to navigate the map, solve puzzles, and win! All are welcome.
[*]May 19th, 4:30pm PT/7:30pm ET, What's Next After Beast Academy?, designed for students finishing Beast Academy and ready for Prealgebra 1.
[*]May 20th, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 1 Math Jam, Problems 1 to 4, join the Canada/USA Mathcamp staff for this exciting Math Jam, where they discuss solutions to Problems 1 to 4 of the 2025 Mathcamp Qualifying Quiz!
[*]May 21st, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 2 Math Jam, Problems 5 and 6, Canada/USA Mathcamp staff will discuss solutions to Problems 5 and 6 of the 2025 Mathcamp Qualifying Quiz![/list]
Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Tuesday, May 13 - Aug 26
Thursday, May 29 - Sep 11
Sunday, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
Wednesday, Jul 16 - Oct 29

Prealgebra 2 Self-Paced

Prealgebra 2
Wednesday, May 7 - Aug 20
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
Friday, Jul 25 - Nov 21

Introduction to Algebra A Self-Paced

Introduction to Algebra A
Sunday, May 11 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, May 14 - Aug 27
Friday, May 30 - Sep 26
Monday, Jun 2 - Sep 22
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
Tuesday, Jul 15 - Oct 28

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Thursday, May 15 - Jul 31
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Wednesday, Jul 9 - Sep 24
Sunday, Jul 27 - Oct 19

Introduction to Number Theory
Friday, May 9 - Aug 1
Wednesday, May 21 - Aug 6
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
Tuesday, Jul 15 - Sep 30

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Sunday, May 11 - Nov 9
Tuesday, May 20 - Oct 28
Monday, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
Monday, Jul 14 - Jan 19

Paradoxes and Infinity
Mon, Tue, Wed, & Thurs, Jul 14 - Jul 16 (meets every day of the week!)

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Jun 1 - Nov 23
Tuesday, Jun 10 - Nov 18
Wednesday, Jun 25 - Dec 10
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22

Intermediate Counting & Probability
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Tuesday, Jun 10 - Aug 26

Calculus
Tuesday, May 27 - Nov 11
Wednesday, Jun 25 - Dec 17

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Friday, May 23 - Aug 15
Monday, Jun 2 - Aug 18
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

MATHCOUNTS/AMC 8 Advanced
Sunday, May 11 - Aug 10
Tuesday, May 27 - Aug 12
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Problem Series
Friday, May 9 - Aug 1
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Tuesday, Jun 17 - Sep 2
Sunday, Jun 22 - Sep 21 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Jun 23 - Sep 15
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Final Fives
Sunday, May 11 - Jun 8
Tuesday, May 27 - Jun 17
Monday, Jun 30 - Jul 21

AMC 12 Problem Series
Tuesday, May 27 - Aug 12
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Wednesday, Aug 6 - Oct 22

AMC 12 Final Fives
Sunday, May 18 - Jun 15

AIME Problem Series A
Thursday, May 22 - Jul 31

AIME Problem Series B
Sunday, Jun 22 - Sep 21

F=ma Problem Series
Wednesday, Jun 11 - Aug 27

WOOT Programs
Visit the pages linked for full schedule details for each of these programs!


MathWOOT Level 1
MathWOOT Level 2
ChemWOOT
CodeWOOT
PhysicsWOOT

Programming

Introduction to Programming with Python
Thursday, May 22 - Aug 7
Sunday, Jun 15 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Tuesday, Jun 17 - Sep 2
Monday, Jun 30 - Sep 22

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22

USACO Bronze Problem Series
Tuesday, May 13 - Jul 29
Sunday, Jun 22 - Sep 1

Physics

Introduction to Physics
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
May 1, 2025
0 replies
Jane street swag package? USA(J)MO
arfekete   5
N 2 minutes ago by bebebe
Hey! People are starting to get their swag packages from Jane Street for qualifying for USA(J)MO, and after some initial discussion on what we got, people are getting different things. Out of curiosity, I was wondering how they decide who gets what.
Please enter the following info:

- USAMO or USAJMO
- Grade
- Score
- Award/Medal/HM
- MOP (yes or no, if yes then color)
- List of items you got in your package

I will reply with my info as an example.
5 replies
arfekete
Yesterday at 4:34 PM
bebebe
2 minutes ago
USAMO Medals
YauYauFilter   41
N 3 minutes ago by Inaaya
YauYauFilter
Apr 24, 2025
Inaaya
3 minutes ago
how prestigious is hsmc
ConfidentKoala4   1
N 8 minutes ago by Ilikeminecraft
been wonderin this for a while

how prestigious is it? ik its not as good as mathily (they rejected me :mad: ) but Idk how good it actually is
1 reply
ConfidentKoala4
22 minutes ago
Ilikeminecraft
8 minutes ago
9 Does Mental Health Actually Matter?
heheman   9
N 21 minutes ago by maxamc
Looking at the goals I once had, it was all just so silly and stupid

I didn't even reach my "Low" goal for AIME... so pathetic

Missed JMO by a huge margin, after missing by only 12.5 points last year

(BTW i didn't slack off one bit)

I guess the most important thing is just to keep my head up and keep going. I can't let failures stop me. Honestly I don't care about setting goals anymore. They only give me a lot of internal pressure to do well. I think the most important thing is to focus on what I do everyday, consistently, and pay attention to the beautiful things in life (like math).

I'm going to try getting more involved in real life. After coming back from COVID, I had trouble to make as many friends with non-math people. But I was reconnecting with some of my friends that I had prepandemic and I realized how precious those friendships really were.

Now the last thing to do is grind my last bit of nonexistent ego to dust and focus on the present, stop looking back

(Note: This doesn't mean I'm going to quit, I just mean I'm going to do math on my own and try to not feel any pressure to do well. Cause i feel like that pressure really beat me a lot.)

I love this community and am happy for everyone who qualified olympiad but at this point competition math just reminds me only of my failures. (Even if it's my own fault.) So I'm probably going to take a break for a while. Thanks everyone for being nice to me and stuff. Sorry if this sounds cringe (it will in a week)

9 replies
heheman
Mar 8, 2024
maxamc
21 minutes ago
No more topics!
Scary Binomial Coefficient Sum
EpicBird08   43
N Apr 19, 2025 by Mathgloggers
Source: USAMO 2025/5
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.$
43 replies
EpicBird08
Mar 21, 2025
Mathgloggers
Apr 19, 2025
Scary Binomial Coefficient Sum
G H J
G H BBookmark kLocked kLocked NReply
Source: USAMO 2025/5
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
EpicBird08
1751 posts
#1 • 2 Y
Y by KevinYang2.71, cubres
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.$
This post has been edited 2 times. Last edited by EpicBird08, Mar 21, 2025, 12:06 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
EpicBird08
1751 posts
#2 • 3 Y
Y by KevinYang2.71, Kingsbane2139, cubres
We claim that the answer is $\boxed{\text{all even positive integers}}.$

Proof that odd $k$ fail: Just take $n = 2$ and get $2^k + 2$ is divisible by $3,$ which implies $2^k \equiv 1 \pmod{3}$ This can only happen if $k$ is even.

Proof that even $k$ work: Substitute $n-1$ in place for $n$ in the problem; we then must prove that $$\frac{1}{n} \sum_{i=0}^{n-1} \binom{n-1}{i}^k$$is an integer for all positive integers $n.$ Call $n$ $k$-good if $n$ satisfies this condition. Letting $\Omega(n)$ denote the number of not necessarily distinct prime factors of $n,$ we will prove that all positive integers $n$ are $k$-good by induction on $\Omega(n).$ The base case is trivial since if $\Omega(n) = 0,$ then $n = 1,$ which vacuously works.

Now suppose that the result was true for all $n$ such that $\Omega(n) \le a.$ Let the prime factorization of $n$ be $p_1^{e_1} \cdot p_2^{e_2} \cdots p_m^{e_m},$ where $p_1, \dots, p_m$ are distinct primes and $e_1, \dots, e_m \in \mathbb{N}$ such that $e_1 + \dots + e_m = a+1.$ We will show that $$\sum_{i=0}^{n-1} \binom{n-1}{i}^k \equiv 0 \pmod{p_l^{e_l}}$$for all $1 \le l \le m,$ which finishes the inductive step by CRT.

We compute
\begin{align*}
\binom{n-1}{i} &= \frac{(n-1)!}{i! (n-i-1)!} \\
&= \frac{(n-1)(n-2)\cdots (n-i)}{i!} \\
&= \prod_{j=1}^i \frac{n-j}{j},
\end{align*}so $$\binom{n-1}{i}^k = \prod_{j=1}^i \left(\frac{n-j}{j}\right)^k.$$If $p_l \nmid j,$ then $p_l \nmid n-j$ as well since $p_l \mid n.$ Thus $j$ has a modular inverse modulo $p_l^{e_k},$ so we can say $$\left(\frac{n-j}{j}\right)^k \equiv \left(\frac{-j}{j}\right)^k \equiv (-1)^k \equiv 1 \pmod{p_l^{e_k}}$$because $k$ is even. Hence the terms in this product for which $p_l \nmid j$ contribute nothing to the binomial coefficient.

If $p_l \mid j,$ then we have $$\frac{n-j}{j} = \frac{\frac{n}{p_l} - \frac{j}{p_l}}{\frac{j}{p_l}}.$$Reindexing the product in terms of $\frac{j}{p_l},$ we get $$\binom{n-1}{i}^k \equiv \prod_{j'=1}^{\lfloor i/p_l \rfloor} \left(\frac{n/p_l - j'}{j'}\right)^k \equiv \binom{n/p_l - 1}{\lfloor i/p_l \rfloor}^k \pmod{p_l^{e_l}}.$$Therefore, plugging back into our sum gives $$\sum_{i=0}^{n-1} \binom{n-1}{i}^k \equiv p_l \sum_{i=0}^{n/p_l - 1} \binom{n/p_l - 1}{i}^k \pmod{p_l^{e_l}}.$$By the inductive hypothesis, the sum on the right-hand side is divisible by $p_l^{e_l - 1},$ so the entire sum is divisible by $p_l^{e_l}.$ This completes our inductive step.

Therefore, we have proven that all positive integers $n$ are $k$-good, and we are done.

Click to reveal hidden text
This post has been edited 7 times. Last edited by EpicBird08, Apr 9, 2025, 1:04 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
KevinYang2.71
426 posts
#3 • 2 Y
Y by cubres, deduck
original statement says "for every positive integer $n$"

We claim that $k$ is $\boxed{\mathrm{even}}$.

From $n=2$ we get $3\mid 2+2^n$ so clearly $k$ is even.

Now suppose $k$ is even.

Claim 1. If $\alpha=\nu_2(n+1)$, then $2^\alpha$ divides
\[
\sum_{i=0}^n\binom{n}{i}^k.
\]Proof. We proceed by induction on $\alpha$ with the base case $\alpha=0$ trivial.

Assume the statement for $\alpha-1$. Let $n+1=:2^\alpha m$ and let us work in $\mathbb{Z}/2^\alpha\mathbb{Z}$. Note that if $r$ is even, $(r+1)^{-1}$ exists so
\[
\binom{n}{r+1}=\frac{n-r}{r+1}\binom{n}{r}=\frac{2^\alpha m-(r+1)}{r+1}\binom{n}{r}=-\binom{n}{r}.
\]We prove that $\binom{n}{2r}=(-1)^r\binom{\frac{n-1}{2}}{r}$ for $r=0,\,1,\,\ldots,\,\frac{n-1}{2}$ by induction on $r$ with the base case $r=0$ trivial.

Assume $\binom{n}{2r}=(-1)^r\binom{\frac{n-1}{2}}{r}$. We have
\begin{align*}
\binom{n}{2r+2}&=\frac{n-2r-1}{2r+2}\binom{n}{2r+1}\\
&=-\frac{\frac{n-1}{2}-r}{r+1}\binom{n}{2r}\\
&=(-1)^{r+1}\frac{\frac{n-1}{2}-r}{r+1}\binom{\frac{n-1}{2}}{r}\\
&=(-1)^{r+1}\binom{\frac{n-1}{2}}{r+1},
\end{align*}completing the induction step.

Thus,
\begin{align*}
\sum_{i=0}^n\binom{n}{i}^k&=\sum_{r=0}^{\frac{n-1}{2}}\left(\binom{n}{2r}+\binom{n}{2r+1}\right)^k\\
&=2\sum_{r=0}^{\frac{n-1}{2}}\binom{n}{2r}^k\\
&=2\sum_{r=0}^{\frac{n-1}{2}}\binom{n}{2r}^k\\
&=2\sum_{r=0}^{\frac{n-1}{2}}\left((-1)^r\binom{\frac{n-1}{2}}{r}\right)^k\\
&=2\sum_{r=0}^{\frac{n-1}{2}}\binom{\frac{n-1}{2}}{r}^k.
\end{align*}Since $\nu_2\left(\frac{n+1}{2}\right)=\alpha-1$, by the induction hypothesis with $n':=\frac{n-1}{2}$, $2^{\alpha-1}$ divides
\[
\sum_{r=0}^{n'}\binom{n'}{r}^k.
\]Thus
\[
\sum_{i=0}^n\binom{n}{i}^k=2\sum_{r=0}^{n'}\binom{n'}{r}^k=0,
\]as desired. $\square$

Odd $p$ case is the same except there is no $(-1)^r$ in the proof. Since all prime powers dividing $n+1$ divide $\sum_{i=0}^n\binom{n}{i}^k$, $n+1$ divides $\sum_{i=0}^n\binom{n}{i}^k$. $\square$

How many point dock for dropping ^k in Claim 1 but doing the odd $p$ case correctly (I wrote a Claim 2 that was basically identical to Claim 1 but modified for odd $p$). Also by dropping the ^k, I did not induct on $\alpha$ in Claim 1 because the last summation (wrongly) becomes $0$ directly.
This post has been edited 1 time. Last edited by KevinYang2.71, Mar 21, 2025, 12:17 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
arfekete
259 posts
#4 • 1 Y
Y by cubres
Will I get docked if I just said it was sufficient to prove that the term is divisible by $p^{v_p{(n + 1)}}$ for any arbitrary $p | n + 1$ and didn't mention CRT? (I defined p-adic notation)
This post has been edited 1 time. Last edited by arfekete, Mar 21, 2025, 12:07 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Countmath1
180 posts
#5 • 1 Y
Y by cubres
this is the one thing i started on before i had to leave. i got that all odd k fail and k=2 works by vandermonde's + catalan. 0/21 day 2 baby
This post has been edited 1 time. Last edited by Countmath1, Mar 21, 2025, 12:10 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
balllightning37
389 posts
#7 • 1 Y
Y by cubres
Nice, solution was same as #2.

Do we get docked for not defining $v_p$? I was in a hurry...
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
plang2008
337 posts
#8 • 1 Y
Y by cubres
Bruh I interpreted this as “For each positive integer $n$, find all positive integers $k$ such that this expression is a positive integer”

Then the answer should be all positive integers if $n + 1$ is a power of $2$ and all even positive integers otherwise
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Sleepy_Head
565 posts
#9 • 1 Y
Y by cubres
how many points for correct answer (no proof), odd $k$ doesn't work, and $k=2$ works?
This post has been edited 1 time. Last edited by Sleepy_Head, Mar 21, 2025, 12:42 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
HamstPan38825
8860 posts
#10 • 1 Y
Y by cubres
nvm this solution is actually wrong you have to induct it :/
This post has been edited 2 times. Last edited by HamstPan38825, Mar 21, 2025, 1:34 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
bachkieu
137 posts
#11 • 1 Y
Y by cubres
dnw vp moment??
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Pear222
5 posts
#12 • 3 Y
Y by CertifiedNoob, andyloo666, cubres
sniped by @2above

We claim that the answer is $\boxed{\text{all even positive integers}}$. To show that odd doesn't work, just look at $n=2$.

The main part of the problem is proving that $n+1$ divides \[\sum_{i=0}^n \binom ni ^{2k}.\]Pick a prime $p$ dividing $n+1$, and let $\nu_p(n+1) = e \ge 1$ so that $p^e$ is the maximal power of $p$ dividing $n+1$. Let $n = mp^e-1$ with $\gcd(m,p) = 1$ The key claim is as follows:

Claim 1: For each $0 \le a < e$, we have that \[\sum_{i=0}^{\left\lfloor \frac{n}{p^a}\right\rfloor} \binom{n}{ip^a}^{2k} \equiv p\sum_{i=0}^{\left\lfloor \frac{n}{p^{a+1}}\right\rfloor} \binom{n}{ip^{a+1}}^{2k}\bmod{p^{e-a}}\]
Proof: Consider the values \[\binom{n}{0}^2, \binom{n}{p^a}^2, \dots, \binom{n}{(mp^{e-a}-1)p^a}^2.\]We claim that these values can be blocked into consecutive groups of $p$ such that the values in each block are equal modulo $p^{e-a}$. Specifically, for $p\nmid i+1$, we claim that \[\binom{n}{ip^a} \equiv \binom{n}{(i+1)p^a} \pmod {p^{e-a}}.\]Indeed, we have that
\begin{align*}
\binom{n}{(i+1)p^a}^2 &= \left(\frac{n}{1}\cdot \frac{n-1}{2} \cdots \frac{n+1-j}{j} \cdots \frac{n+1 - (i+1)p^a}{(i+1)p^a}\right)^2 \\
&= \binom{n}{ip^a}^2 \prod_{j = ip^a + 1}^{(i+1)p^a} \left(\frac{n+1}j - 1\right)^2
\end{align*}But for every $ip^a + 1 < j \le (i+1)p^a$, $\nu_p(j) \le a$ since $p\nmid i+1$. Therefore $\frac{n+1}{j} \equiv 0 \bmod{p^{e-a}}$, so the entire product is equal to $1\pmod{p^{e-a}}$; thus the subclaim is true. Therefore we have that
\begin{align*}
\sum_{i=0}^{\left\lfloor \frac{n}{p^a} \right\rfloor} \binom{n}{ip^a}^{2k} &=\sum_{i=0}^{\frac 1p\left\lfloor \frac{n}{p^a} \right\rfloor} \sum_{j= ip}^{ip+p-1} \left(\binom{n}{jp^a}^2\right)^k\\
& \equiv \sum_{i=0}^{\left\lfloor \frac{n}{p^{a+1}} \right\rfloor} p\left(\binom{n}{ip(p^a)}^2\right)^k \pmod{ p^{e-a}}\\
& \equiv p\sum_{i=0}^{\left\lfloor \frac{n}{p^{a+1}} \right\rfloor} \binom{n}{ip^{a+1}}^{2k}
\end{align*}and the claim is proven.

To finish, note that a quick induction implies that \[p^{e-a} \mid \sum_{i=0}^{\left\lfloor \frac{n}{p^a}\right\rfloor} \binom{n}{ip^a}^{2k}\]for all $0\le a \le e$. Taking $a = 0$ gives that \[p^e \mid \sum_{i=0}^{n} \binom ni^k\]for any prime power $p^e$ dividing $n+1$. This means that \[\frac 1{n+1} \sum_{i=0}^n \binom ni^{2k}\]is an integer for any $k\in \mathbb{N}$, so we are done.
This post has been edited 2 times. Last edited by Pear222, Apr 5, 2025, 8:22 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pianoboy
320 posts
#13 • 1 Y
Y by cubres
I noticed (by taking powers over first 10 rows of Pascal triangle) that (n choose k)^4 = (n choose k)^2 mod (n+1). Is that always true?

If we prove that the problem is basically solved.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
YaoAOPS
1540 posts
#14 • 1 Y
Y by cubres
$n = 215, k = 54$ is a counterexample.
This post has been edited 1 time. Last edited by YaoAOPS, Mar 21, 2025, 1:37 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
NoSignOfTheta
1736 posts
#15 • 1 Y
Y by cubres
No its not
This post has been edited 2 times. Last edited by NoSignOfTheta, Mar 21, 2025, 1:46 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
YaoAOPS
1540 posts
#16 • 1 Y
Y by cubres
yes it is????????
Attachments:
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pianoboy
320 posts
#17 • 1 Y
Y by cubres
What ? This false conjecture with an absurdly high counterexample?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
OronSH
1733 posts
#18 • 3 Y
Y by centslordm, peppapig_, cubres
Answer is even $k$. Odd $k$ fail at $n=2$.

Let $m=n+1$ and set $\nu_p(m)=s$. The main idea is that \begin{align*}\binom{pm-1}{pi+j}&=\frac{(pm-1)(pm-2)\cdots(pm-pi-j)}{1\cdot 2\cdots(pi+j)}\\&=\left(\frac{pm-1}1\cdot\frac{pm-2}2\cdots\frac{pm-p+1}{p-1}\cdot\frac{pm-p-1}{p+1}\cdots\right)\cdot\frac{(m-1)(m-2)\cdots(m-i)}{1\cdot 2\cdots i}\\&\equiv\pm\binom{m-1}i\pmod{p^{s+1}}.\end{align*}Then \[\sum_{i=0}^{pm-1}\binom{pm-1}i^k\equiv p\sum_{i=0}^{m-1}\binom{m-1}i^k\pmod{p^{s+1}}\]so inducting on $\nu_p(m)$ works.
This post has been edited 1 time. Last edited by OronSH, Mar 21, 2025, 1:54 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
OronSH
1733 posts
#19 • 1 Y
Y by cubres
pianoboy wrote:
What ? This false conjecture with an absurdly high counterexample?

$n=8,k=3$ is a counterexample
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
NoSignOfTheta
1736 posts
#20 • 1 Y
Y by cubres
YaoAOPS wrote:
yes it is????????

ohhh I thought u were talking about the actual problem
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Ilikeminecraft
619 posts
#21 • 1 Y
Y by cubres
how many points will proving the case for $\operatorname{rad}(n) = n$(prime exponents are 1)
This post has been edited 1 time. Last edited by Ilikeminecraft, Mar 21, 2025, 3:21 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
awesomeguy856
7265 posts
#22 • 3 Y
Y by OronSH, bjump, cubres
OronSH wrote:
Answer is even $k$. Odd $k$ fail at $n=2$.

Let $m=n+1$ and set $\nu_p(m)=s$. The main idea is that \begin{align*}\binom{pm-1}{pi+j}&=\frac{(pm-1)(pm-2)\cdots(pm-pi-j)}{1\cdot 2\cdots(pi+j)}\\&=\left(\frac{pm-1}1\cdot\frac{pm-2}2\cdots\frac{pm-p+1}{p-1}\cdot\frac{pm-p-1}{p+1}\cdots\right)\cdot\frac{(m-1)(m-2)\cdots(m-i)}{1\cdot 2\cdots i}\\&\equiv\pm\binom{m-1}i\pmod{p^{s+1}}.\end{align*}Then \[\sum_{i=0}^{pm-1}\binom{pm-1}i^k\equiv p\sum_{i=0}^{m-1}\binom{m-1}i^k\pmod{p^{s+1}}\]so inducting on $\nu_p(m)$ works.

more like pmo
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
krithikrokcs
148 posts
#23 • 1 Y
Y by cubres
if i wrote my solution backwards will i get points off?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6877 posts
#24 • 5 Y
Y by Curious_Droid, jkim0656, cubres, krithikrokcs, Sedro
The answer is all even $k$.
Let's abbreviate $S(n) \coloneq \binom n0^k + \dots + \binom nn^k$ for the sum in the problem.
Proof that even $k$ is necessary. Choose $n=2$. We need $3 \mid S(2) = 2+2^k$, which requires $k$ to be even.

Remark: It's actually not much more difficult to just use $n = p-1$ for prime $p$, since $\binom{p-1}{i} \equiv (-1)^i \pmod p$. Hence $S(p-1) \equiv 1 + (-1)^k + 1 + (-1)^k + \dots + 1 \pmod p$, and this also requires $k$ to be even. This special case is instructive in figuring out the proof to follow.

Proof that $k$ is sufficient. From now on we treat $k$ as fixed, and we let $p^e$ be a prime fully dividing $n+1$. The basic idea is to reduce from $n+1$ to $(n+1)/p$ by an induction.

Remark: Here is a concrete illustration that makes it clear what's going on. Let $p = 5$. When $n = p-1 = 4$, we have \[ S(4) = 1^k + 4^k + 6^k + 4^k + 1^k \equiv 1 + 1 + 1 + 1 + 1 \equiv 0 \pmod 5. \]When $n = p^2-1 = 24$, the $25$ terms of $S(24)$ in order are, modulo $25$, \begin{align*} S(24) &\equiv 1^k + 1^k + 1^k + 1^k + 1^k\\ &+ 4^k + 4^k + 4^k + 4^k + 4^k \\ &+ 6^k + 6^k + 6^k + 6^k + 6^k \\ &+ 4^k + 4^k + 4^k + 4^k + 4^k \\ &+ 1^k + 1^k + 1^k + 1^k + 1^k \\ &= 5(1^k + 4^k + 6^k + 4^k + 1^k). \end{align*}The point is that $S(24)$ has five copies of $S(4)$, modulo $25$.
To make the pattern in the remark explicit, we prove the following lemma on each individual binomial coefficient.
Lemma: Suppose $p^e$ is a prime power which fully divides $n+1$. Then \[ \binom{n}{i} \equiv \pm \binom{\frac{n+1}{p}-1}{\left\lfloor i/p \right\rfloor} \pmod{p^e}. \]Proof. [Proof of lemma] It's easiest to understand the proof by looking at the cases $\left\lfloor i/p \right\rfloor \in \{0,1,2\}$ first.
  • For $0 \le i < p$, since $n \equiv -1 \mod p^e$, we have \[ \binom{n}{i} = \frac{n(n-1) \dots (n-i+1)}{1 \cdot 2 \cdot \dots \cdot i} \equiv \frac{(-1)(-2) \dots (-i)}{1 \cdot 2 \cdot \dots \cdot i} \equiv \pm 1 \pmod{p^e}. \]
  • For $p \le i < 2p$ we have \begin{align*} \binom{n}{i} &\equiv \pm 1 \cdot \frac{n-p+1}{p} \cdot \frac{(n-p)(n-p-1) \dots (n-i+1)}{(p+1)(p+2) \dots i} \\ &\equiv \pm 1 \cdot \frac{\frac{n-p+1}{p}}{1} \cdot \pm 1 \\ &\equiv \pm \binom{\frac{n+1}{p}-1}{1} \pmod{p^e}. \end{align*}
  • For $2p \le i < 3p$ the analogous reasoning gives \begin{align*} \binom ni &\equiv \pm 1 \cdot \frac{n-p+1}{p} \cdot \pm 1 \cdot \frac{n-2p+1}{2p} \cdot \pm 1 \\ &\equiv \pm \frac{\left(\frac{n+1}{p}-1\right)\left( \frac{n+1}{p}-2 \right) }{1 \cdot 2} \\ &\equiv \pm \binom{\frac{n+1}{p}-1}{2} \pmod{p^e}. \end{align*}
\dots And so on. The point is that in general, if we write \[ \binom ni = \prod_{0 \le j \le i} \frac{n-(j-1)}{j} \]then the fractions for $p \nmid j$ are all $\pm 1 \pmod{p^e}$. So only considers those $j$ with $p \mid j$; in that case one obtains the claimed $\binom{\frac{n+1}{p}-1}{\left\lfloor i/p \right\rfloor}$ exactly (even without having to take modulo $p^e$). $\blacksquare$
From the lemma, it follows if $p^e$ is a prime power which fully divides $n+1$, then \[ S(n) \equiv p \cdot S\left( \frac{n+1}{p}-1 \right) \pmod{p^e} \]by grouping the $n+1$ terms (for $0 \le i \le n$) into consecutive ranges of length $p$ (by the value of $\left\lfloor i/p \right\rfloor$).
This post has been edited 1 time. Last edited by v_Enhance, Mar 21, 2025, 2:59 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Mathandski
757 posts
#25 • 1 Y
Y by cubres
I initially fakesolved this problem writing a proof that was somewhat a convoluted way of saying $\binom{n}{i} \equiv \binom{-1}{i} \pmod{n}$. Realized this with 2 hours left and had to start over. 25AMO5 gave me the exact same feeling as 24JMO4. It took another 1:15 to solve correctly - easily the most stressful hour of my life. I measured my heart rate with roughly an hour left and it was at 50 beats / 20 seconds = 150 BPM.
This post has been edited 1 time. Last edited by Mathandski, Mar 21, 2025, 3:01 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6877 posts
#26 • 2 Y
Y by NaturalSelection, cubres
Realized this with 2 hours left and had to start over. In total it took 1:15 to solve correctly; the most stressful hour of my life. I measured my heart rate with 45 minutes left and it was at 50 beats / 20 seconds = 150 BPM
I remember that experience as a student too. In my case, the problem was USAMO 2014/4, but I only had 20 minutes to fix my wrong solution.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
peppapig_
281 posts
#27 • 15 Y
Y by YaoAOPS, OronSH, KnowingAnt, golue3120, centslordm, i3435, sixoneeight, EpicBird08, VicKmath7, Lam040208, Supercali, cubres, krithikrokcs, scannose, john0512
Haven't seen this solution yet! Pure manipulation, no induction on $p$.

We claim that the answer is all even $k$, odd $k$ dies to $n=2$.

For even $k$, let $k=2m$ for $m\in \mathbb{Z}^+$, note that
\[\binom{n}{i}^{2m}=\binom{n}{0}^{2m}+\left(\binom{n}{1}^{2m}-\binom{n}{0}^{2m}\right)+\left(\binom{n}{2}^{2m}-\binom{n}{1}^{2m}\right)+\dots+\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right).\]Now, summing this up over all $1\le i\le n$, we have
\[\sum_{i=0}^{n}\binom{n}{i}^{2m}=(n+1)\binom{n}{0}^{2m}+\sum_{i=1}^{n}(n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right).\]
It now suffices to show that
\[(n+1)\mid (n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right),\]for all $1\le i\le n$. However, note that since $2m$ is even, we have that
\[(n+1-i)\left(\binom{n}{i}+\binom{n}{i-1}\right) \mid (n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right).\]But we also have that
\[(n+1-i)\left(\binom{n}{i}+\binom{n}{i-1}\right)=(n+1-i)\binom{n+1}{i}=(n+1-i)\cdot \frac{(n+1)!}{(n+1-i)!i!}=(n+1)\cdot \frac{n!}{(n-i)!i!},\]which is just $(n+1)\binom{n}{i}$. This is clearly divisible by $n+1$, proving that
\[(n+1)\mid (n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right),\]for all $1\le i\le n$.

Summing this over all $i$, this means that
\[(n+1)\mid \sum_{i=1}^{n}(n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right),\]so
\[(n+1)\mid (n+1)\binom{n}{0}^{2m}+\sum_{i=1}^{n}(n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right)=\sum_{i=0}^{n}\binom{n}{i}^{2m},\]as desired. Therefore all even $k$ work, completing our proof.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ihatemath123
3446 posts
#28 • 6 Y
Y by peace09, Lhaj3, sixoneeight, cubres, biomathematics, megarnie
theres no way this problem hasnt already been posted somewhere in hso or math overflow 20 years ago or smth
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
solasky
1566 posts
#29 • 1 Y
Y by cubres
v_Enhance wrote:
The answer is all even $k$.
Let's abbreviate $S(n) \coloneq \binom n0^k + \dots + \binom nn^k$ for the sum in the problem.
Proof that even $k$ is necessary. Choose $n=2$. We need $3 \mid S(2) = 2+2^k$, which requires $k$ to be even.

Remark: It's actually not much more difficult to just use $n = p-1$ for prime $p$, since $\binom{p-1}{i} \equiv (-1)^i \pmod p$. Hence $S(p-1) \equiv 1 + (-1)^k + 1 + (-1)^k + \dots + 1 \pmod p$, and this also requires $k$ to be even. This special case is instructive in figuring out the proof to follow.

Proof that $k$ is sufficient. From now on we treat $k$ as fixed, and we let $p^e$ be a prime fully dividing $n+1$. The basic idea is to reduce from $n+1$ to $(n+1)/p$ by an induction.

Remark: Here is a concrete illustration that makes it clear what's going on. Let $p = 5$. When $n = p-1 = 4$, we have \[ S(4) = 1^k + 4^k + 6^k + 4^k + 1^k \equiv 1 + 1 + 1 + 1 + 1 \equiv 0 \pmod 5. \]When $n = p^2-1 = 24$, the $25$ terms of $S(24)$ in order are, modulo $25$, \begin{align*} S(24) &\equiv 1^k + 1^k + 1^k + 1^k + 1^k\\ &+ 4^k + 4^k + 4^k + 4^k + 4^k \\ &+ 6^k + 6^k + 6^k + 6^k + 6^k \\ &+ 4^k + 4^k + 4^k + 4^k + 4^k \\ &+ 1^k + 1^k + 1^k + 1^k + 1^k \\ &= 5(1^k + 4^k + 6^k + 4^k + 1^k). \end{align*}The point is that $S(24)$ has five copies of $S(4)$, modulo $25$.
To make the pattern in the remark explicit, we prove the following lemma on each individual binomial coefficient.
Lemma: Suppose $p^e$ is a prime power which fully divides $n+1$. Then \[ \binom{n}{i} \equiv \pm \binom{\frac{n+1}{p}-1}{\left\lfloor i/p \right\rfloor} \pmod{p^e}. \]Proof. [Proof of lemma] It's easiest to understand the proof by looking at the cases $\left\lfloor i/p \right\rfloor \in \{0,1,2\}$ first.
  • For $0 \le i < p$, since $n \equiv -1 \mod p^e$, we have \[ \binom{n}{i} = \frac{n(n-1) \dots (n-i+1)}{1 \cdot 2 \cdot \dots \cdot i} \equiv \frac{(-1)(-2) \dots (-i)}{1 \cdot 2 \cdot \dots \cdot i} \equiv \pm 1 \pmod{p^e}. \]
  • For $p \le i < 2p$ we have \begin{align*} \binom{n}{i} &\equiv \pm 1 \cdot \frac{n-p+1}{p} \cdot \frac{(n-p)(n-p-1) \dots (n-i+1)}{(p+1)(p+2) \dots i} \\ &\equiv \pm 1 \cdot \frac{\frac{n-p+1}{p}}{1} \cdot \pm 1 \\ &\equiv \pm \binom{\frac{n+1}{p}-1}{1} \pmod{p^e}. \end{align*}
  • For $2p \le i < 3p$ the analogous reasoning gives \begin{align*} \binom ni &\equiv \pm 1 \cdot \frac{n-p+1}{p} \cdot \pm 1 \cdot \frac{n-2p+1}{2p} \cdot \pm 1 \\ &\equiv \pm \frac{\left(\frac{n+1}{p}-1\right)\left( \frac{n+1}{p}-2 \right) }{1 \cdot 2} \\ &\equiv \pm \binom{\frac{n+1}{p}-1}{2} \pmod{p^e}. \end{align*}
\dots And so on. The point is that in general, if we write \[ \binom ni = \prod_{0 \le j \le i} \frac{n-(j-1)}{j} \]then the fractions for $p \nmid j$ are all $\pm 1 \pmod{p^e}$. So only considers those $j$ with $p \mid j$; in that case one obtains the claimed $\binom{\frac{n+1}{p}-1}{\left\lfloor i/p \right\rfloor}$ exactly (even without having to take modulo $p^e$). $\blacksquare$
From the lemma, it follows if $p^e$ is a prime power which fully divides $n+1$, then \[ S(n) \equiv p \cdot S\left( \frac{n+1}{p}-1 \right) \pmod{p^e} \]by grouping the $n+1$ terms (for $0 \le i \le n$) into consecutive ranges of length $p$ (by the value of $\left\lfloor i/p \right\rfloor$).

Wait I proved the lemma in-contest but I didn’t realize you can just induct on that to finish :sob: I didn’t even write it down b/c I thought it was a dead end, oh well
This post has been edited 1 time. Last edited by solasky, Mar 21, 2025, 4:29 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Mathandski
757 posts
#30 • 3 Y
Y by solasky, GrantStar, cubres
v_Enhance wrote:
Remark: Here is a concrete illustration that makes it clear what's going on. Let $p = 5$. When $n = p-1 = 4$, we have \[ S(4) = 1^k + 4^k + 6^k + 4^k + 1^k \equiv 1 + 1 + 1 + 1 + 1 \equiv 0 \pmod 5. \]When $n = p^2-1 = 24$, the $25$ terms of $S(24)$ in order are, modulo $25$, \begin{align*} S(24) &\equiv 1^k + 1^k + 1^k + 1^k + 1^k\\ &+ 4^k + 4^k + 4^k + 4^k + 4^k \\ &+ 6^k + 6^k + 6^k + 6^k + 6^k \\ &+ 4^k + 4^k + 4^k + 4^k + 4^k \\ &+ 1^k + 1^k + 1^k + 1^k + 1^k \\ &= 5(1^k + 4^k + 6^k + 4^k + 1^k). \end{align*}The point is that $S(24)$ has five copies of $S(4)$, modulo $25$.

These are the exact numbers I used to motivate my solve as well :O
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
golue3120
57 posts
#31 • 5 Y
Y by GrantStar, OronSH, centslordm, cubres, MS_asdfgzxcvb
well, I guess I have to post this

Answer is all even $k$, necessity follows from setting $n=2$. Henceforth assume $k$ is even.

Lemma. Let $p^e$ be a prime power. Then $\textstyle (1+x)^{p^e}\equiv (1+x^p)^{p^{e-1}}\pmod p^e$.
Proof. When $e=1$, $\textstyle(1+x)^p=1+x^p+\sum_{i=1}^{p-1}\binom pix^i\equiv 1+x^p\pmod p$. Now we induct on $e$. Suppose $\textstyle (1+x)^{p^e}\equiv (1+x^p)^{p^{e-1}}\pmod p^e$. Then $\textstyle (1+x)^{p^e}=(1+x^p)^{p^{e-1}}+p^eQ$ where $Q$ is some integer polynomials. Raising both sides to the power of $p$, we have $\textstyle (1+x)^{p^{e+1}}=(1+x^p)^{p^e}+\text{terms divisible by }p^{e+1}$, as desired.

We now prove that for every positive integer $m$, prime $p$, and nonnegative integer $e$,
\[p^e\mid\sum_{i=0}^{mp^e-1}\binom{mp^e-1}i^k.\]
We induct on $e$. If $e=0$, this is trivial. Now suppose it holds for $e$. Working modulo $p^{e+1}$, we have
\[(1-x)^{mp^{e+1}-1}=\frac{(1-x)^{mp^{e+1}}}{1-x}=\frac{(1+(-x)^p)^{mp^e}}{1-x}=\frac{1+(-x)^p}{1-x}(1+(-x)^p)^{mp^e-1}=(1+(-x)^p)^{mp^e-1}\sum_{i=0}^{p-1}x^i.\]Thus by comparing coefficients, $\textstyle\binom{mp^{e+1}-1}{qp+r}\equiv\pm\binom{mp^e-1}{q}$ for $0\le q<mp^e$, $0\le r<p$. Therefore, modulo $p^{e+1}$,
\[\sum_{i=0}^{mp^{e+1}-1}\binom{mp^{e+1}-1}{i}^k=\sum_{q=0}^{mp^e-1}\sum_{r=0}^{p-1}\binom{mp^e-1}{q}=p\sum_{q=0}^{mp^e-1}\binom{mp^e-1}{q}.\]By the inductive hypothesis, the last sum is a multiple of $p^e$, hence the first sum is a multiple of $p^{e+1}$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Curious_Droid
37 posts
#32 • 2 Y
Y by peppapig_, cubres
Here is my solution which I stumbled upon after four hours of feverish grinding. I cannot make up my mind whether it is beautiful or just incredibly ugly. Scariest thing is, I still don't know if its correct :blush:

Lemma: If $\nu_p(c) = \nu_p(m) \ge 1$, then $p^k \mid {m-1 \choose c\cdot p^k -1}$ for any $k \ge 1$.

Proof: Kummers Theorem.

Corollary: Take positive integers $i, n$. Define $g = \gcd(i, n+1)$ and $i = g\cdot a\cdot b$ where $\gcd(b, n+1) = 1$ and $b$ is maximal. Then $a \mid {n \choose i-1}$.

Proof: Take one prime exponent $p^k \mid a$, where $k = \nu_p(a)$. By maximality of $b$, $p \mid n+1$. Obviously $p \nmid b$, and we must have $p \nmid \frac{n+1}{g}$. Thus $\nu_p(n+1) = \nu_p(g) = \nu_p\left(\frac{i}{p^k}\right)$, all $\ge 1$, and the desired follows by applying the Lemma. $\Box$

The case where $k$ is odd is easy, so we assume $k$ is even and show the desired conclusion.

Now consider the following process: Start with $n+1$ ones lined up in a row. Then on step $i$, multiply the central $n+1-2i$ terms by $\frac{n+1-i}{i}$. Obviously, we eventually construct the sequence of all binomial coefficients, and after step $i$, the sequence will be

$$1, {n \choose 1}, {n \choose 2}, \dots, {n \choose i-1}, \underbrace{{n \choose i}, \dots, {n \choose i}}_{\text{$n+1-2i$ copies}}, {n \choose i-1}, \dots, {n \choose 2}, {n \choose 1}, 1$$
Let $S_i$ be the sum of the $k$th powers of these terms after step $i$. As a result, $S_0 = n+1$. We claim that $S_i$ is invariant throughout the process.

Proof: First, note that $S_i - S_{i-1} = (n+1-2i)\left( {n \choose i}^k - {n \choose i-1}^k \right) =(n+1-2i){n \choose i-1}^k\left( \left(\frac{n+1-i}{i}\right)^k -1 \right) $. Now define $g = \gcd(i, n+1)$ and $i = g\cdot a\cdot b$ where $\gcd(b, n+1) = 1$ and $b$ is maximal. Further, let $n+1 = gd$. By the Corollary, $a \mid {n \choose i-1}$. Thus, we may set $X = \left(\frac{{n \choose i-1}}{a}\right)^k \in \mathbb Z$. Now
\begin{align*}
{n \choose i-1}^k\left( \left(\frac{n+1-i}{i}\right)^k -1 \right) &= X \cdot a^k \cdot \left( \left(\frac{gd-gab}{gab}\right)^k -1 \right)\\
&= X \cdot \left( \left(\frac{d-ba}{b}\right)^k -a^k \right)\\
&\equiv X \cdot \left( \left(\frac{-ba}{b}\right)^k -a^k \right)\\
&\equiv X \cdot \left( (-a)^k -a^k \right)\\
&\equiv 0 \pmod{d},
\end{align*}where division by $b$ was allowed because $\gcd(b, d) = 1$. Further, it is obvious that $g \mid n+1-2i$, so in conclusion, $n+1 = gd \mid S_i - S_{i-1}$. $\Box$

It is clear to see how we finish from here.

Note: Just a worse, more convoluted version of peppapig_'s solution.
This post has been edited 7 times. Last edited by Curious_Droid, Mar 22, 2025, 2:25 AM
Reason: clown
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
john0512
4187 posts
#33 • 1 Y
Y by cubres
Clearly, $k$ is even as $n=2$ gives $3\mid 2+2^k$. Now, we show that all even $k$ work. Let $k=2m$.

Main Claim: If $p^r$ is a prime power such that $n\equiv -1\pmod{p^r}$, then
$${n\choose i}^{2m} \equiv {\lfloor n/p\rfloor \choose \lfloor i/p\rfloor}^{2m} \pmod{p^r}.$$
Consider the equation

$${n\choose i}=(\frac{n}{1})(\frac{n-1}{2})(\frac{n-2}{3})\dots(\frac{n-i+1}{i}).$$
Denote the "$k$th slot" as the fraction $\frac{n-k+1}{k}$. Considering just the slots that are multiples of $p$,

$$\frac{n-p+1}{p}\cdot \frac{n-2p+1}{2p}\cdots \frac{n-p\lfloor i/p \rfloor+1}{p\lfloor i/p\rfloor}$$$$=\frac{\lfloor n/p\rfloor}{1}\cdot \frac{\lfloor n/p\rfloor-1}{2}\cdots \frac{\lfloor n/p\rfloor-\lfloor i/p \rfloor +1}{\lfloor i/p\rfloor}$$$$={\lfloor n/p \rfloor \choose \lfloor i/p \rfloor}.$$
However, if $p\nmid k$, then the $k$th slot is
$$\frac{n-k+1}{k}\equiv \frac{-k}{k}\equiv -1\pmod{p^r},$$so if the exponent is even, the slots that are not multiples of $p$ do not affect the residue mod $p^r$ at all, which shows the claim.

Let $f(n)= \sum_{i=0}^n {n\choose i}^{2m}$. Then, if $n\equiv -1\pmod{p^r}$, then by the above claim,

$$f(n)={n\choose 0}^{2m} + {n\choose 1}^{2m}+\dots+{n\choose n}^{2m}$$$$\equiv {\lfloor n/p\rfloor \choose \lfloor 0/p\rfloor}^{2m}+{\lfloor n/p\rfloor \choose \lfloor 1/p\rfloor}^{2m}+\dots+{\lfloor n/p\rfloor \choose \lfloor n/p\rfloor}^{2m}$$$$\equiv p \left [ {\lfloor n/p \rfloor \choose 0}^{2m}+{\lfloor n/p \rfloor \choose 1}^{2m}+\dots+{\lfloor n/p \rfloor \choose \lfloor n/p \rfloor}^{2m}  \right ] \pmod{p^r}$$$$f(n) \equiv pf(\lfloor n/p \rfloor)\pmod{p^r}.$$
Finally we induct on the number of trailing $p-1$'s in the base $p$ representation of $n$ to show that $n\equiv -1\pmod{p^r}$ implies $p^r\mid f(n)$. If there is one trailing $p-1$, then clearly the above implies $p\mid f(n)$. Then, if $n$ has $r$ trailing $p-1$'s, then $\lfloor n/p \rfloor$ has $r-1$ trailing $p-1$'s. Thus, if $p^{r-1}\mid f(\lfloor n/p\rfloor)$, then $p^r\mid f(n)$, as desired.

Since $p^r\mid n+1$ implies $p^r\mid f(n)$, we are done.
This post has been edited 2 times. Last edited by john0512, Mar 22, 2025, 5:16 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
plang2008
337 posts
#34 • 2 Y
Y by cubres, megarnie
I misread it. The answer is all $k$ if $n + 1$ is a power of $2$ and all even $k$ otherwise.


Consider a prime $p \mid n + 1$, and let $a = \nu_p(n + 1)$. Notice that by definition we have $\binom ni = \prod_{j=1}^i \frac{n+1-j}{j}$. Since $p \mid n + 1$, we have $p \mid n + 1 - j$ if $p \mid j$ and $p\nmid n + 1 - j$ otherwise, so for each term, either both the numerator are divisible by $p$, or neither are. Let $M$ be the number of terms in the denominator that are not divisible by $p$.

For each term such that $p \nmid j$, we have $n + 1 - j \equiv -j$, so $\frac{n + 1 - j}{j} \equiv -1 \pmod {p^a}$. For each term such that $p \mid j$, we can divide out a $p$ from both the numerator and the denominator. Notice that what's left is simply $\binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor}$. Thus, we conclude that \[\boxed{\binom ni \equiv (-1)^M \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor}}.\]

Proof that $k$ even works for all $p$: For $n = p - 1$, we clearly have \[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (-1)^{Mk} \equiv p \equiv 0 \pmod p.\]
Now consider $n = p(d + 1) - 1$ where $\nu_p(n) = a$, and suppose that $n = d$ satisfies the induction hypothesis for the prime $p$. Clearly $\nu_p(d + 1) = a - 1$. Then we have \[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (-1)^{Mk} \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor}^k \equiv p\sum_{i=0}^d \binom di^k \pmod {p^a}\]By the induction hypothesis, $p^{a-1}$ divides the inner binomial sum, so since we are multiplying it by $p$, $p^a$ must divide $\sum_{i=0}^n \binom ni^k$.


Proof that $k$ odd fails for $p \neq 2$: For $n = p - 1$, we clearly have \[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (-1)^{Mk} \equiv 1 \pmod p.\]
Now consider $n = p(d + 1) - 1$ where $\nu_p(n) = a$, and suppose that $n = d$ satisfies the induction hypothesis for the prime $p$. Since $p - 1$ is even, there exists one more $(-1)^M = 1$ than $(-1)^M = -1$ for each block of $p$ such that $\lfloor i/p \rfloor$ remains constant. Then we have \[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (-1)^{Mk} \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor}^k \equiv \sum_{i=0}^d \binom di^k \pmod {p^a}.\]By the induction hypothesis, $p^{a-1}$ does not divide this sum, so $p^a$ does not divide it either.


Proof that $k$ odd works for $n + 1$ a power of $2$: Let $p = 2$. For $n = 1$, clearly odd $k$ work as $1^k + 1^k \equiv 0 \pmod 2$. Now suppose odd $k$ works for $n = 2^d - 1$. If we let $n = 2^{d+1} - 1$, then we have \[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (-1)^{Mk} \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor}^k \pmod{2^{d+1}}.\]
Notice that the since for each block of $p = 2$ such that $\lfloor i/p \rfloor$ remains constant, there is exactly one odd $M$ and one even $M$. Thus, the sum simply vanishes $\bmod~2^{d+1}$.


Since all even $k$ work for all primes $p$, it follows by CRT that all even $k$ work. For $n + 1$ not a power of $2$, there exists an odd prime $p$ such that $p \mid n + 1$, which can be easily used to show that all odd $k$ fail.
This post has been edited 1 time. Last edited by plang2008, Mar 22, 2025, 4:53 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
awesomeming327.
1714 posts
#35 • 1 Y
Y by cubres
Define
\begin{align*}
f_k(n,i) &= \binom{n-1}{i}^k \\
F_k(n) &= \sum_{i=0}^{n-1}f_k(n,i)
\end{align*}We want to find all $k$ such that $n\mid F_k(n)$ for all positive integers $n\ge 2$. Clearly, letting $n=3$, we have
\[3\mid F_k(n,i)=1^k+2^k+1^k\]which forces $k$ to be even.

Now we show that when $k$ is even, $n\mid F_k(n)$. Let $\nu_p(n)=a\ge 1$. First, we prove a claim.

Claim 1: $f_k(n,ip+j)\equiv f_k(n,ip+j+1)\pmod{p^a}$ for all $0\le j\le p-2$.
Note that we have
\begin{align*}
f_k(n,ip+j+1) &= \left(\frac{(n-1)!}{(ip+j+1)!(n-ip-j-2)!}\right)^k \\
&= \left(\frac{(n-1)!}{(ip+j)!(n-ip-j-1)!}\right)^k\cdot \left(\frac{n-ip-j-1}{ip+j+1}\right)^k \\
&\equiv f_k(n,ip+j)\cdot 1\pmod {p^a}
\end{align*}
This implies that $f_k(n,i)\pmod {p^a}$ is constant given that $\lfloor i/p\rfloor$ is constant. Therefore,
\[F_k(n)\equiv p\sum_{i=0}^{n/p-1}f_k(n,ip)\pmod {p^a}\]We now continue to our second claim.

Claim 2: Then $f_k(n,ip)\equiv f_k(n/p,i)\pmod{p^{a-1}}$ for all $0\le i\le p-1$.
We proceed by induction on $i$. Note that if $i=0$ this simply says $1\equiv 1\pmod {p^{a-1}}$ which is trivially true. Now assume
\[f_k(n/p,i)\equiv f_k(n,ip)\equiv f_k(n,ip+p-1)\pmod {p^{a-1}}\]and we have
\begin{align*}
f_k(n,(i+1)p)&\equiv f_k(n,ip+p-1)\cdot \frac{(n-(i+1)p)}{(i+1)p} \\ 
&\equiv f_k(n/p,i)\cdot \left(\frac{n/p-i-1}{i+1}\right)^k \\
&\equiv f_k(n/p,i+1) \pmod {p^{a-1}}
\end{align*}Which completes the induction step.
Now we have
\[F_k(n)\equiv p\sum_{i=0}^{n/p-1}f_k(n,ip)\equiv pF_k(n/p)\pmod {p^a}\]so if $p^{a-1}\mid F_k(n/p)$ then $p^a\mid F_k(n)$. By induction we are done.
This post has been edited 1 time. Last edited by awesomeming327., Mar 22, 2025, 9:27 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MathLuis
1524 posts
#36 • 2 Y
Y by KevinYang2.71, cubres
If $k$ is odd then $n=2$ fails, now if $k$ is even then from CRT all we need is to prove that $p^{\ell} \mid \sum_{i=0}^{m \cdot p^{\ell}-1} \binom{m \cdot p^{\ell}-1}{i}^k$.
For this matter notice that (for $y<p$) and some positive integer $x$ such that $m \cdot p^{\ell}-1>xp+y$ that:
\[ \binom{m \cdot p^{\ell}-1}{xp+y}=\left( \frac{(m \cdot p^{\ell}-1) \cdots (m \cdot p^{\ell}-p+1)(m \cdot p^{\ell}-p-1) \cdots )}{1 \cdots (p-1)(p+1) \cdots} \right) \cdot \frac{(mp^{\ell-1}-1) \cdots (mp^{\ell-1}-x)}{1 \cdots x} \equiv \pm \binom{m \cdot p^{\ell-1}-1}{x} \pmod{p^{\ell}} \]So now using this notice that we have $\sum_{i=0}^{m \cdot p^{\ell}-1} \binom{m \cdot p^{\ell}-1}{i}^k \equiv p \cdot \sum_{i=0}^{m \cdot p^{\ell-1}-1} \binom{m \cdot p^{\ell-1}-1}{i}^k \pmod{p^{\ell}}$ so we can induct down and throw CRT until we get a degenerate case of the divisibility prompt in which case it is a trivial result thus we are done :cool:.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
deduck
238 posts
#37 • 3 Y
Y by KevinYang2.71, LostDreams, cubres
The answer is even only.

Odds fail because of $n=2$.

Now let $n+1 = \Pi p_a^{e_a}$. To show that evens work, we will induct by taking mod $p_a^{e_a}$, then CRT finishes.

We want to prove $$\sum_{i=0}^n \binom{n}{i}^k = 0 (\text{mod } p_a^{e_a})$$.

We will proceed by induction based on $v_{p_a}(n+1)$. When $v_{p_a}(n+1) = 0$ it's obvious.

For the inductive step, let's look at each $\binom{n}{i}^k$ individually. Note that $\binom{n}{i}^k = \Pi \frac{(n+1)-x}{x}$. Therefore, if $p_a \nmid x$, then both the numerator and denominator of $\frac{(n+1)-x}{x}$ are relatively prime, therefore it's $-1$. But since $k$ is even $(-1)^k=1$ and it does nothing. So just ignore all $x$ with $p_a \nmid x$.

Therefore $$\binom{n}{i}^k = \Pi \frac{(n+1)-x}{x} = \Pi_{p_a | x} \frac{\frac{n+1}{p_a} - \frac{x}{p_a}}{\frac{x}{p_a}} = \binom{\frac{n+1}{p_a}-1}{\lfloor \frac{i}{p_a} \rfloor}^k.$$
Therefore $$\sum_{i=0}^n \binom{n}{i}^k = \sum_{i=0}^n \binom{\frac{n+1}{p_a} - 1}{\lfloor \frac{i}{p_a} \rfloor}^k (\text{mod } p_a^{e_a})$$
Finishes by inductive assumption
This post has been edited 1 time. Last edited by deduck, Mar 23, 2025, 5:46 AM
Reason: typo bruh
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
deduck
238 posts
#38 • 1 Y
Y by cubres
Motivation:
We can see that to move from $\binom{n}{i}$ to $\binom{n}{i+1}$ we see that we multiply by $\frac{n-i}{i+1}$, and this fraction is $-1$ when $p$ and $i$ are relatively prime. So that eliminates all odd cases in general no matter which $n$ u picked as long as $n$ is prime (i just said n=2 because it takes less explanation). Because if it's odd then $(-1)^k = -1$ and it breaks but we need $(-1)^k=1$.

However the issue is what if $i$ and $p$ aren't relatively prime?

Obviously first take a prime $p^e$ from $n$ to make it easier because CRT duh

But then everything is divisible by whichever prime $p$ that we picked and then it's easy to see we can use induction after shrink the binomial coefficient by $p$ on the top and bottom

i fakesolved it first in like 10 min then i was like sus i did not think about $i$ and $n$ aren't relatively prime, im simple minded lmao
This post has been edited 2 times. Last edited by deduck, Mar 23, 2025, 6:37 AM
Reason: typo
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
atdaotlohbh
186 posts
#40 • 1 Y
Y by cubres
The answer is all $k \ \vdots \ 2$.
To prove odd numbers don't work, consider $n=3$. Then we need $$1^k+2^k+1^k=2+2^k \ \vdots \ 3$$which tells us $k$ should be even.

Now we will prove that all evens work. To do that, let's prove that if $n+1 \ \vdots \ p^{\alpha}$, then $\sum_{i=0}^n \binom{n}{i}^k \ \vdots \ p^{\alpha}$.
We will do it using induction on $\alpha$. Base case $\alpha=0$ is trivial.
Now suppose $\alpha=u$ works, let's prove $u+1$ works. Notice that $$\frac{n+1-r}{r} \equiv -1 \pmod {p^{u+1}} \text{ for all } r \not\vdots p$$It implies that $$\binom{n}{pi}^k \equiv \binom{n}{pi+r}^k \pmod {p^{u+1}} \text{ for all } 0 \leq r \leq p-1$$Thus $$\sum_{i=0}^n \binom{n}{i}^k \equiv p\sum_{i=0}^{\frac{n+1}{p}-1} \binom{n}{pi}^k \pmod {p^{u+1}}$$So it remains to prove that $$\sum_{i=0}^{\frac{n+1}{p}-1} \binom{n}{pi}^k \ \vdots \ p^u$$But still by the fact above $$\binom{n}{pt}^k=(\prod_{i=1}^{pt} \frac{n+1-i}{i})^k \equiv (\prod_{i=1}^{t} \frac{n+1-pi}{pi})^k \equiv (\prod_{i=1}^{t} \frac{\frac{n+1}{p}-i}{i})^k \equiv \binom{\frac{n+1}{p}-1}{t}^k \pmod {p^u}$$And so we need to prove that $$\sum_{i=0}^{\frac{n+1}{p}-1} \binom{\frac{n+1}{p}-1}{t}^k \ \vdots \ p^u$$And that is our induction hypothesis. The induction is done.

As $\sum_{i=0}^n \binom{n}{i}^k$ is divisible by every prime power of $n+1$, it is divisible by $n+1$ and hence $\frac{1}{n+1} \sum_{i=0}^n \binom{n}{i}^k$ is an integer.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Mathandski
757 posts
#41 • 2 Y
Y by KevinYang2.71, cubres
If you see any issue in the following solution, please email me at westskigamer@gmail.com.
This solution was what I officially submitted. I have transcribed it per verbatim.

Submitted Solution
This post has been edited 1 time. Last edited by Mathandski, Mar 26, 2025, 4:34 AM
Reason: fix typo
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Fibonacci_11235
44 posts
#42
Y by
While solving the problem, I discovered that
${\binom{n}{0}}^2 + {\binom{n}{1}}^2 + \dots + {\binom{n}{n}}^2 = \binom{2n}{n}$

which immediately settles the case when $k=2$, using the fact that $C_n = \frac{1}{n+1} \binom{2n}{n}$ is an integer. Motivated by this observation, I tried evaluating the sum for other values of $k$, but made no progress. Is it possible to solve the problem in this way?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Irreplaceable
1274 posts
#43
Y by
very scary indeed
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
zoinkers
12 posts
#44 • 1 Y
Y by Fibonacci_11235
Fibonacci_11235 wrote:
While solving the problem, I discovered that
${\binom{n}{0}}^2 + {\binom{n}{1}}^2 + \dots + {\binom{n}{n}}^2 = \binom{2n}{n}$

which immediately settles the case when $k=2$, using the fact that $C_n = \frac{1}{n+1} \binom{2n}{n}$ is an integer. Motivated by this observation, I tried evaluating the sum for other values of $k$, but made no progress. Is it possible to solve the problem in this way?

no, as far as i know there is no closed form for the sum when $k \ge 3$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
programjames1
3046 posts
#45
Y by
Newton Sums
Unfortunately this only works for odd $n$.
This post has been edited 2 times. Last edited by programjames1, Apr 13, 2025, 6:24 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Mathgloggers
82 posts
#46
Y by
Isn't just this babbage's congruence theorem which states that:
$\binom{ap}{bp} \equiv \binom{a}b mod(p)$,or what we trying to show here :
$\binom{mp^e -1}{ip} \equiv (-1)^k\binom{mp^{e-1}-1}{i}$,then applying our inductive hypothesis .
Z K Y
N Quick Reply
G
H
=
a