# Difference between revisions of "Pascal's Triangle2"

Pascal's Triangle
Field: Algebra
Image Created By: The Math Forum @ Drexel

Pascal's Triangle

Pascal's Triangle

# Basic Description

Pascal's triangle is a triangular arrangement of certain numbers that show interesting patterns. We start out with 1 on the top row, which we will label as row 0. Every entry from the next row is the sum of the two numbers above it. If a number is absent on the diagonal left or the right, replace that empty entry with 0 and find the sum. We can repeat this process endlessly.

Image 1

For instance, let's look at a row $1, 4, 6, 4, 1$. This row can be seen as $0, 1, 4, 6, 4, 1, 0$. We can find the entries for the next row by following the method above. The next row will be $0+1=1, 1+4=5, 4+6=10, 4+1=5, 1+0=1$.

Pascal's triangle was first introduced in Pascal's paper Treatise on the Arithmetic Triangle published posthumously in 1665. In his original paper, the the triangle was rotated 45° so that each entry is the sum of the two preceding entries on the horizontal row and the vertical column, as shown in Image 1.

# A More Mathematical Explanation

### Constructing Pascal's Triangle

There is a mathematical rule to constructing Pascal's triangle. [...]

### Constructing Pascal's Triangle

There is a mathematical rule to constructing Pascal's triangle. This general rule is not necessary for the readers' understanding of the following sections, but it is helpful for the readers' understanding of the proofs of certain sections.

Let ${\color{Gray}\alpha}$ be a sequence ${\color{Gray}a_0, a_1, \dots, a_n}$ for some ${\color{Gray}n=0, 1, 2}$ Then we can

Let $\alpha$ be a sequence $a_0, a_1, \dots, a_n$ for some $n=0, 1, 2, \dots$. Then we can generate a new sequence $b_0, b_1, \dots, b_n, b_{n+1}$ that is in Pascal's relations with the original sequence according to the following rule:

Eq. (1)        $\begin{cases} b_0=a_0\\ b_k=a_{k-1}+a_k \quad (1\leq k \leq n)\\ b_{k+1}=a_k \end{cases}$

as shown in Image 2.

Image 2

For instance, if we have a sequence $1, 2, 1$, we can produce a new sequence by following the rule above and get the sequence $1, 3, 3, 1$.

Now, we can construct Pascal's triangle starting from a sequence that consists of one term, 1. We can use Pascal's relations to generate further sequences and place these new sequence below the original sequence.

Before we proceed, we will define the terms rows and places that are used in Pascal's Triangle. The rows proceed as row 0, row 1, row 2, ..., as we start from the top. Places are given to each entry starting from the first number after 1, from the left to the right. 6, for example, would be identified as row 4, place 3.

We will use the notation:

${T_m}^n$

for the entry that is on the $n$th row and $m$th place.

### Patterns within Pascal's Triangle

#### Hockey Stick Pattern

Image 2

When we look at Pascal's triangle, we can find figures that look like hockey sticks as we start from any 1 in the triangle. The handle of the hockey stick, or the numbers shown inside colored loops in Image 2, should start from any 1 in the border. The head of the hockey stick, or the colored cell in Image 2, should not be aligned in the same direction as the handle, and all numbers in the hockey stick should be on different rows of the Pascal's triangle.

An interesting fact about the hockey stick figures is that the sum of all the numbers in the handle is equal to the number that is at the head of the hockey stick. For instance, let's look at the blue hockey stick. When we add the numbers positioned at a straight line, we get :

$1+3+6=10$,

which is the number that is at the head of the same hockey stick. We can prove this property using mathematical induction.

Let ${\color{Gray}{X_m}^n}$ denote for the ${\color{Gray}n}$th row and the ${\color{Gray}m}$th entry

Let ${X_m}^n$denote for the entry in the $n$th row and $m$th column. We want to prove that

${X_m}^n={X_0}^{n-1}+{X_1}^{n-1}+\dots+{X_m}^{n-1}$

First, we show the base case that the assertion works for when $m=0$. In other words, we want to show that:

${X_0}^n={X_0}^{n-1}$.

Because ${X_0}^n={X_0}^{n-1}=1$, we have shown the base case.

Next, we will show that if the assertion holds true for $m=k$, then it also holds true for $m=k+1$. Because every number in the triangle is a sum of the numbers to its left and top, we know that

${X_{k+1}}^n={X_k}^n+{X_{k+1}}^{n-1}$
$={X_0}^{n-1}+{X_1}^{n-1}+\dots{X_k}^{n-1} +{X_{k+1}}^{n-1}$.

The assertion is true for $m=k+1$ when it is true for $m=k$, and we have proved the first property. The second property can also be proved in a similar way.

#### Horizontal Sum

We can add the numbers in each row horizontally. We can see that the sum of entries in each row is twice the sum of entries in the previous row. In fact, the sum of all entries on the $n$th row is $2^n$.

Let the sequence ${\color{Gray}a_0, a_1, a_2, \dots, a_n}$ be a sequence of any row in the Pascal's triangle, and let

