Posts Tagged ‘Pascal’s Triangle’

Star of David Theorem

December 21, 2008

star-of-davidHanukkah starts today at sundown, so in honor of the holiday here is the Star of David Theorem.  In simplest terms, this theorem says that the greatest common divisor of  {{n-1} \choose k}, {n \choose {k-1}}, and {{n+1} \choose {k+1}} is equal to the greatest common divisor of  {{n-1} \choose {k-1}}, {n \choose {k+1}}, and {{n+1} \choose k}.  To see why it’s called the Star of David, look at the following visual.  the greatest common divisor of the blue corners and the greatest common divisor of the purple corners are equal.  Together, the two triangles form the Star of David.

star-of-david

For example, if n=4 and k=2, this says that the greatest common divisor of  {3 \choose 2}, {4 \choose 1}, and {5 \choose 3} is equal to the greatest common divisor of  {3 \choose 1}, {4\choose 3}, and {5 \choose 2}.  As it turns out, this is one of the less interesting examples because both sides simplify to gcd(3,4,10), which is 1.  So let’s look for another example.

Where there are binomial coefficients, Pascal’s triangle can’t be too far behind.  Sadly, when the above Theorem is placed visually into Pascal’s triangle, it ends up looking kind of turned and squooshed.

pascal-star-1Visually, the top star illustrates the previous not-so-interesting example of how gcd(3,4,10) is equal to gcd(3,4,10).  But the lower star illustrates that that gcd(36,210,165) is equal to gcd(84,45,330), and this is a little less obvious.  In this second case, but greatest common divisors are equal to 3.

According to Wolfram’s Mathworld, the Star of David Theorem was first stated by H. W. Gould in 1972, and there were several generalization in the years immediately following.  Apprently the association with Pascal’s triangle wasn’t noticed until 6 years ago, however, by B. Butterworth in this article (which is originally about using Pascal’s triangle to illustrate the song “The Twelve Days of Christmas”).

Advertisements