# Tag Archives: binomial coefficient

## A Combinatorial Identity

$(*)\qquad\qquad\qquad\displaystyle\sum_{n\ge i\ge j\ge k\ge 0}\binom ni\binom ij\binom jk=4^n$.

One way to prove it is to count the number of possible triples $(A,B,C)$ of sets with $C\subseteq B\subseteq A\subseteq S=\{1,\dots,n\}$. This can be done in two ways. First, if $A, B, C$ contain $i,j,k$ elements respectively then the number of such triples clearly equals the left-hand side of $(*)$. On the other hand, since each element of $S$ must belong to one of the four disjoint regions in the picture below

the number of such triples equals precisely $4^n$.

An algebraic proof can be obtained by repeated use of the binomial theorem:

$\displaystyle 4^n=\sum_{n\ge i\ge 0}\binom ni3^i=\sum_{n\ge i\ge j\ge 0}\binom ni\binom ij2^j=\sum_{n\ge i\ge j\ge k\ge 0}\binom ni\binom ij\binom jk$.

Similarly, one obtains the more general identity

$\displaystyle\sum_{n\ge i_m\ge\cdots\ge i_1\ge 0}\binom{n}{i_1}\binom{i_1}{i_2}\cdots\binom{i_{m-1}}{i_m}=(m+1)^n$.

This also follows from the multinomial theorem since the left-hand side equals

$\displaystyle\sum_{n\ge i_m\ge\cdots\ge i_1\ge 0}\frac{n!}{(n-i_1)!(i_1-i_2)!\cdots (i_{m-1}-i_m)!i_m!}=(m+1)^n$.

Filed under Combinatorics

## Products of Consecutive Integers Dividing One Another

I’ve been working on a project lately and I find myself stuck with the following problem.

Problem. Given positive integers $a, what can be said about the least positive integer $t$ such that $a(a+1)\cdots (a+t)$ does not divide $b(b-1)\cdots (b-t)$?

Obviously $t$ is bounded above by $b-a+1$ but this is very weak. Probably the least $t$ should be close to $b/a$.

Filed under Number Theory

## A Nice Divisibility Result on Binomial Coefficients

I just came across this cute little result on Quora and generalised it to the following.

Proposition. For any integers $0\le k\le n$,

$\displaystyle\frac{n}{(n,k)}$ divides $\displaystyle\binom{n}{k}$.

First proof. Note that

$\displaystyle \frac{k}{(n,k)}\binom nk=\frac{n}{(n,k)}\binom{n-1}{k-1}$.

Since $\displaystyle\left(\frac{n}{(n,k)},\frac{k}{(n,k)}\right)=1$, the result follows. $\square$

Second proof. Let $n=p_1^{a_1}\cdots p_r^{a_r}$ and $k=p_1^{b_1}\cdots p_r^{b_r}$ where $p_1,\dots,p_r$ are the prime factors of $nk$. For each $i$, the base $p_i$ representations of $n$ and $k$ have $a_i$ and $b_i$ trailing zeros respectively. Hence $p_i^{\max\{a_i-b_i,0\}}$ divides $\displaystyle\binom nk$, by Kummer’s theorem. Therefore

$\displaystyle k\prod_{i=1}^rp_i^{\max\{a_i-b_i,0\}}=\prod_{i=1}^rp_i^{\max\{a_i,b_i\}}=[n,k]$

divides $\displaystyle k\binom nk$. Now the result follows using $[n,k]/k=n/(n,k)$. $\square$

A nice corollary is the following property of Pascal’s triangle.

Corollary. For any integers $0,

$\displaystyle\gcd\left(n,\binom nk\right)>1$.

Using the identity

$\displaystyle\binom nk\binom kr=\binom nr\binom{n-r}{k-r}$

the argument in the first proof above can be adapted to prove the following generalisation:

Proposition. For any integers $0\le r\le k\le n$,

$\displaystyle\frac{\binom nr}{\left(\binom nr,\binom kr\right)}$ divides $\displaystyle\binom{n}{k}$.

Corollary. Any two entries $\neq 1$ in a given row of Pascal’s triangle have a common factor $>1$.

Filed under Number Theory

## Binomial Sum Modulo Prime Power: Part 2

Let $p$ be a prime number and $\omega=\exp(2\pi i/p)$. Recall that we conjectured in this post that

$(*)\qquad\qquad\qquad\displaystyle\sum_{j=0}^{p-1}(1-\omega^j)^n=p\sum_{k=0}^{\lfloor n/p\rfloor}(-1)^{kp}\binom{n}{kp}$

is divisible by $p^{\lceil n/(p-1)\rceil}$. From exercise 2 of this post we know that $(p)$ factors as $(p,\omega-1)^{p-1}$ into prime ideals in the ring $\mathbb Z[\omega]$. So $(\omega-1)^{p-1}\in (p)$. Therefore the right-hand side of $(*)$ is divisible by $p^{\lfloor n/(p-1)\rfloor}$. So we are off by at most one factor of $p$! I believe this approach can be improved upon to account for the extra factor, since we haven’t used any property of the sum.

Furthermore,

$\displaystyle\sum_{j=0}^{p-1}\omega^{-rj}(1-\omega^j)^n=p\sum_{m\equiv r\pmod p}(-1)^m\binom{n}{m}$

for any $r$. So our best result thus far is the following:

Theorem (weaker version of Fleck’s).

$\displaystyle\sum_{m\equiv r\pmod p}(-1)^m\binom{n}{m}\equiv 0\pmod{p^{\lfloor\frac{n}{p-1}\rfloor-1}}$.

Goal: Improve the floors to ceilings.

Filed under Algebra, Number Theory

## Binomial Sum Modulo Prime Power: Part 1

In the last post we showed that

$\displaystyle N_p(n)\equiv\sum_{k=1}^{\lfloor n/p\rfloor}(-1)^k\binom{n}{pk}\pmod p$

and then we used Lucas’ theorem to evaluate the sum modulo $p$.

My initial attempt at evaluating the sum was to note that

$(*)\qquad\qquad\qquad\displaystyle\sum_{j=0}^{p-1}(1-\omega^j)^n=p\sum_{k=0}^{\lfloor n/p\rfloor}(-1)^{kp}\binom{n}{kp}$

where $\omega=\exp(2\pi i/p)$, but then I was stuck. Numerical examples suggested that this sum is in fact divisible by $p^{\lceil n/(p-1)\rceil}$, but I could not think of a way of extending the argument from the last post. Nonetheless, some extensive google search recently revealed that

Theorem (Fleck, 1913). For any $j$,

$\displaystyle\sum_{m\equiv j\pmod p}(-1)^m\binom{n}{m}\equiv 0\pmod{p^{\left\lfloor \frac{n-1}{p-1}\right\rfloor}}$.

So taking $j=0$ gives the desired claim after noting that

Fact. $\displaystyle \left\lfloor\frac{n-1}{p-1}\right\rfloor+1=\left\lceil\frac{n}{p-1}\right\rceil$.

Proof. Write $n=q(p-1)+r$ with $0\le r. If $r=0$ then the equation is just $q-1+1=q$, and if $r>0$ then it is $q+1=q+1$. $\square$

This article contains a proof of Fleck’s result using the identity $(*)$. Unfortunately I don’t have a good grasp of the theory behind it.