AoPS Academy
, 
,
, 
, why 
or even expressions of those terms combined as if that would make them defined. I have made this post to answer these questions once and for all, and I politely ask everyone to link this post to threads that are talking about this issue.. It is usually regarded that 
, not because this works numerically but because it is convenient to define it this way. You will see the convenience of defining other undefined things later on in this post.? The issue here is that 
isn't even rigorously defined in this expression. What exactly do we mean by ? Unless the example in question is put in context in a formal manner, then we say that is meaningless.? Suppose that 
. Then we would have 
, absurd. A more rigorous treatment of the idea is that 
does not exist in the first place, although you will see why in a calculus course. So the point is that is undefined.
? An article from brilliant has a good explanation. Alternatively, you can just use a geometric series. Notice that
? Usually this is considered to be an indeterminate form, but I would also wager that this is also undefined.
indeterminate? In analysis (the theory behind calculus and beyond), limits involving an algebraic combination of functions in an independent variable may often be evaluated by replacing these functions by their limits. However, if the expression obtained after this substitution does not provide sufficient information to determine the original limit, then the expression is called an indeterminate form. For example, we could say that is an indeterminate form.
, 
or , obtained by applying the algebraic limit theorem (a theorem in analysis, look this up for details) in the process of attempting to determine a limit, which fails to restrict that limit to one specific value or infinity, and thus does not determine the limit being calculated. This is why it is called indeterminate. Some examples of indeterminate forms are![\[0/0, \infty/\infty, \infty-\infty, \infty \times 0\]](http://latex.artofproblemsolving.com/2/6/0/260f97a1cf1ea8722ff97a29b83bac7bfe83e577.png)
etc etc. So what makes something undefined? In the broader scope, something being undefined refers to an expression which is not assigned an interpretation or a value. A function is said to be undefined for points outside its domain. For example, the function 
given by the mapping 
is undefined for 
. On the other hand, 
is undefined because dividing by is not defined in arithmetic by definition. In other words, something is undefined when it is not defined in some mathematical context. is considered both indeterminate and undefined (but in the context of a limit then it is considered in indeterminate form). Additionally, this notion of something being undefined also means that we can define it in some way. To rephrase, this means that technically, we can make something that is undefined to something that is defined as long as we define it. I'll show you what I mean.![\[\overline{\mathbb{R}}=\mathbb{R}\cup \{-\infty,+\infty\}.\]](http://latex.artofproblemsolving.com/9/9/3/993c78b62ec2c84b5d77daa8e9a8cd6f70fcf904.png)
So instead of treating infinity as an idea, we define infinity (positively and negatively, mind you) as actual numbers in the reals. The advantage of doing this is for two reasons. The first is because we can turn this thing into a totally ordered set. Specifically, we can let 
for each 
which means that via this order topology each subset has an infimum and supremum and 
is therefore compact. While this is nice from an analytic standpoint, extending the reals in this way can allow for interesting arithmetic! In it is perfectly OK to say that,![\begin{align*}
a + \infty = \infty + a & = \infty, & a & \neq -\infty \\
a - \infty = -\infty + a & = -\infty, & a & \neq \infty \\
a \cdot (\pm\infty) = \pm\infty \cdot a & = \pm\infty, & a & \in (0, +\infty] \\
a \cdot (\pm\infty) = \pm\infty \cdot a & = \mp\infty, & a & \in [-\infty, 0) \\
\frac{a}{\pm\infty} & = 0, & a & \in \mathbb{R} \\
\frac{\pm\infty}{a} & = \pm\infty, & a & \in (0, +\infty) \\
\frac{\pm\infty}{a} & = \mp\infty, & a & \in (-\infty, 0).
\end{align*}](http://latex.artofproblemsolving.com/6/d/8/6d8fc1eca5c791d430a7168cd3b37a02104fa318.png)
So addition, multiplication, and division are all defined nicely. However, notice that we have some indeterminate forms here which are also undefined,![\[\infty-\infty,\frac{\pm\infty}{\pm\infty},\frac{\pm\infty}{0},0\cdot \pm\infty.\]](http://latex.artofproblemsolving.com/a/0/b/a0b67076efcc014c78b2023be1151c84b57c1503.png)
So while we define certain things, we also left others undefined/indeterminate in the process! However, in the context of measure theory it is common to define 
as greenturtle3141 noted below. I encourage to reread what he wrote, it's great stuff! As you may notice, though, dividing by is undefined still! Is there a place where it isn't? Kind of. To do this, we can extend the complex numbers! More formally, we can define this extension as![\[\mathbb{C}^*=\mathbb{C}\cup\{\tilde{\infty}\}\]](http://latex.artofproblemsolving.com/8/4/e/84ed3d6ab237df970333b87beaef5311caa46185.png)
which we call the Riemann Sphere (it actually forms a sphere, pretty cool right?). As a note, 
means complex infinity, since we are in the complex plane now. Here's the catch: division by is allowed here! In fact, we have![\[\frac{z}{0}=\tilde{\infty},\frac{z}{\tilde{\infty}}=0.\]](http://latex.artofproblemsolving.com/1/6/0/160cb939707708ff4e0930724df2928af11d7fd1.png)
where 
and are left undefined. We also have
Furthermore, we actually have some nice properties with multiplication that we didn't have before. In 
it holds that![\[\tilde{\infty}\times \tilde{\infty}=\tilde{\infty}\]](http://latex.artofproblemsolving.com/8/e/0/8e035b4841d20c5ad671c46355cc667ca01e533b.png)
but 
and 
are left as undefined (unless there is an explicit need to change that somehow). One could define the projectively extended reals as we did with , by defining them as![\[{\widehat {\mathbb {R} }}=\mathbb {R} \cup \{\infty \}.\]](http://latex.artofproblemsolving.com/c/0/4/c044ff37849acad3b8b280b9753539225a1276ca.png)
They behave in a similar way to the Riemann Sphere, with division by also being allowed with the same indeterminate forms (in addition to some other ones).
different icons.
are
such that 
is an integer for every positive integer 
fail: Just take 
and get 
is divisible by 
which implies 
This can only happen if is even. work: Substitute 
in place for 
in the problem; we then must prove that 
is an integer for all positive integers Call -good if satisfies this condition. Letting 
denote the number of not necessarily distinct prime factors of 
we will prove that all positive integers are -good by induction on 
The base case is trivial since if 
then 
which vacuously works. such that 
Let the prime factorization of be 
where 
are distinct primes and 
such that 
We will show that 
for all 
which finishes the inductive step by CRT.
so 
If 
then 
as well since 
Thus 
has a modular inverse modulo 
so we can say 
because is even. Hence the terms in this product for which 
contribute nothing to the binomial coefficient.
then we have 
Reindexing the product in terms of 
we get 
Therefore, plugging back into our sum gives 
By the inductive hypothesis, the sum on the right-hand side is divisible by 
so the entire sum is divisible by 
This completes our inductive step. are -good, and we are done.
" is 
.
we get 
so clearly is even. is even.
, then 
divides![\[
\sum_{i=0}^n\binom{n}{i}^k.
\]](http://latex.artofproblemsolving.com/2/9/e/29ef574279744f8e99496f7ec1a84b6b2550e5e6.png)
Proof. We proceed by induction on 
with the base case 
trivial.
. Let 
and let us work in 
. Note that if 
is even, 
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}.
\]](http://latex.artofproblemsolving.com/a/b/d/abd2cc8dc5612dffb45ca2822f622f487ef31943.png)
We prove that 
for 
by induction on with the base case 
trivial.. We have
completing the induction step.
Since 
, by the induction hypothesis with 
, 
divides![\[
\sum_{r=0}^{n'}\binom{n'}{r}^k.
\]](http://latex.artofproblemsolving.com/5/1/b/51b7c7546b7a7185c3b7be2d20aabc8debbf820f.png)
Thus![\[
\sum_{i=0}^n\binom{n}{i}^k=2\sum_{r=0}^{n'}\binom{n'}{r}^k=0,
\]](http://latex.artofproblemsolving.com/5/7/f/57f07e0144c77a1846ac0753ba534ae4571b3e30.png)
as desired. 
case is the same except there is no 
in the proof. Since all prime powers dividing 
divide 
, divides . case correctly (I wrote a Claim 2 that was basically identical to Claim 1 but modified for odd ). Also by dropping the ^k, I did not induct on in Claim 1 because the last summation (wrongly) becomes directly.
for any arbitrary 
and didn't mention CRT? (I defined p-adic notation)
? I was in a hurry...
, find all positive integers such that this expression is a positive integer”
is a power of 
and all even positive integers otherwise
doesn't work, and 
works?
. To show that odd doesn't work, just look at . divides ![\[\sum_{i=0}^n \binom ni ^{2k}.\]](http://latex.artofproblemsolving.com/8/4/1/84139da2890840ac8fcb775b99ff1949182e57f8.png)
Pick a prime dividing , and let 
so that 
is the maximal power of dividing . Let 
with 
The key claim is as follows:
, 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}}\]](http://latex.artofproblemsolving.com/6/4/e/64e09c4d93130ccbac6a28690d36d4998540b31b.png)
![\[\binom{n}{0}^2, \binom{n}{p^a}^2, \dots, \binom{n}{(mp^{e-a}-1)p^a}^2.\]](http://latex.artofproblemsolving.com/e/0/9/e0917119b3286520109182ff9ecadcfb11b0d65b.png)
We claim that these values can be blocked into consecutive groups of such that the values in each block are equal modulo 
. Specifically, for 
, we claim that ![\[\binom{n}{ip^a} \equiv \binom{n}{(i+1)p^a} \pmod {p^{e-a}}.\]](http://latex.artofproblemsolving.com/b/3/b/b3be2f22ec29244f0062d3092a9fd47bbb0416ec.png)
Indeed, we have that
But for every 
, 
since . Therefore 
, so the entire product is equal to 
; thus the subclaim is true. Therefore we have that
and the claim is proven.![\[p^{e-a} \mid \sum_{i=0}^{\left\lfloor \frac{n}{p^a}\right\rfloor} \binom{n}{ip^a}^{2k}\]](http://latex.artofproblemsolving.com/3/e/f/3ef54510be325f6a2cc9e38897d4bdfb0bb283b5.png)
for all 
. Taking 
gives that ![\[p^e \mid \sum_{i=0}^{n} \binom ni^k\]](http://latex.artofproblemsolving.com/2/6/9/2690bac952cb36989e8fa4576042c9e5bfd75a74.png)
for any prime power dividing . This means that ![\[\frac 1{n+1} \sum_{i=0}^n \binom ni^{2k}\]](http://latex.artofproblemsolving.com/9/8/9/989d213c9ec12273fc610b7739378dd28c7876be.png)
is an integer for any 
, so we are done.
(prime exponents are 1)
. Odd fail at .
and set 
. The main idea is that 
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}}\]](http://latex.artofproblemsolving.com/a/8/e/a8ee4173684952aca3735bb1a1bc63a8db2c27a8.png)
so inducting on 
works.
.
for the sum in the problem.
is necessary. Choose . We need 
, which requires to be even.
for prime , since 
. Hence 
, and this also requires to be even. This special case is instructive in figuring out the proof to follow. is sufficient. From now on we treat as fixed, and we let be a prime fully dividing . The basic idea is to reduce from to 
by an induction.
. When 
, we have ![\[ S(4) = 1^k + 4^k + 6^k + 4^k + 1^k \equiv 1 + 1 + 1 + 1 + 1 \equiv 0 \pmod 5. \]](http://latex.artofproblemsolving.com/d/4/0/d405c93989cb8c5954041c054416c6e8be3ede52.png)
When 
, the 
terms of 
in order are, modulo , 
The point is that has five copies of 
, modulo . is a prime power which fully divides . Then ![\[ \binom{n}{i} \equiv \pm \binom{\frac{n+1}{p}-1}{\left\lfloor i/p \right\rfloor} \pmod{p^e}. \]](http://latex.artofproblemsolving.com/5/b/9/5b9bf0fdf09bc4cc62ba09107a7fdfa9f1252d18.png)
Proof. [Proof of lemma] It's easiest to understand the proof by looking at the cases 
first.
, since 
, 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}. \]](http://latex.artofproblemsolving.com/7/2/4/72446f7a23991dbd82dee8b7979f07b4b2efb0aa.png)
we have 
the analogous reasoning gives 
![\[ \binom ni = \prod_{0 \le j \le i} \frac{n-(j-1)}{j} \]](http://latex.artofproblemsolving.com/4/0/2/40265f398831b8703194076e28dccc1a58c1a94f.png)
then the fractions for 
are all 
. So only considers those with 
; in that case one obtains the claimed 
exactly (even without having to take modulo ). 
is a prime power which fully divides , then ![\[ S(n) \equiv p \cdot S\left( \frac{n+1}{p}-1 \right) \pmod{p^e} \]](http://latex.artofproblemsolving.com/2/7/5/2755a27d0a39a5f9cd5bfcafde0e955c5f86f484.png)
by grouping the terms (for 
) into consecutive ranges of length (by the value of 
).
. 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.
., odd dies to ., let 
for 
, 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).\]](http://latex.artofproblemsolving.com/e/5/2/e52aea9ca81731dfbf3248ba89782270fa7606ea.png)
Now, summing this up over all 
, 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).\]](http://latex.artofproblemsolving.com/4/2/4/424f73676e5567cfa5ad7780b81ae65f72947122.png)
![\[(n+1)\mid (n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right),\]](http://latex.artofproblemsolving.com/a/b/d/abd2716339b8461b603b54a8d005136d98c6ebfa.png)
for all . However, note that since 
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).\]](http://latex.artofproblemsolving.com/4/d/3/4d3d39f943654cf05ca324b0a0c4bff928f9aafa.png)
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!},\]](http://latex.artofproblemsolving.com/8/5/7/857929600c73ec3912ace293d5641cd2d936b066.png)
which is just 
. This is clearly divisible by , proving thatfor all .
, this means that![\[(n+1)\mid \sum_{i=1}^{n}(n+1-i)\left(\binom{n}{i}^{2m}-\binom{n}{i-1}^{2m}\right),\]](http://latex.artofproblemsolving.com/6/0/f/60f1c9ed14f96c9a010c1d74f1b44ac52d72bdff.png)
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},\]](http://latex.artofproblemsolving.com/0/e/3/0e38b432759426919204494110c3382e85f4ad3c.png)
as desired. Therefore all even work, completing our proof.
. for the sum in the problem.
is necessary. Choose . We need , which requires to be even. for prime , since . Hence , and this also requires to be even. This special case is instructive in figuring out the proof to follow. is sufficient. From now on we treat as fixed, and we let be a prime fully dividing . The basic idea is to reduce from to by an induction.. When , we have When , the terms of in order are, modulo , The point is that has five copies of , modulo . is a prime power which fully divides . Then Proof. [Proof of lemma] It's easiest to understand the proof by looking at the cases first.
, since , we have we have the analogous reasoning gives then the fractions for are all . So only considers those with ; in that case one obtains the claimed exactly (even without having to take modulo ). is a prime power which fully divides , then by grouping the terms (for ) into consecutive ranges of length (by the value of ).
. When , we have When , the terms of in order are, modulo , The point is that has five copies of , modulo .
, necessity follows from setting . Henceforth assume is even. be a prime power. Then 
.
, 
. Now we induct on 
. Suppose . Then 
where 
is some integer polynomials. Raising both sides to the power of , we have 
, as desired.
, prime , and nonnegative integer ,![\[p^e\mid\sum_{i=0}^{mp^e-1}\binom{mp^e-1}i^k.\]](http://latex.artofproblemsolving.com/f/9/2/f92881a8c87422cc07fad6a1bb55f4ea8b1ccc00.png)
. If 
, this is trivial. Now suppose it holds for . Working modulo 
, 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.\]](http://latex.artofproblemsolving.com/6/e/2/6e24dd0428cac6181d17e04c34a47131832b56ac.png)
Thus by comparing coefficients, 
for 
, 
. Therefore, modulo ,![\[\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}.\]](http://latex.artofproblemsolving.com/4/1/6/416976281de08bc64838ff9bd3e1a6f892b1a9f0.png)
By the inductive hypothesis, the last sum is a multiple of , hence the first sum is a multiple of .
, then 
for any 
.
. Define 
and 
where 
and 
is maximal. Then 
.
, where 
. By maximality of , 
. Obviously 
, and we must have 
. Thus 
, all 
, and the desired follows by applying the Lemma. 
is odd is easy, so we assume is even and show the desired conclusion. ones lined up in a row. Then on step , multiply the central 
terms by 
. Obviously, we eventually construct the sequence of all binomial coefficients, and after step , the sequence will be
be the sum of the th powers of these terms after step . As a result, 
. We claim that is invariant throughout the process.
. Now define and where and is maximal. Further, let 
. By the Corollary, . Thus, we may set 
. Now
where division by was allowed because 
. Further, it is obvious that 
, so in conclusion, 
. 
is even as gives 
. Now, we show that all even work. Let .
is a prime power such that 
, then
th slot" as the fraction 
. Considering just the slots that are multiples of ,
, then the th slot is
so if the exponent is even, the slots that are not multiples of do not affect the residue mod at all, which shows the claim.
. Then, if , then by the above claim,
![$$\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}$$](http://latex.artofproblemsolving.com/e/0/e/e0e5151a5440ee3e485bf33a2fa92fd2a2253d84.png)
's in the base representation of to show that implies 
. If there is one trailing , then clearly the above implies 
. Then, if has trailing 's, then 
has 
trailing 's. Thus, if 
, then , as desired.
implies , we are done.
if is a power of and all even otherwise.
, and let 
. Notice that by definition we have 
. Since , we have 
if and 
otherwise, so for each term, either both the numerator are divisible by , or neither are. Let 
be the number of terms in the denominator that are not divisible by ., we have 
, so 
. For each term such that , we can divide out a from both the numerator and the denominator. Notice that what's left is simply 
. Thus, we conclude that ![\[\boxed{\binom ni \equiv (-1)^M \binom{\lfloor n/p \rfloor}{\lfloor i/p \rfloor}}.\]](http://latex.artofproblemsolving.com/e/0/f/e0f2a107e53c8631fd3cf1210ade103d8fd64009.png)
even works for all : For 
, we clearly have ![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (-1)^{Mk} \equiv p \equiv 0 \pmod p.\]](http://latex.artofproblemsolving.com/4/d/f/4df990e36b11b2a0f285995c194ed186b12ad2d6.png)
where 
, and suppose that 
satisfies the induction hypothesis for the prime . Clearly 
. 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}\]](http://latex.artofproblemsolving.com/5/9/4/594fb854a4626f0577e795c410495c3bd69db64b.png)
By the induction hypothesis, 
divides the inner binomial sum, so since we are multiplying it by , 
must divide 
. odd fails for 
: For , we clearly have ![\[\sum_{i=0}^n \binom ni^k \equiv \sum_{i=0}^n (-1)^{Mk} \equiv 1 \pmod p.\]](http://latex.artofproblemsolving.com/2/8/0/280473e428505c0c672beb4b3b11e6a6bd0b5af0.png)
where , and suppose that satisfies the induction hypothesis for the prime . Since 
is even, there exists one more 
than 
for each block of such that 
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}.\]](http://latex.artofproblemsolving.com/a/1/7/a178742010900bf910f7d1745ee31203de2ddfda.png)
By the induction hypothesis, does not divide this sum, so does not divide it either. odd works for a power of : Let 
. For 
, clearly odd work as 
. Now suppose odd works for 
. If we let 
, 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}}.\]](http://latex.artofproblemsolving.com/0/f/f/0fff79199fa08d23fdd0637082ce55d76826612e.png)
such that remains constant, there is exactly one odd and one even . Thus, the sum simply vanishes 
. work for all primes , it follows by CRT that all even work. For not a power of , there exists an odd prime such that , which can be easily used to show that all odd fail.
We want to find all such that 
for all positive integers 
. Clearly, letting 
, we have![\[3\mid F_k(n,i)=1^k+2^k+1^k\]](http://latex.artofproblemsolving.com/8/d/f/8dfd2f126b81d6d01b3d76c271424f11deea5584.png)
which forces to be even. is even, . Let 
. First, we prove a claim.
for all 
.
is constant given that 
is constant. Therefore,![\[F_k(n)\equiv p\sum_{i=0}^{n/p-1}f_k(n,ip)\pmod {p^a}\]](http://latex.artofproblemsolving.com/b/3/a/b3a0d05cd82fa8c799929ed4c859a749601e2e1f.png)
We now continue to our second claim.
for all 
.
. Note that if 
this simply says 
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}}\]](http://latex.artofproblemsolving.com/6/6/f/66fd05865092ffade91f1d4eb3205daea1935a3e.png)
and we have
Which completes the induction step.
![\[F_k(n)\equiv p\sum_{i=0}^{n/p-1}f_k(n,ip)\equiv pF_k(n/p)\pmod {p^a}\]](http://latex.artofproblemsolving.com/2/6/8/26831e9aa39a05983a55035269e08c68ac9027d4.png)
so if 
then 
. By induction we are done.
is odd then fails, now if is even then from CRT all we need is to prove that 
.
) and some positive integer 
such that 
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}} \]](http://latex.artofproblemsolving.com/7/8/5/7851252f0cde588fbcee11b8d01e91883dbb213d.png)
So now using this notice that we have 
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 
.
.
. To show that evens work, we will induct by taking mod 
, then CRT finishes.
.
. When 
it's obvious.
individually. Note that 
. Therefore, if 
, then both the numerator and denominator of 
are relatively prime, therefore it's 
. But since is even 
and it does nothing. So just ignore all with .
to 
we see that we multiply by 
, and this fraction is when and are relatively prime. So that eliminates all odd cases in general no matter which u picked as long as is prime (i just said n=2 because it takes less explanation). Because if it's odd then 
and it breaks but we need . and aren't relatively prime? from to make it easier because CRT duh that we picked and then it's easy to see we can use induction after shrink the binomial coefficient by on the top and bottom and aren't relatively prime, im simple minded lmao
.. Then we need 
which tells us should be even.
, then 
.. Base case is trivial.
works, let's prove 
works. Notice that 
It implies that 
Thus 
So it remains to prove that 
But still by the fact above 
And so we need to prove that 
And that is our induction hypothesis. The induction is done.
is divisible by every prime power of , it is divisible by and hence 
is an integer.
, using the fact that 
is an integer. Motivated by this observation, I tried evaluating the sum for other values of , but made no progress. Is it possible to solve the problem in this way?
, using the fact that is an integer. Motivated by this observation, I tried evaluating the sum for other values of , but made no progress. Is it possible to solve the problem in this way?
.
,or what we trying to show here :
,then applying our inductive hypothesis .
is a counterexample.
is a counterexample
.
is 
when ![\[n + 1 = {p_1}^{e_1} {p_2}^{e_2} \dots {p_m}^{e_m}\]](http://latex.artofproblemsolving.com/0/7/2/072b7b27e9b848aa52f090cae04c2e626f1e0745.png)
,![\[\sum_{i=0}^n \binom{n}{i}^k \equiv 0 \pmod{{p_j}^{e_j}}\]](http://latex.artofproblemsolving.com/4/7/b/47b249d90866951daffcc690a613580753a16d5f.png)
and let 
,
for convenience. We equivalently show that,![\[\sum_{i=0}^{cp^e - 1} \binom{cp^e - 1}{i}^k \equiv 0 \pmod{p^e} \text{ } \forall c, e \in Z^{+}, \text{ prime } p\]](http://latex.artofproblemsolving.com/e/7/0/e70b87cd706c076659737ef7894f9eb4c5eb2181.png)
.
.![\[\binom{cp - 1}{0}^k \equiv \binom{cp - 1}{1}^k \equiv \dots \equiv \binom{cp - 1}{p - 1}^k \pmod{p}\]](http://latex.artofproblemsolving.com/b/e/5/be57d1808f2d338dabf42dbd10f687a913c2875e.png)
![\[\binom{cp - 1}{p}^k \equiv \binom{cp - 1}{p + 1}^k \equiv \dots \equiv \binom{cp - 1}{2p - 1}^k \pmod{p}\]](http://latex.artofproblemsolving.com/1/2/4/12473d0589cf7ce16ae369f4cb7ad47ac840945c.png)
![\[\binom{cp - 1}{2p}^k \equiv \dots \equiv \binom{cp - 1}{3p - 1}^k \pmod{p}\]](http://latex.artofproblemsolving.com/7/5/f/75f83b068c379c7b1b74e5f4d54a4d44859a9262.png)
![\[\dots\]](http://latex.artofproblemsolving.com/1/6/7/16762e47f22f53e2431935f211fa82570b46b6cb.png)
.
,
and 
so,
![\[\iff (-m - 1)^k \equiv (m+1)^k \pmod{p}\]](http://latex.artofproblemsolving.com/d/9/0/d9081f5f4c24440ec653d2c7c12ce7aef2e0f29e.png)
when 
.![\[\binom{cp - 1}{0}^k + \binom{cp - 1}{1}^k + \dots + \binom{cp - 1}{p - 1}^k \equiv p \binom{cp - 1}{0} \equiv 0 \pmod{p}\]](http://latex.artofproblemsolving.com/6/3/9/639c1c04909eec39a20399fa49976322b126ac4f.png)
![\[\binom{cp - 1}{p}^k + \binom{cp - 1}{p + 1}^k + \dots + \binom{cp - 1}{2p - 1}^k \equiv 0 \pmod{p}\]](http://latex.artofproblemsolving.com/8/b/2/8b2b6f369c3ee0dd36ecc9779c58826468dc32d4.png)
for 
.![\[\binom{cp^e - 1}{0}^k \equiv \binom{cp^e - 1}{1}^k \equiv \dots \equiv \binom{cp^e - 1}{p - 1}^k \pmod{p^e}\]](http://latex.artofproblemsolving.com/2/9/7/29796414db0736f91d253d135ec1d575352f150e.png)
![\[\binom{c^ep - 1}{p}^k \equiv \dots \equiv \binom{cp^e - 1}{2p - 1}^k \pmod{p^e}\]](http://latex.artofproblemsolving.com/5/6/6/5663c861c24e7ea2d1ffe5be2d2eb47afc99351d.png)
is still true when ![\[\sum_{d = 0}^{c p^{e-1} - 1} \binom{c p^e - 1}{dp}^k = \frac1p \sum_{d=0}^n \binom{cp^e - 1}{d}^k \equiv 0 \pmod{p^{e-1}}\]](http://latex.artofproblemsolving.com/a/f/b/afbeb0d30087f7c107581d4a5e3b64ad4bcdd22d.png)
![\[\binom{c p^e - 1}{dp}^k \equiv \binom{c p^{e-1} - 1}{d}^k \pmod{p^{e-1}}\]](http://latex.artofproblemsolving.com/1/6/3/163e50724176a67f6cefd150406f5f99aa0d81a3.png)
.
.
.![\[\binom{c p^e - 1}{dp}^k \equiv \dots \equiv \binom{c p^e - 1}{(d+1)p - 1}^k \pmod{p^{e-1}}\]](http://latex.artofproblemsolving.com/2/7/2/272a4129b591aa0cff79714f3923cb1f21adf9d3.png)
![\[ \frac{ \binom{c p^e - 1}{(d+1)p}^k}{ \binom{c p^e - 1}{(d+1)p - 1}^k} \equiv \left( \frac{cp^e - (d+1)p}{(d+1)p} \right)^k \]](http://latex.artofproblemsolving.com/2/8/4/2842111ae65017069ea95132191affc600351a32.png)
![\[\equiv \left( \frac{cp^{e-1} - (d+1)}{d+1} \right)^k \equiv \frac{\binom{cp^{e-1}- 1}{d+1}^k}{\binom{cp^{e-1}- 1}{d}^k} \pmod{p^{e-1}}\]](http://latex.artofproblemsolving.com/0/1/4/014d5c7eda7b52d0fdeec607818f68057c55a78e.png)
we have 
as desired.![\[\sum_{d = 0}^{c p^{e-1} - 1} \binom{c p^e - 1}{dp}^k \equiv \sum_{d=0}^{c p^{e-1} - 1} \binom{cp^{e-1} - 1}{d}^k \pmod{p^{e-1}}\]](http://latex.artofproblemsolving.com/4/5/3/4531c8d747bc33161477b85a07e529ff85d873bf.png)
![\[\sum_{i=0}^n \binom{n}{i}^k \equiv 0 \pmod{n+1}\]](http://latex.artofproblemsolving.com/2/d/0/2d048f281c4a0e47cb11a4e9510a12a6827e0bb2.png)
gives the integer 
which has roots
Let
From Newton's identities,![$$s_{k} = (-1)^{k-1}k[x^{k-1}]P + \sum_{i=1}^{k-1} (-1)^is_{k-i}[x^i]P.$$](http://latex.artofproblemsolving.com/e/6/f/e6f84a3fd0237d7d5bd1db526637a8854f0fc061.png)
However, ![$[x^i]P = 0$](http://latex.artofproblemsolving.com/f/1/b/f1b8d40ace3297179d867f0694eb92cd623dbf6a.png)
for odd ![$$s_{2k} = 0 + \sum_{i=1}^{k-1} s_{2k-2i}[x^{2i}]P\equiv 0\pmod{n+1}$$](http://latex.artofproblemsolving.com/0/d/3/0d3ccf4a6aee60d9a49561e546584b99f445d255.png)
by the inductive hypothesis. Thus, all even