View topic - E 16 • Art of Problem Solving

EDIT: An edited and extended (Theorem 1 generalized even further, Theorem 5 extended and proved anew) version of the below solution can be found here:
http://projectpen.files.wordpress.com/2 ... en-e16.pdf
or here:
http://www.cip.ifi.lmu.de/~grinberg/pene16.pdf

Peter wrote:

Prove that for any prime $p$ in the interval $\left]n, \frac {4n}{3}\right]$ , $p$ divides
$\sum^{n}_{j = 0}{{n}\choose{j}}^{4}.$

Nice and instructive problem. Let's generalize:

Theorem 1. If $n$ and $k$ are positive integers and $p$ is a prime such that $\frac {2k - 1}{2k}\left(p - 1\right) < n < p$ , then $p\mid\sum_{j = 0}^{n}\binom{n}{j}^{2k}$ .

Before we prove this, we first show some basic facts about binomial coefficients and remainders modulo primes.

Definition. The binomial coefficient $\binom{x}{u}$ is defined for all reals $x$ and for all integers $u$ as follows: $\binom{x}{u} = \frac {x\cdot\left(x - 1\right)\cdot ...\cdot\left(x - u + 1\right)}{u!}$ if $u$ is a positive integer, $\binom{x}{0} = 1$ , and $\binom{x}{u} = 0$ if $u$ is a negative integer.

Theorem 2, the upper negation identity. If $n$ is a real, and $r$ is an integer, then $\binom{ - n}{r} = \left( - 1\right)^{r}\binom{n + r - 1}{r}$ .

Proof of Theorem 2. We will only consider the case of $r$ being positive (the other cases are trivial). Then, using the definition of binomial coefficients,

