Show that any two elements (both greater than one) drawn from the same row of Pascal's triangle have greatest common divisor (gcd) greater than one. For example, the greatest common divisor of 28 and 70 is 14.
Each element in Pascal's triangle is obtained by adding the two elements diagonally above. (With suitable boundary conditions; see below.)
The binomial coefficient may be defined as the number of ways of choosing k outcomes out of n possibilities, ignoring order.
We prove the well known result that row n of Pascal's triangle comprises the sequence of binomial coefficients: , , ... ,
row 0: 1 row 1: 1 1 row 2: 1 2 1 row 3: 1 3 3 1 row 4: 1 4 6 4 1 row 5: 1 5 10 10 5 1 row 6: 1 6 15 20 15 6 1 row 7: 1 7 21 35 35 21 7 1 row 8: 1 8 28 56 70 56 28 8 1
To establish this result we first note that, for 1 k n, the following recurrence relation holds:
This follows from a simple direct counting, or combinatorial, argument.
How many ways can we choose a committee of k students from a class of n students? We count in two different ways:
Recurrence relation (1) follows. This relation is equivalent to the method of constructing Pascal's triangle by adding two adjacent numbers and writing the sum directly underneath.
With suitable initial conditions ( = 1 and = 0 for n < k), it is now easy to prove by mathematical induction that Pascal's triangle comprises binomial coefficients.
We show that, for 0 m k n,
Again we make use of a combinatorial argument. In a class of n students, how many ways can we choose a committee of k students that contains a subcommittee of m students? Counting in two different ways:
Identity (2) follows.
We show that, for 0 < m k < n, gcd ( , ) > 1.
Suppose, to the contrary, that and are relatively prime.
By identity (2), divides
Since and are relatively prime, it follows that divides
But this is impossible, as, by combinatorial considerations, >
We conclude that and are not relatively prime; that is, any two elements (both greater than one) drawn from the same row of Pascal's triangle have greatest common divisor greater than one.
This result was first proved by Erdös and Szekeres in 1978.