Pascal's Triangle, Polynomials, and Vector Programs

The formula

The left-hand side is known as the "product" or "generating" form. The right-hand side is the "additive" or "expanded" form. We can also write the right-hand side as a "power series" (or "Taylor series") expansion: (because if ).

If we let , we obtain a new representation of the number of subsets of an -element set:

In fact, by varying , we can discover new identities. For example, if , we get

Equivalently, we can say

In other words, the number of even-sized subsets of an -element set is the same as the number of odd-sized subsets.

There are many other identities that can be established in this way. For example, we could try complex roots of unity, and so on.

Combinatorial Proofs

Proofs that work by manipulating algebraic forms are called "algebraic" arguments. Proofs that form a bijection are called "combinatorial" arguments.

For example, let be the set of binary strings of length with an odd number of ones, and let be the set of binary strings of length with an even number of ones. Earlier, we gave an algebraic proof that . A combinatorial proof must construct a bijection between and .

Here is one way to try to establish such a correspondence. Let be the function that takes an -bit string and flips all its bits. The function is clearly a bijection function for odd .

For example, in we have:

The first instance starts with an odd number of 1's and, after applying the function, ends with an even number of 1's. The second instance starts with an even number of 1's and ends with an odd number of 1's.

But does it work in the even case? In we have:

In this case, it doesn't work. Complementing maps evens to evens and odds to odds!

Let's try another correspondence. Let be the function that takes an -bit string and flips only the first bit.

For example, in we have:

In , we have:

Using this correspondence, we can provide a combinatorial proof that .

Binomial Coefficients

The binomial coefficients, , have many representations, which lead to numerous fundamental mathematical identities.

Consider the following sequence of results:

Note that the coefficients by themselves create an intriguing pattern. This array of numbers is known as Pascal's triangle. The row of the triangle consists of the coefficients of :

            1
          1   1
        1   2   1
      1   3   3   1
    1   4   6   4   1

We can develop an inductive definition of the entry of the row as follows:

In effect, each number in the table, except for the first and last numbers in a row, is the sum of the two neighboring numbers in the preceding row.

Pascal's triangle, which is named for French mathematician Blaise Pascal (1623-1662), has a long and distinguished history. It was discovered and used independently by Indian, Persian, and Chinese mathematicians, working hundreds of years before Pascal was born.

The Indian mathematician Brahmagupta (598-670) is credited with the invention of the concept of zero. He defined zero as the result of subtracting a number from itself and gave some of its properties. In his 628 work, “The Opening of the Universe,” he also introduced methods for computing square roots, solving linear and some quadratic equations, and rules for summing series. The text includes evidence of his familiarity with binomial coefficients. There is evidence that Brahmagupta’s was known and possibly influential in Baghdad and elsewhere in the Middle East two centuries later.

One of the earliest known constructions of what looks like Pascal's triangle appears in the work of the mathematician al-Karaji (953–1029), who lived in Baghdad. Al-Karaji’s main contribution was to free algebra completely from geometrical operations and replace them with the arithmetic of the types of operations we know today to operate on unknowns. He was first to define the monomials and , and to give rules for products of any two of these, defining the product of these terms without any reference to geometry. He used a form of mathematical induction in some of his arguments, worked with binomial coefficients, and provided rules for the construction of Pascal’s triangle.

Around 1050, the Chinese mathematician Chia Hsien (Jia Xian) (1010–1070) demonstrated an understanding of Pascal’s triangle, for calculating binomial coefficients and using it in the context of extracting square and cube roots of numbers. At about the same time, the Persian astronomer, mathematician, and poet Omar Khayyam (1048–1131) used Pascal’s triangle for a similar purpose. Chu Shih-Chieh (Zhu Shijiei) (1260–1320) depicted Pascal’s triangle in his 1303 book “Precious Mirror of the Four Elements” and indicated its use for providing coefficients of the binomial expansion of .

Pascal’s triangle was probably known in Europe by 1529, but it was rediscovered by Pascal in 1654. He was the first mathematician to give clear and complete demonstrations of its basic properties, making the first explicit use of mathematical induction along the way. Pascal is said to have written, “It is extraordinary how fertile in properties the triangle is. Everyone can try his hand.”

Pascal's Triangle

By closely examining the numbers in Pascal's triangle, we can identify patterns and establish a variety of identities.

For example, suppose that we sum the rows.

Notice that we get the powers of 2, again establishing the identity .

Suppose that we sum the odd terms of the 7^th row. In this case, we get . When we sum the even terms of the row, we get . In general, for the row, the sum of the odd terms equals the sum of the even terms.

Summing along the "Avenues"

Summing numbers along the diagonal called "first avenue" (shown below), we obtain another interesting set of numbers.