Let the sequence $a_0, a_1, a_2, \dots, a_n$ be a sequence of any row in the Pascal's triangle, and let $b_0, b_1, b_2, \dots, b_n, b_{n+1}$ be a sequence of the row right below the original sequence.

Then the sum of the entries of the sequence $b_0, b_1, b_2, \dots, b_n, b_{n+1}$ can be written as:

$b_0+b_1+b_2+\dots+b_n+b_{n+1}$
$=a_0+(a_0+a_1)+(a_1+a_2)+\dots+(a_{n-1}+a_n)+a_n$
$=2a_0+2a_1+2a_2+\dots+2a_{n-1}+2a_n$
$=2(a_0+a_1+a_2+\dots+a_n)$

Thus, the sum of entries of any row is twice the sum of the entries in the previous row. In fact, the sum of entries for each row is :

$\rm {row} \quad 0=1=2^0$
$\rm{row} \quad 1=1*2=2=2^1$
$\rm{row} \quad 2=2*2=4=2^2$
$\rm{row} \quad 3=4*2=8=2^3$
$\dots$
$\rm{row} \quad n=2^n$

#### Other Patterns and Properties

• The triangle is symmetrical. The numbers on the left side of the triangle have identical numbers on the right side. In other words, the $k$th number from the left at any row $n$ is the same as the $k$th number from the right at the same row; thus, ${T_k}^n=T_{n-k}^n$. For instance, look at the 5th row. 10, which is the 3rd from the left, is also 3rd from the right in the 5th row.
• The triangle is bordered by 1's on the right and left edges.
• The next line of numbers in diagonal order after the edge numbers are natural numbers $1, 2, 3, 4, 5, \dots$
• The next set of numbers inwards after the natural numbers are that continues as $1, 3, 6, 10, 15, 21,\dots$
• After the triangular numbers we have that continue as $1, 4, 10, 20, 35, \dots$.
• The next d-diagonal contains the next higher dimensional "d-simplex" numbers.
• The first number after 1 in each row divides all the other numbers in that row if and only if it is prime.

#### Animation Demonstrating Patterns

The Flash animation below allows you to explore some of the patterns present in Pascal's Triangle:

### Applications of Pascal's Triangle

Image

We can use Pascal's triangle to find the probability of having a certain outcome of tossing coins.

For example, if we toss a coin twice, we could have the any of the following results: Head-Head once, Tail-Head twice and Tail-Tail once. (Here, we do not differentiate the coins. Thus, Tail-Head and Head-Tail are considered the same combination.) The number of each possible outcome is 1, 2, 1, which is also the same as the second row of Pascal's triangle.

In general, if we toss a coin $x$ times, the number of each possible outcome is the same as the horizontal entries in the $x$th row of the Pascal's triangle.

Image

What is the probability of getting exactly 2 heads with 3 coin tosses?

To answer this, we could use Pascal's triangle. Adding the entries of the third row of Pascal's triangle, we get $1+3+3+1=8$ possible outcomes. Therefore we have 8 possible outcomes. 3 of the possible 8 outcomes give exactly 2 heads, therefore the probility of getting exactly 2 heads from 3 coin tosses is $3/8=37.5%$.

#### Binomial Coefficients in Pascal's Triangle

Pascal's triangle can be used to determine in binomial expansions. For example, when we consider the expansion of $(x+y)^n$ for $n=0, 1, 2, 3, \dots,$ we get:

$(x+y)^0=1$
$(x+y)^1=x+y$
$(x+y)^2=x^2+2xy+y^2$
$(x+y)^3=x^3+3x^2y+3xy^2+y^3$
$\dots$.

Notice that the coefficients in the expansion are the entries in the $n$th row in Pascal's triangle. In general, we can use binomial coefficients to describe the coefficient of the expansion as :

$(x+y)^n={n \choose 0}x^n+{n \choose 1}x^{n-1}y+{n \choose 2}x^{n-2}y^2+ \dots + {n \choose k}x^{n-k}y^k+ \dots + {n \choose {n-1}}xy^{n-1}+{n \choose n}y^n$.

This is called the binomial theorem. Indeed, the binomial coefficient ${n \choose k}$ is the entry of the $n$ row and $k$th place in Pascal's triangle, and we can find the value by:

${n \choose k}=\frac{n!}{k!{(n-k)}!}$

We know that

${\color{Gray}(x+y)^n={n \choose 0}x^n+{n \choose 1}x^{n-1}y+ \dots + {n \choose k}x^{n-k}y^k+ \dots + {n \choose {n-1}}xy^{n-1}+{n \choose n}y^n}$.

Now, let's consider the expansion of ${\color{Gray}(x+y)^{n+1}}$.

This can be written as :

We know that

$(x+y)^n={n \choose 0}x^n+{n \choose 1}x^{n-1}y+ \dots + {n \choose k}x^{n-k}y^k+ \dots + {n \choose {n-1}}xy^{n-1}+{n \choose n}y^n$.

