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

screenshot-2016-10-03-21

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.

Advertisements

Leave a comment

Filed under Combinatorics

Jordan-Hölder theorem

I am cramming for my algebra comprehensive exam so I will probably be posting stuff like this for a while.

A chain of subgroups \{e\}=H_0\triangleleft H_1\triangleleft\cdots\triangleleft H_n=G of a finite group G with H_{i+1}/H_i simple for all i is called a composition series of G. (The H_{i+1}/H_i are called composition factors.) The theorem in question states that every group has a composition series, and the composition factors in any two such series are unique up to reordering.

We can easily prove the first part of the theorem, that any finite group has a composition series, using the extreme principle. Let n\ge 0 be the largest integer for which there is a chain \{e\}=H_0\triangleleft H_1\triangleleft\cdots\triangleleft H_n=G of subgroups. (Such an n exists because there is trivially a chain with n=1, and our group is finite.) We claim that the composition factors in this case are simple. If not, WLOG H_{i+1}/H_i has a non-trivial normal subgroup \widetilde N. By correspondence, \widetilde N=N/H_i for some H_i\triangleleft N\triangleleft H_{i+1}. But then

\{e\}=H_0\triangleleft H_1\triangleleft\cdots\triangleleft H_i\triangleleft N\triangleleft H_{i+1}\cdots\triangleleft H_n=G

is a longer chain, a contradiction.

While the proof of the general theorem requires some non-trivial group theory (e.g. see here), we can easily prove the theorem for finite abelian groups using elementary number theory. For such a group, the orders of the composition factors must exactly be the prime factors—listed with multiplicity—of the order of the group. So the result follows immediately from the fundamental theorem of arithmetic.

Leave a comment

Filed under Algebra, Number theory

A new AM-GM inequality

I recently found the following inequalities useful:

\displaystyle \left(x+\frac{a_1+\cdots+a_n}{n}\right)^n\ge (x+a_1)\cdots(x+a_n)\ge \left(x+\sqrt[n]{a_1\cdots a_n}\right)^n,

for any x,a_1,\dots,a_n\ge 0.

To prove the left half simply apply AM-GM to the product

\displaystyle (x+a_1)\cdots (x+a_n)\le \left(\frac{(x+a_1)+\cdots+(x+a_n)}{n}\right)^n.

The right half follows directly from Hölder’s inequality.

More generally, one has

\displaystyle\left(\frac{a_1+\cdots+a_n}{n}+\frac{b_1+\cdots+b_n}{n}\right)^n\ge (a_1+b_1)\cdots(a_n+b_n)\\\ge \left(\sqrt[n]{a_1\cdots a_n}+\sqrt[n]{b_1\cdots b_n}\right)^n

for a_1,\dots,a_n,b_1,\dots,b_n\ge 0. The proof goes similarly.

One obtains similar inequalities for any number of vectors a,b,c,\dots.


As an example, for a_i=i we get the inequalities

\displaystyle \left(x+\frac{n+1}{2}\right)^n\ge (x+1)\cdots (x+n)>\left(x+\frac ne\right)^n

using the fact that \sqrt[n]{n!}/n\to 1/e from above.

Leave a comment

Filed under Algebra

Hilbert’s nullstellensatz

Leaving it here because I want to study this at some point.

What's new

I had occasion recently to look up the proof of Hilbert’s nullstellensatz, which I haven’t studied since cramming for my algebra qualifying exam as a graduate student. I was a little unsatisfied with the proofs I was able to locate – they were fairly abstract and used a certain amount of algebraic machinery, which I was terribly rusty on – so, as an exercise, I tried to find a more computational proof that avoided as much abstract machinery as possible. I found a proof which used only the extended Euclidean algorithm and high school algebra, together with an induction on dimension and the obvious observation that any non-zero polynomial of one variable on an algebraically closed field has at least one non-root. It probably isn’t new (in particular, it might be related to the standard model-theoretic proof of the nullstellensatz, with the Euclidean algorithm and high school algebra taking…

View original post 3,546 more words

Leave a comment

Filed under Algebra

Midy’s theorem

Let b have order d modulo p. Then the base b expansion of 1/p has period L=(b^d-1)/p of length d. To see this, note that if b^d-1=mp, then

\displaystyle\frac 1p=\frac{m}{b^d-1}=\frac{m}{b^d}+\frac{m}{b^{2d}}+\frac{m}{b^{3d}}+\cdots.

Note also that aL<b^d for any 1\le a\le p-1. Hence a/p has period aL. Now suppose that d is even. Since b has order d modulo p, it follows that b^{d/2}\equiv -1\pmod p. Hence p-a\equiv b^{d/2}a\pmod p. This means that at their midpoints the two numbers aL and (p-a)L are mirror images of one another. This means that splitting aL midway into two equal parts and adding them gives b^{d/2}-1, i.e., a string of (b-1)‘s in base b. This is known as Midy’s theorem.

For example, with p=7 and b=10 we get d=6, and L=142857. Split L into two equal parts 142 and 857, adding which gives

142+857=999.

In general, if m is any divisor of d, then

\begin{aligned} b^d-1&=(b^m-1)(1+b^{d/m}+b^{2d/m}+\cdots+b^{(m-1)d/m})\\&\equiv 0\pmod p\end{aligned}

so

b^{d/m}+b^{2d/m}+\cdots+b^{(m-1)d/m}\equiv -1\pmod p

and so splitting L into m equal parts and adding them will always give a multiple of b^{d/m}-1.

Leave a comment

Filed under Number theory