Scary Binomial Coefficient Sum

Art of Problem Solving

AoPS Online

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

No tags match your search

M

Scary Binomial Coefficient Sum

G H J

Reveal topic tags

L

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.

1740 posts

#1 h Mar 21, 2025, 11:59 AM • 1 Y

Y by KevinYang2.71

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.

1740 posts

#2 h Mar 21, 2025, 12:01 PM • 1 Y

Y by KevinYang2.71

We claim that the answer is $\boxed{\text{all even 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 4 times. Last edited by EpicBird08, Yesterday at 4:03 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

409 posts

#3 h Mar 21, 2025, 12:04 PM

Y by

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.

247 posts

#4 h Mar 21, 2025, 12:06 PM

Y by

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.

176 posts

#5 h Mar 21, 2025, 12:09 PM

Y by

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

382 posts

balllightning37

#7 h Mar 21, 2025, 12:26 PM

Y by

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.

329 posts

#8 h Mar 21, 2025, 12:31 PM

Y by

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.

562 posts

#9 h Mar 21, 2025, 12:33 PM

Y by

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.

8857 posts

#10 h Mar 21, 2025, 12:53 PM

Y by

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.

131 posts

#11 h Mar 21, 2025, 12:58 PM

Y by

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.

5 posts

#12 h Mar 21, 2025, 1:22 PM • 2 Y

Y by CertifiedNoob, andyloo666

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 1 time. Last edited by Pear222, Mar 21, 2025, 1:30 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

320 posts

#13 h Mar 21, 2025, 1:32 PM

Y by

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.

1500 posts

#14 h Mar 21, 2025, 1:37 PM

Y by

$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.

1692 posts

#15 h Mar 21, 2025, 1:45 PM

Y by

No its not

53031441159622046326327094779576487532705078723889948233144005742849311334346641167247987665250164456319302501118190363981913546084408930974035276684384343684364317026824580859910580034496128407258293749608158596365741974566381148422021723495377174985334070920958857037684040737975130505283736106347656411528020854195187480540512064305979335137972544361944077974584772119227219605460283270029863823395260229656221228429994365626695009019304655554162663087963822866578602476940867988759171617624282603498492460931993252720524497084581219259506956694198024970457703174242564603519835258152580067014935962722271645999400919842122798881580127951401920949353491433373382053216186341065921711311913876446395797658927550709236575020460238369470162109852707920171413962299467941675410151822835931141078445960298997332901867250353450894088036755122497777862682795818835475294211474178314584011270780586690421181483156171502774400366590212176509516408423709660259966449320439650902480302193572969307516458052898936411352619193780586471916277523417110701569708439736252478513702152773264218558461046253161255293706645154815495679212818529935411152680813155323090458969139535553824553079368514076772241441250499736135708722317359654810862200534539705418591621948550395185912994885152856379374022647410456528203488381373498216464649408012999726049816427717742759427916548940121001005790882600437047287294001931783602544729374494674973279585732796400683178190592137997973791197801711002257570751515046458384434678479683690099228691366770881334184291297525721965281237825405731491483042623036052098640016825155256548301100626548824093538937958082046084229491965258664676747225592302497184628709938033157612905305480363610548396786428851469208648806729213508186798508270079313783359325789100959251002301125680773104663521303105042415577081103989640074323041455815843712726866718995861138109553418156904083555769324112626027465942029508924518158602327278197247326508739742873224461370752492036234096907660917726200633234879888685454313610243104691738788052224863357097327778914716387511870769039029141383926281302159712594399631356521028027229241465155462305043154172552825161925729706578079444238571842484837560995743527132807987677207620798069602577591425280375461245739448367725727773486042374253098712688135220590567814929800914165106754221713516085034436414679527371949914709313997111165170342234634876746569663603989599326142140031037019730037199047257839185786311930369008585720558719729429467208218221850994836632699195030319853516877475503000523506198703583466597628495405184299036933805324728496661392146786903487992036260218832261468419744554490569325277529573270515262361250570579846870941366291388136176952521990735971808672377782857554691897048324330074742366488204933262790120965747532422981618548183385304677040848133824534852598960762467041761887844962826855561547362229939930586186058596137319161470761633071921723160937237347668340490301208486986278896188512403450151792844812536792463199934599079087103489779830138200790610715410012674141132193309131954222289334885555087670172924199887392682338664253154965727868971240630008299161161829583784835406953784778111621984215670183728832238912280528733029588861447282555701887578037321783612252105625049747792403581816465388555606661047432559226531619920485136813613859011131264287899863575663212300164235659285942785853854066175185870616020760370174266313521295241947182619000

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.

1500 posts

#16 h Mar 21, 2025, 1:47 PM

Y by

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.

320 posts

#17 h Mar 21, 2025, 1:48 PM

Y by

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.

1727 posts

OronSH

#18 h Mar 21, 2025, 1:49 PM • 2 Y

Y by centslordm, peppapig_

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.

1727 posts

OronSH

#19 h Mar 21, 2025, 1:50 PM

Y by

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.

1692 posts

#20 h Mar 21, 2025, 1:52 PM

Y by

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.

308 posts

#21 h Mar 21, 2025, 1:57 PM

Y by

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.

7263 posts

#22 h Mar 21, 2025, 2:18 PM • 2 Y

Y by OronSH, bjump

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.

146 posts

#23 h Mar 21, 2025, 2:50 PM

Y by

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.

6870 posts

#24 h Mar 21, 2025, 2:57 PM • 2 Y

Y by Curious_Droid, jkim0656

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.

724 posts

#25 h Mar 21, 2025, 2:58 PM

Y by

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.

6870 posts

#26 h Mar 21, 2025, 3:01 PM • 1 Y

Y by NaturalSelection

Mathandski wrote:

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.

279 posts

#27 h Mar 21, 2025, 3:19 PM • 8 Y

Y by YaoAOPS, OronSH, KnowingAnt, golue3120, centslordm, i3435, sixoneeight, EpicBird08

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.

3440 posts

#28 h Mar 21, 2025, 3:22 PM • 3 Y

Y by peace09, Lhaj3, sixoneeight

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.

1566 posts

#29 h Mar 21, 2025, 4:26 PM

Y by

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.

724 posts

#30 h Mar 21, 2025, 4:49 PM • 2 Y

Y by solasky, GrantStar

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.

54 posts

#31 h Mar 21, 2025, 5:46 PM • 3 Y

Y by GrantStar, OronSH, centslordm

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.

35 posts

#32 h Mar 22, 2025, 2:14 AM • 1 Y

Y by peppapig_

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:

: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.

4173 posts

#33 h Mar 22, 2025, 5:10 AM

Y by

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.

329 posts

#34 h Mar 22, 2025, 4:51 PM

Y by

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.

1674 posts

awesomeming327.

#35 h Mar 22, 2025, 9:26 PM

Y by

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.

1466 posts

#36 h Mar 23, 2025, 1:49 AM • 1 Y

Y by KevinYang2.71

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:

:cool:

.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

177 posts

deduck

#37 h Mar 23, 2025, 5:24 AM • 2 Y

Y by KevinYang2.71, LostDreams

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.

177 posts

deduck

#38 h Mar 23, 2025, 5:31 AM

Y by

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.

171 posts

#40 h Mar 23, 2025, 5:01 PM

Y by

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

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a