Now, let's consider the expansion of $(x+y)^{n+1}$.

$(x+y)^{n+1}$ can be written as :

Eq. (2)        $(x+y)^{n+1}=(x+y)^n(x+y)$

We can find the binomial expansion of $(x+y)^{n+1}$ by expanding the right side and left side of Eq. (2), and the expansion of either side of the equation must give the same result.

Expanding the left side of Eq. (2), we get:

$(x+y)^{n+1}={n+1 \choose 0}x^{n+1}+{n+1 \choose 1}x^ny+ \dots +{n+1 \choose k}x^{n+1-k}y^k+\dots+{n+1 \choose n}xy^n+{n+1 \choose n+1}y^{n+1}$

Expanding the right side of Eq. (2), we get:

$(x+y)^n(x+y)=\Bigg( {n \choose 0}x^n+{n \choose 1}x^{n-1}y+ \dots + {n \choose k}x^{n-k}y^k+ \dots + {n \choose {n-1}}xy^{n-1}+{n \choose n}y^n\Bigg) (x+y)\,$
$={n \choose 0}x^{n+1}+{n \choose 0}x^ny+{n \choose 1}x^ny+{n \choose 1}x^{n-1}y^2+\dots+{n \choose k}x^{n+1-k}y^k+{n \choose k}x^{n-k}y^{k+1}+\dots +{n \choose n-1}x^2y^{n-1}+{n \choose n-1}xy^n+ {n \choose n}xy^n +{n \choose n}y^{n+1}$

The left side expansion and right side expansion must be the same. Thus, the coefficients for terms with same powers of $x$ and $y$ must also be the same. Thus,

$\begin{cases} \displaystyle {n+1 \choose 0}={n \choose 0}\\ \displaystyle {n+1 \choose k}={n \choose k-1} +{n \choose k} \quad (1 \leq k \leq n )\\ \displaystyle {n+1 \choose n+1}={n \choose n} \end{cases}$

This is the same form as Pascal's relations in Eq. (1). We can see that the sequence of coefficients of the expansion of $(x+y)^{n+1}$ is in Pascal's relations with the sequence of coefficients of the expansion of $(x+y)^n$. The very first sequence for $n=0$ is :

${0 \choose 0}=1$,

which is the sequence in the $0$th row of Pascal's triangle. Thus, all other sequences of coefficients of binomial expansion also coincide with the entries of Pascal's triangle.

#### Combinations in Pascal's Triangle

Let $S$ be a set of $n$ elements. Then, we can find a subset of $S$ that contains $k$ different elements. This subset is called a k-combination. The number of k-combination of an $n$ element set is equal to the number of $n$ things taken $k$ at a time. This number is denoted by $C_{(n,k)}$, ${C_k}^n$, or ${}_nC_k$, and is equal to the binomial coefficient:

${n \choose k}=\frac{n!}{k!{(n-k)}!}$

Thus, we can find the number of k-combinations from Pascal's triangle.

# Why It's Interesting

In addition to its application in algebra, combination, probability theory, and other areas of mathematics, Pascal's triangle has been intriguing mathematicians because of the patterns that can be seen in the triangle. The Fibonacci sequence and Sierpenski triangle are two of the many patterns that can be found in Pascal's triangle.

#### Fibonacci Sequence

Image 4

The Fibonacci sequence is the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... where the first two numbers are 1s and every later number is the sum of the two previous numbers. The Fibonacci numbers can also be found in Pascal's triangle by adding the entries of diagonals as shown in image 4. You can try this at animation demonstrating patterns.

An easier way to show the Fibonacci numbers is to list the numbers on the diagonals on a triangular arrangement. Then, we get Image 5, and adding all the numbers in the same row gives the Fibonacci Sequence.

Image 5

#### Sierpinski Triangle

If we are to color the odd and even numbers in Pascal's triangle with two distinct colors, we would observe an interesting recursive pattern seen in the Sierpinski triangle.

We can construct a Sierpinski triangle according to the following rule :

(1) Draw an equilateral triangle, as shown in the first step of Image 6.

(2) Then, connect the midpoints of each side of the triangle and remove the triangle in the center, as shown in step 2 of Image 6.

(3) For the remaining three black triangles, repeat step 2.

(4) Repeat step 2 for any remaining triangles.

In fact, if we repeat this process until the number of rows in the triangle approaches infinity, we get Sierpinski's triangle. You could try this out in the animation and see what happens.

## References

Hockey stick pattern http://ptri1.tripod.com/
Triangular numbers http://www.mathsisfun.com/numberpatterns.html#triangular
Tetrahedral numbers http://www.mathsisfun.com/tetrahedral-number.html
Horizontal sum http://www.mathsisfun.com/pascals-triangle.html
Fibonacci sequence http://mathforum.org/dr.math/faq/faq.pascal.triangle.html
Sierpenski Triangle http://en.wikipedia.org/wiki/Pascal's_triangle http://en.wikipedia.org/wiki/Combination