We see, for example, that , one of the triangle numbers (see chapter 2). This can be expressed as the identity which simplifies to , the familiar formula for triangle numbers as the sum of consecutive integers.

If we were to sum on the avenue, we get

For example, for , we obtain

Pascal meets Fibonacci

Another remarkable set of numbers emerges when we add together numbers along a somewhat different diagonal.

The sums along these "shallow diagonals" produce the Fibonacci numbers: In general, we get the identity

relating the binomial coefficients and the Fibonacci numbers.

Summing and Squaring in Pascal's Triangle

Suppose that we add the squares of the numbers in a row, starting with the third row: for the third row, or for the fourth row. Notice that the sum of squares of rows of Pascal's triangle give us the central term in a subsequent row: indeed, is the central term of the fifth row, and is the central term of the seventh row. In general, this seems to suggest the identity for any :

While this identity, as with all identities in this chapter, can be proved inductively, we will give a "walking" proof later in the chapter.

One can go even further, and obtain a formula for the sum of squares of the first n positive integers. To begin, for each row , consider the sum of the term in the first avenue and twice the term in the second avenue: we get . Now we can apply this relationship to get a formula for the sum of squares.

This technique above, where we sum over on both sides, is due to al-Karaji.

Walking Proofs

All the properties demonstrated in the previous section can be proved inductively and algebraically. We will give combinatorial proofs using the Manhattan block-walking representation of binomial coefficients.

The city of Manhattan is laid out in a grid pattern, with consecutively number streets (running roughly east and west) and avenues (running north and south). Consider the ways in which a person can traverse the blocks in the Manhattan-based map shown below, starting at the top left corner, where streets are horizontal and avenues are vertical.

The person begins at the spot marked A (0, 0) and moves along the network, making a choice at each intersection to go along an avenue or a street. We label each intersection in the network with a pair of numbers (j, k), where j indicates the street number and k the avenue number. The gray path given in the diagram above shows a possible route from corner A (0, 0) to corner B (5, 5), traversing a total of 10 blocks. Altogether, there are possible routes that are all equally short from A to B.

In general, there are or shortest routes from (0, 0) to (j, k).

Similarly, in treating Pascal’s triangle as a network with levels and avenues (diagonals), there are shortest routes from (0, 0) to (n – k, k). So, we end up with a block-walking model for binomial coefficients.

We can use this model to obtain an alternate proof of the fundamental identity

At the end of a route from the start to corner (n, k), a block walker arrives at (n, k) from either corner (n – 1, k) or corner (n – 1, k – 1). Thus, the number of routes from (0, 0) to corner (n, k) equals the number of routes from (0, 0) to (n – 1, k) plus the number of routes from (0, 0) to (n – 1, k – 1).

For example, to get to corner (6, 3), a person goes to corner (5, 3) and branches left to (6, 3) or goes to corner (5, 2) and branches right to (6, 3). There are 10 ways to get to corner (5, 3) and 10 ways to get to corner (5, 2). Hence there are 20 ways to get to corner (6, 3).

In general, the advantage of block-walking proofs is that we can draw pictures of the “proof.” The picture shows all the routes to a certain corner—this amount is the right-hand-side of the identity—can be decomposed in terms of all the routes to certain intermediate corners (or blocks)—the sum on the right-hand side of the identity.

Exercise

1. Use a block-walking argument to show that
2. Without using the results of #1, use a block-walking argument to show that

Note that by convention: and if or .

We can also use block-walking arguments to prove the following identity:

Corollary :

Similarly, we can provide a block-walking argument for the al-Karaji summation of squares formula (see previous section).

Vector Programs

Now we can look at a link between a simple programming language and Pascal’s triangle.

We define a (parallel) programming language called VECTOR that operates on possibly infinite vectors of numbers. Each variable can be thought of as: . For example, we can have .

Let stand for a scalar constant. So, stands for the vector , , and .

means to add the vectors position-wise. .

means to shift every number in ; one position to the right and to place a 0 in position 0.

Example

Suppose that we have the following program:

Loop n times:
      

As we loop through the program we get the following sequence of results:

As we loop through the program for the time, row of Pascal’s triangle. This indicates that vector programs can be implemented by polynomials.

The vector is represented by the polynomial:

which is described as a formal power series.

So, is represented by . is represented by , is represented by , and is represented by .

Example

We can now reinterpret the vector program given above for generating the row of Pascal’s triangle in terms of polynomials.

Loop n times:
      

Looping through times, we get .

This leads us back to our definition of a geometric series (see chapter x):

, and the infinite geometric series:

.

We can express a geometric series in linear form as follows:

,

and in quadratic form as

.

Suppose that we multiply out the expression to get a single, infinite polynomial What is the expression for ?

To find , we need to compute . We have

Hence, if , then . If , then .

For the geometric series in quadratic form, we can say that

or when .