Tag Archives: binomial coefficient

A Combinatorial Identity

While tutoring today a student asked me about the following 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.

Leave a comment

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<b, 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.

Leave a comment

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<k<n,

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

Leave a comment

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.


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

Leave a comment

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<p-1. 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.


Filed under Number Theory