$\binom{ - n}{r} = \frac {\left( - n\right)\cdot\left( - n - 1\right)\cdot ...\cdot\left( - n - r + 1\right)}{r!} = \left( - 1...$
$= \left( - 1\right)^{r}\cdot\frac {\left(n + r - 1\right)\cdot ...\cdot\left(n + 1\right)\cdot n}{r!} = \left( - 1\right)^{r}...$ .

This proves Theorem 2.

Theorem 3. If $p$ is a prime, if $u$ and $v$ are two integers such that $u\equiv v\mod p$ , and if $k$ is an integer such that $k < p$ , then $\binom{u}{k}\equiv\binom{v}{k}\mod p$ .

Proof of Theorem 3. If $k\leq 0$ , then $\binom{u}{k} = \binom{v}{k}$ , so that Theorem 3 is trivial. Thus, it remains to consider the case $k > 0$ only. In this case, $k!$ is coprime with $p$ (since $k! = 1\cdot 2\cdot ...\cdot k$ , and all numbers $1$ , $2$ , ..., $k$ are coprime with $p$ , since $p$ is a prime and $k < p$ ).

Now, $u\equiv v\mod p$ yields

$k!\cdot\binom{u}{k} = k!\cdot\frac {u\cdot\left(u - 1\right)\cdot ...\cdot\left(u - k + 1\right)}{k!} = u\cdot\left(u - 1\rig...$
$\equiv v\cdot\left(v - 1\right)\cdot ...\cdot\left(v - k + 1\right) = k!\cdot\frac {v\cdot\left(v - 1\right)\cdot ...\cdot\le...$
$= k!\cdot\binom{v}{k}\mod p$ .

Since $k!$ is coprime with $p$ , we can divide this congruence by $k!$ , and thus we get $\binom{u}{k}\equiv\binom{v}{k}\mod p$ . Hence, Theorem 3 is proven.

Finally, a basic property of binomial coefficients:

Theorem 4. For every nonnegative integer $n$ and any integer $k$ , we have $\binom{n}{k} = \binom{n}{n - k}$ .

This is known, but it is important not to forget the condition that $n$ is nonnegative (it is necessary!).

Now to something completely different:

Theorem 5. If $p$ is a prime, and $f$ is a polynomial of degree $< p - 1$ whose coefficients are all integers, then $\sum_{j = 0}^{p - 1}f\left(j\right)\equiv 0\mod p$ .

Proof of Theorem 5. Since $f$ is a polynomial of degree $< p - 1$ whose coefficients are all integers, it can be written in the form $f\left(X\right) = \sum_{i = 0}^{p - 2}f_{i}X^{i}$ with $f_{i}$ being an integer (not necessarily nonzero) for every $i\in\left\{0;\;1;\;...;\;p - 3;\;p - 2\right\}$ .

Hence,

$\sum_{j = 0}^{p - 1}f\left(j\right) = \sum_{j = 0}^{p - 1}\sum_{i = 0}^{p - 2}f_{i}j^{i} = \sum_{i = 0}^{p - 2}f_{i}\cdot\sum...$ .

But for every $i\in\left\{0;\;1;\;...;\;p - 3;\;p - 2\right\}$ , we have $\sum_{j = 0}^{p - 1}j^{i}\equiv 0\mod p$ (in fact, for $i = 0$ , this is clear since $\sum_{j = 0}^{p - 1}j^{0} = \sum_{j = 0}^{p - 1}1 = p$ , and for $i\geq 1$ , this is equivalent to $\sum_{j = 1}^{p}j^{i}\equiv 0\mod p$ (since $\sum_{j = 0}^{p - 1}j^{i}\equiv \sum_{j = 1}^{p}j^{i}\mod p$ , because $0^{i}\equiv p^{i}\mod p$ ), what follows from http://www.problem-solving.be/pen/viewtopic.php?t=676 part a) because $p - 1\nmid i$ ). Thus,

$\sum_{j = 0}^{p - 1}f\left(j\right) = \sum_{i = 0}^{p - 2}f_{i}\cdot\sum_{j = 0}^{p - 1}j^{i}\equiv\sum_{i = 0}^{p - 2}f_{i}\...$ ,

and Theorem 5 is proven.

Proof of Theorem 1. We have $p - n - 1\geq 0$ , since $n < p$ yields $n + 1\leq p$ .

Also, $\frac {2k - 1}{2k}\left(p - 1\right) < n$ yields $\left(2k - 1\right)\left(p - 1\right) < 2kn$ , so that $2k\left(p - 1\right) - \left(p - 1\right) < 2kn$ , thus $2k\left(p - 1\right) - 2kn < p - 1$ , or, equivalently, $2k\left(p - n - 1\right) < p - 1$ .

We have to prove that $p\mid\sum_{j = 0}^{n}\binom{n}{j}^{2k}$ . This rewrites as $\sum_{j = 0}^{n}\binom{n}{j}^{2k}\equiv 0\mod p$ . This is equivalent to $\sum_{j = 0}^{p - 1}\binom{n}{j}^{2k}\equiv 0\mod p$ (in fact, since $n < p$ , the two sums $\sum_{j = 0}^{p - 1}\binom{n}{j}^{2k}$ and $\sum_{j = 0}^{n}\binom{n}{j}^{2k}$ differ only in some terms $\binom{n}{j}^{2k}$ with indices $j$ in the interval $\left]n;\;p - 1\right]$ , and these terms are zero, so we have $\sum_{j = 0}^{p - 1}\binom{n}{j}^{2k} = \sum_{j = 0}^{n}\binom{n}{j}^{2k}$ ).

For every integer $j$ with $0\leq j < p$ , we have

$\binom{n}{j} = \binom{ - \left( - n\right)}{j} = \left( - 1\right)^{j}\binom{\left( - n\right) + j - 1}{j}$ (after Theorem 2)
$\equiv\left( - 1\right)^{j}\binom{p - n + j - 1}{j}$ (by Theorem 3, since $\left( - n\right) + j - 1\equiv p - n + j - 1\mod p$ and $j < p$ )
$= \left( - 1\right)^{j}\binom{p - n + j - 1}{\left(p - n + j - 1\right) - j}$ (by Theorem 4, since $p - n + j - 1$ is nonnegative, since $p - n - 1\geq 0$ and $j\geq 0$ )
$= \left( - 1\right)^{j}\binom{p - n + j - 1}{p - n - 1}\mod p$ ,

so that

$\binom{n}{j}^{2k}\equiv\left(\left( - 1\right)^{j}\binom{p - n + j - 1}{p - n - 1}\right)^{2k} = \binom{p - n + j - 1}{p - n ...$ (since $2k$ is even).

Therefore,

(1) $\left(p - n - 1\right)!^{2k}\cdot\sum_{j = 0}^{p - 1}\binom{n}{j}^{2k}\equiv\left(p - n - 1\right)!^{2k}\cdot\sum_{j = 0}^{p ...$
$= \sum_{j = 0}^{p - 1}\left(\left(p - n - 1\right)!\cdot\binom{p - n + j - 1}{p - n - 1}\right)^{2k}$
$= \sum_{j = 0}^{p - 1}\left(\left(p - n - 1\right)!\cdot\frac {\prod_{u = 0}^{\left(p - n - 1\right) - 1}\left(\left(p - n + ...$
$= \sum_{j = 0}^{p - 1}\left(\prod_{u = 0}^{\left(p - n - 1\right) - 1}\left(\left(p - n + j - 1\right) - u\right)\right)^{2k}...$ .

Now,

$\prod_{u = 0}^{\left(p - n - 1\right) - 1}\left(\left(p - n + X - 1\right) - u\right)$

is a polynomial of the variable $X$ whose degree is $p - n - 1$ . Thus,

$\left(\prod_{u = 0}^{\left(p - n - 1\right) - 1}\left(\left(p - n + X - 1\right) - u\right)\right)^{2k}$

is a polynomial of the variable $X$ whose degree is $2k\left(p - n - 1\right)$ . Since $2k\left(p - n - 1\right) < p - 1$ , it is therefore a polynomial of degree $< p - 1$ . Since the coefficients of this polynomial are all integers, Theorem 5 thus yields

$\sum_{j = 0}^{p - 1}\left(\prod_{u = 0}^{\left(p - n - 1\right) - 1}\left(\left(p - n + j - 1\right) - u\right)\right)^{2k}\e...$ .

Using (1), this becomes

$\left(p - n - 1\right)!^{2k}\cdot\sum_{j = 0}^{p - 1}\binom{n}{j}^{2k}\equiv 0\mod p$ .

Now, $\left(p - n - 1\right)!$ is coprime with $p$ (since $\left(p - n - 1\right)! = 1\cdot 2\cdot ...\cdot\left(p - n - 1\right)$ , and all numbers $1$ , $2$ , ..., $p - n - 1$ are coprime with $p$ because $p$ is a prime and $p - n - 1 < p$ ). Hence, we can divide this congruence by $\left(p - n - 1\right)!^{2k}$ , and obtain $\sum_{j = 0}^{p - 1}\binom{n}{j}^{2k}\equiv 0\mod p$ . As we said, this proves Theorem 1.

Darij

E 16

Login