Making Mathematics: Pascal’s Triangle Results

Results for the Patterns in Pascal’s Triangle Problem

Solutions to the Warm-up Problems

See Pascal’s Triangle at http://www2.edc.org/makingmath/mathtools/pascal/pascal.asp for a range of possible discoveries.
Each step removes¹/₉ and leaves ⁸/₉ of the remaining black area. After n steps, the original square will be (⁸/₉)ⁿ black. As this process is continued for ever larger n, the square will get ever closer to being 0% black. Surprisingly, this does not mean that the whole figure will be black. There will still remain a set of black points (of measure zero). Where are they? Think of the points that are removed at each step (the interior of each square and not its boundary).
See the modular arithmetic resources for the solutions to their problems.
See the results section of the trains project.
Answers for a) , b), and c) are the same as rows 0 through 4 of Pascal’s triangle.

d) f(n, k) = f(n – 1, k – 1) + f(n – 1, k)

Proof that f(n,k) obeys the sum rule

Since 0! = 1, f(n, n) = and f(n, 0) = both simplify to 1. Thus, f(n, k) satisfies the same properties as Pascal(n, k).

e) For , we are choosing a subset of size k from our set of size n. Arbitrarily pick one element of the set, e. Each of our k-element subsets either contains e or does not. So,

= the number of subsets containing e +

the number of subsets that do not contain e

If a subset contains e, we still have to pick k – 1 elements from the remaining n – 1 elements of the set (). If a subset does not contain e, we have to pick k elements from the remaining n – 1 elements (). Therefore, .

asks for all subsets containing all elements of a set and there is only one way to do that (take the whole set). Likewise, asks for all subsets containing no elements of a set and there is only one way to do that (use the empty set). So satisfies the same properties as Pascal(n, k) and f(n, k).

This last proof demonstrates that the arithmetic (add the two numbers above) and combinatorial (the elements come from ) ways of defining Pascal’s triangle are consistent. These two proofs show that the value of the kth number in the nth row of Pascal’s triangle (with our counts starting at the 0th value in row 0) matches the values from the factorial and combinations formulas.

Main Results

Because of the many different ways of deriving Pascal’s triangle, there are many ways to prove discoveries about it. The following results take different approaches to proving related findings. Each representation provides insights that combine to give us a rich picture of the patterns in the triangle.

Thinking about Pascal mod 2 geometrically and arithmetically (some answers to project question #3):

Although the mod 2 Pascal’s triangle is often compared to Sierpinski’s gasket, it differs in one important respect: Pascal’s triangle is discrete. Because of this lack of continuity, the self-similar scalings are imprecise. For example, the central 0 in the red triangle in the figure below corresponds with the triangle of six 0’s in the blue triangle and the triangle of twenty-eight 0’s in the center of the figure. These two scalings do not maintain a consistent ratio (although the ratio does tend toward 4, consistent with a scaling factor of 2). Nonetheless, the figure does display a variant of self-similarity as we look at ever-larger portions. It is self-similarity based on translation! Each element has the same parity as that of the element rows earlier (for the largest possible).

Pascal’s Triangle mod 2 with highlighted matching regions

Theorem: For the mod 2 Pascal’s triangle, each new block of rows from row through row –1 has exactly two copies of the first rows (rows 0 through –1) with a triangle of 0’s in between.

Proof: We will prove the claim inductively. We will add the additional claim that row –1 is composed entirely of 1’s (odds). We have the base case in row 1, which is two copies of row 0. The row numbers 0 and 1 are both of the form–1 and both rows contain only 1’s.

Let’s now show that if our claims are true for n, they must also be true for n + 1. If true for n, then row – 1 is composed entirely of 1’s. That means that row will have 1’s on the ends and – 1 0’s in between. This stretch of 0’s will shrink by one 0 per row until they are gone in row + – 1 = – 1. The two terminal 1’s in row – 1 will each start the pattern that the 1 in row 0 starts. These two copies, initially separated by – 1 spaces, will grow until the separating 0’s are gone in row – 1. That is, they will have grown, without interference, for rows and each reproduced the original rows. Since row – 1 had 1’s, row – 1 will have + = 1’s. Thus we have shown that both claims, the duplication of the prior set of rows and the presence of all 1’s necessary to establish the conditions for a new round of duplicating, are satisfied. Q.E.D.

Describing the pattern of odds (a first answer to the number of odds in row 100):

Although the above ideas may follow an exploration of project question # 1, it is easier to prove observations about the patterns of odds following work on question #3.

The geometric duplication process suggests a related method for counting the number of odds in each row. If S is the sequence of the number of odds in the rows of Pascal’s triangle, we can get S from the following procedure: S₀ = 1, S_n = S_n – 1 & (2^. S_n – 1). Which means: to get the next sequence, take the last sequence and follow it (“&” means catenate) with all of the last sequence’s elements doubled:

S₀ = {1}

S₁ = {1} & 2^.{1} = {1, 2}

S₂ = {1, 2} & 2^.{1, 2} = {1, 2, 2, 4}

S₃ = {1, 2, 2, 4} & 2^.{1, 2, 2, 4} = {1, 2, 2, 4, 2, 4, 4, 8}

This doubling and appending corresponds to the translating and copying of the geometric description above. If we keep generating S_n, we find that getting row 100 is not so labor intensive. S_n has elements, so the 101st element in S is in S₇. The following commands entered into a Texas Instruments TI-83 calculator take care of the labor:

Start with S₀:	{1} L1	L1 is a list variable.
Build S₁:	augment(L1, 2*L1) L1	Augment catenates two lists.
Build S₁ through S₇.	Press ENTER six times.	ENTER repeats the recursive rule.
To get row 100:	L1(101)	This is the 101st element in L1.

And the 101st element is 8, so there are 8 odds in row 100.

This recursive approach is pretty quick, but what if our calculator batteries are dead? Is there a more direct way to find the value in terms of the row number itself?

Explicitly predicting the pattern for any line:

When a problem involves patterns of doubling or trebling, thinking in terms of base 2 or base 3 representations can lead to insights. The table below, produced by a Making Mathematics teacher compares the number of ones in a row’s base 2 representation with the number of odds in that row.

n	n in base 2	# of 1’s (in base 2)	Number of odds in row n
0	0	0	2⁰ = 1
1	1	1	2¹ = 2
2	10	1	2¹ = 2
3	11	2	2² = 4
4	100	1	2¹ = 2
5	101	2	2² = 4
6	110	2	2² = 4
7	111	3	2³ = 8
8	1000	1	2¹ = 2

Why does this pattern seem to work? One explanation comes from the self-similarity rule and the doubling procedure for S. These imply the following:

Let f(n) be the number of odd entries in line n of Pascal’s triangle, then .

This function is equivalent to moving up the triangle by the highest power of 2 possible (to the line that we duplicated to make line n). For example f(27) = 2 f(27 – 16) = 2 f(11). But what is f(11)? Well, reapplying the formula yields f(11) = 2 f(11 – 8) = 2 f(3). Continuing, we get f(3) = 2 f(3 – 2) = 2 f(1) and f(1) = 2 f(1 – 1) = 2 f(0) and f(0) = 1. Putting that recursive sequence altogether gives f(27) = 2⁴. Each of the factors of two was contributed when we subtracted the highest power of two possible and these are each represented by a 1 in the base 2 representation of 27 (27₁₀ = 11011₂). In general, iterative application of the above formula will lead to f(0) after as many recursions as the number of 1’s in n’s base two representation. This rule corresponds nicely with the 1, 2, 2, 4 pattern because the rightmost digits of the counting numbers in base 2 cycle through 00, 01, 10, and 11 (and lead us to think about the fractal nature of counting in any base).

An algebraic finding:

Here is an excerpt from one Pascal explorer’s report:

“I have been using the factorial formula to prove that the scaling patterns in Pascal always work. I was able to show that the parity of matches that of . However, that scaling leaves lots of gaps. If we know the first four rows or Pascal, doubling all of the coordinates just gives us the parity of the even entries in rows 6 and 8 (for example, is odd, so must be, too). I then moved on to proving the parity of the elements that neighbor those that have even row and column numbers when I discovered what I think is a strange little observation. I was trying to prove: If = 0 then = 0. Here is what I found:

Meg’s Little Observation Theorem: Odd and even numbers can appear in Pascal’s triangle for three of the four cases of odd and even row and column numbers. However, when the row is even and the column is odd, the entry is always even.

Proof:

Case 1: row is odd, column is odd. Proof by example: = 5 and = 10 (so we can get an odd or even result).

Case 2: row is odd, column is even. Proof by example: = 10 and = 5.

Case 3: row is even, column is even. Proof by example: = 15 and = 28.

Case 4: row is even, column is odd. The even row is 2r and the odd column is 2c-1.

We know that this entire expression is an integer. Since the denominator of the final factor consists of all odd terms, the initial factor of 2 remains and the result is even. Q.E.D.

My question is why?! What is special about these combinations that they must be even? Interestingly, the pattern of alternating zeroes in every other line had not caught my eye because of the stronger triangular patterns (see the picture below).”

Pascal's triangle with even-row, odd-column cells colored

The above result is summarized in the table below.

Possible remainders for cells mod 2

Possible remainders for different mod 2

Variations also arise with 3 as the modulus (see below). These two tables hint at a number of possible generalizations. Are these generalizations valid? Are they limited to moduli that are prime?

possible remainders for cells mod 3

Possible remainders for different mod 3

Thinking about Pascal mod p arithmetically (some answers to project question #4):

There are eight odd numbers in the 100th row of Pascal’s triangle, 89 numbers that are divisible by 3, and 96 numbers that are divisible by 5.

Of course, one way to get these answers is to write out the 100th row, of Pascal’s triangle, divide by 2, 3, or 5, and count (this is the basic idea behind the geometric approach).

But let’s see if we can find a more efficient (and elegant) way to get our answers. In an attempt to show how one might actually come up with interesting results, what follows is a collage of various arithmetic approaches that we’ve seen over the years in our work with students and teachers.

We want to count the number of elements in a row of Pascal’s triangle that are (or are not) divisible by some integer. Divisibility by a prime is easier to deal with, so let’s look at that case. The question, then, is

Given a non-negative integer n and a prime p, which numbers are divisible by p?

Well, sometimes a more pointed question is easier to answer:

Given a non-negative integer n and a prime p, what is the highest power of p that divides ?

This “highest power of p” function is useful in many contexts, and it’s sometimes denoted by ord_p, so, for example:

ord₅(40)	= 1 (20 = 5¹ ^. 2³)
ord₂(40)	= 3
ord₇(40)	= 0
ord₇(5⁸ ^. 3⁴ ^. 5 ^. 7² ^. 11⁵)	= 2

To get ord_p(n), factor n into primes and look at the power of p that shows up. That’s ord_p(n). You can check that ord_p has the property that, for non-negative integers m and n,

ordp(mn) = ordp(m) + ordp(n)

And, if n is a factor of m,

( ) ordp m- = ordp(m) - ordp(n) n

So, our question becomes

Given a non-negative integer n and a prime p, what’s an easy way to calculate ord_p?

In particular, we want to know when

(( )) n ordp > 0 k

because this is when p is a factor of

. Of course, what we really want to do is to count all the entries in the nth row of Pascal that have ord_p > 0, but let’s worry about that later.

Well, there’s an explicit formula for in terms of factorials:

( ) n ----n!------ k = k! .(n - k)!

So, using the properties of ord (the ord of a quotient is the difference of the ords, and the ord of a product is the sum of the ords), we have

ord_p	= ord_p
	= ord_p(n!) - ord_p(k!) - ord_p

It seems like a next step might be to find a way to find the ord of a factorial. A numerical example points the way: let’s calculate ord₃(139!). So, we want to find the highest power of 3 that divides

1 .2 .3 .4 .....137 .138 .139

Each multiple of 3 give us at least one “contribution”:

3,6,9,12,15,...

This stops at the last multiple of 3 before 139 (that is, at 138), and there are about

numbers in the list. In fact, there are exactly

|_ _| 139- = 46 3

where

means the “integer part” of 46

(that is, the integer part of

Of course, we’ve missed some “extra” multiples of 3: every multiple of 9 (that is, 9, 18, 27... ) counts twice, and there are

|_ _| 139- 9 = 15

of these. But, we’ve now missed the extra multiples of 3 that come from multiples of 27, and there are

|_ _| 139- = 5 27

of these. You get the idea. Next, we need to count the multiples of 81 (to get the extra factor that comes from 3⁴), and there are

|_ _| 139- = 1 81

of these (namely, 81 itself). If we didn’t know any better, we could count the multiples of 243 that are less than 139, and there’d be

|_ _| 139 ---- = 0 243

of these. And everything would be 0 from here on. So, the power of 3 that divides 139! is

ord3(139!) = 46 + 15 + 5 + 1 = 67

Remember where this came from. Summarizing our calculations, we could say:

|_ _| |_ _| _ | _| _ | _| _ | _| _ | _| |_ _| ord (139!) = 139- + 139- + 139- + 139- + 139-+ 139- + 139- +... 3 3 32 33 34 35 36 37

Of course, after awhile (in fact, after 3⁴), all these “floors” are 0. So, we have a method for finding ord_p(n!):

Proposition 1. If n is a non-negative integer and p is a prime, then

|_ _| |_ _| |_ _| |_ _| |_ _| |_ _| |_ _| ordp(n!) = n- + -n- + n-- + n-- + -n- + n-- + n-- + ... p p2 p3 p4 p5 p6 p7

This is unsatisfying in many ways. For one, it doesn’t tell you when the terms of the sum drop off to zero. For that, you’d have to write n in base p. But wait—if you write n in base p, the whole sum in the proposition gets easier. Here’s how:

Let’s go back to our example if 139 and 3. First, let’s write 139 as a base-3 expansion:

139 = (1 .1) + (1 .3) + (0 .32) + (2 .33) + (1 .34)

So,

1393 = 12011

Then, to get ord₃(139!), we use the proposition and calculate as follows:

=

= (1 ^. 1) + (0 ^. 3) + (2 ^. 3²) + (1 ^. 3³)

=

= (0 ^. 1) + (2 ^. 3) + (1 ^. 3²)

=

= (2 ^. 1) + (1 ^. 3)

=

= (1 ^. 1)

And everything is 0 after this. Wow, look at this. Look at the rightmost equations. One thing we could do is to read down instead of across; that would allow us to add “like” powers of 3. And, just like when you read across, when you read down you see the base-3 digits of 139, first all except the “units” 1, then all except the 11, then all but the 011, and finally all but the 2011. Will this always happen? Let’s see. Suppose

n = n0 + n1p + n2p2 + ...+ nsps

Then

	= ( n ₀ ^. ) + ( n₁ ^. 1) + ( n₂ ^. p ) + ( n₃ ^. p² ) + + ( n_s ^. p^{s - 1} )
	= ( n₁ ^. 1) + ( n₂ ^. p ) + ( n₃ ^. p² ) + + ( n_s ^. p^s - 1 )

and

	= ( n₀ ^. ) + ( n₁ ^. ) + ( n₂ ^. 1) + ( n₃ ^. p ) + + ( n_s ^. p^{s - 2} )
	= (n₂ ^. 1) + (n₃ ^. p) + + (n_s ^. p^s-2)

And, more generally,

	= (n₀ ^. ) + (n₁ ^. ) + (n₂ ^. ) + (n₃ ^. ) + + (n_s ^. p^s-k)

	= (n_k ^. 1) + (n_k+1 ^. p) + + (n_s ^. p^s-k)

But

|_ n _| |_ n _| |_ n _| |_ n _| |_ n _| |_ n _| |_ n _| ordp(n!) = -- + --2 + -3- + -4- + -5- + -6- + -7- + ... p p p p p p p

So let’s write this all out and see if we can use the “add down” trick:

	= (n₁ ^. 1) + (n₂ ^. p) + (n₃ ^. p²) + (n₄ ^. p³) + + (n_s ^. p^s-1)
	= (n₂ ^. 1) + (n₃ ^. p) + (n₄ ^. p²) + (n₅ ^. p³) + (n_s ^. p^s-2)
	= (n₃ ^. 1) + (n₄ ^. p) + (n₅ ^. p²) + + (n_s ^. p^s-3)

	= (n_s ^. 1)

If we add down, we get the “clipped” sum of the base-p digits of n. Let’s invent a notation for this: Let

_p(n) be the sum of the base-p digits of n. Then adding down, we have

ord_p(n!)	= (_p(n) - n₀) ^. 1 + (_p(n) - n₀ - n₁) ^. p + (_p(n) - n₀ - n₁ - n₂) ^. p²+
	(_p(n) - n₀ - n₁ - n₂ - n₃) ^. p³ + + (_p(n) - n₀ - n₁ - n₂ - - n_s-1) ^. p^s-1+
	(_p(n) - n₀ - n₁ - n₂ - - n_s) ^. p^s

The last line is 0, but we put it in to keep the pattern going. Time for some algebraic fooling around. Gather the

_p(n)s, the n₀s, the n₁s, and so on:

ord_p(n!)	= _p(n)
	- n₀
	- n₁
	- n₂

	- n_s

Each sum is a geometric series, just begging to be summed:

ord_p(n!)	= _p(n)
	- n₀
	- n₁
	- n₂

	- n_s

Factor out the denominator of p - 1 and rearrange what’s left:

ord_p(n!)	=

Oh, how nice: since

n₀ + n₁ + + n_s	= _p(n) and
n₀ + n₁p + n₂p² + + n_sp^s	= n

this simplifies to

n---sp(n)- p - 1

Let’s state it as a result:

Proposition 2. If n is a non-negative integer and p is a prime,

n---sp(n)- ordp(n!) = p - 1

where

_p(n) is the sum of the digits in the base-p expansion of n.

We can apply this formula to our example and, again, get 67:

139 - s (139) 134 ord3(139!) = -------3------= ----= 67. 3 - 1 2

ord_p	= ord_p

	= ord_p(n!) - ord_p(k!) - ord_p

	= n - _p(n) - - p - 1

	= _p(k) + _p(n - k) - _p(n)p - 1

This is pretty interesting. Let’s state it as a result:

Proposition 3. If n is a non-negative integer and p is a prime,

(( )) n sp(k) +-sp(n---k)---sp(n)- ordp k = p- 1

where

_p(n) is the sum of the digits in the base-p expansion of n.

Notice that what we really care about is which have non-zero ords. But it turns out that one can get the exact value of the expression in proposition 3 with very little extra work (we know this because we worked it out before we wrote up these results). The fact that

(( )) n sp(k) +-sp(n---k)---sp(n)- ordp k = p- 1

is one of those strange results that contains a surprise: We know that ord_p

is a non-negative integer, so p - 1 must be a factor of

_p(k) +

_p(n - k) -

_p(n)—that’s not at all obvious. And shouldn’t the digit sum of n equal the digit sum of k plus the digit sum of n - k? After all, k and n - k add up to n, so shouldn’t the sum of the digits work the same way? Let’s see what happens with an example:

Let’s look at ord₃:

Well, according to the proposition, we need to look at the digit sum (base 3) of 139, 32, and 139 - 32 = 107. We have

139 = (1 ^. 1) + (1 ^. 3) + (0 ^. 3²) + (2 ^. 3³) + (1 ^. 3⁴)

32 = (2 ^. 1) + (1 ^. 3) + (0 ^. 3²) + (1 ^. 3³) + (0 ^. 3⁴)

107 = (2 ^. 1) + (2 ^. 3) + (2 ^. 3²) + (0 ^. 3³) + (1 ^. 3⁴)

So,

139₃ = 12011

32₃ = 01012

107₃ = 10222

So,

₃(139) = 5

₃(32) = 4

₃(107) = 7

and proposition 3 says that

(( )) ord3 139 = 7 +-4---5-= 6-= 3 32 3 - 1 2

And sure enough,

	= 29794458700044250140618567735660
	= 2² ^. 3³ ^. 5¹ ^. 11² ^. 17¹ ^. 19¹ ^. 23¹ ^. 37¹ ^. 41¹ ^. 43¹ ^. 59¹ ^. 61¹ ^.
	67¹ ^. 109¹^. 113¹ ^. 127¹ ^. 131¹ ^. 137¹ ^. 139¹

So, why is

₃(32) +

₃(107) -

₃(139) not 0? If we look at the traditional way we add base-3 numbers (or numbers in any base), we see where the discrepancy shows up. Here’s how you’d add 32 to 107 to get 139 in base 3:

		1	1	1
	0	1	0	1	2
+	1	0	2	2	2

	1	2	0	1	1

So, what disturbs the digit sums are the “carries;” that’s why

s3(32) + s3(107) /= s3(139)

Notice that each carry gets multiplied by 3 when it jumps into the next column. For example, looking at the rightmost column, the 2 + 2 is 11, so the carried 1 is really 1 ^. 3 (or 10 in base 3). Let’s look at the general situation:

Suppose we are looking at . We write n, k, and n - k in base p:

n = n₀ + n₁p + n₂p² + + n_sp^s

k = k₀ + k₁p + k₂p² + + k_sp^s

n - k = m₀ + m₁p + m₂p² + + m_sp^s

And suppose the carries are denoted by _i:

d ... d d s-1 1 0 ms ... m2 m1 m0 -+----ks---...--k2---n1---k0---- ns ... n2 n1 n0

Well, by the way this algorithm works,

m₀ + k₀	= n₀ + p₀
m₁ + k₁ + ₀	= n₁ + p₁
m₂ + k₂ + ₁	= n₂ + p₂

m_s + k_s + _s-1	= n_s

Then

m₀ + k₀ - n₀	= p₀
m₁ + k₁ - n₁	= p₁ - ₀
m₂ + k₂ - ₀	= p₂ - ₁

m_s + k_s - n_s	= -_s-1

Add down:

(m₀ + m₁ + m₂ + + m_s) + (k₀ + m₁ + k₂ + + k_s) - (n₀ + n₁ + n₂ + + n_s)	=
(p - 1)(₀ + ₁ + ₂ + + _s)

sp(n- k) + sp(k)- sp(n) = (p- 1)(d0 + d1 + d2 + ...+ ds)

There’s the factor of p - 1. Dividing by it, and combining the result with the result of proposition 3, we have “Kummer’s carry theorem:”

Theorem 1. If n is a non-negative integer and p is a prime,

(( )) n ordp k

is the number of carries you get when k and n - k are added in base p.

Let’s go back to the original question:

Given a non-negative integer n and a prime p, for how many k is ord_p

> 0 ?

In light of theorem 1, this is the same question as:

Given a non-negative integer n and a prime p, for how many k is there a carry when k and n - k are added in base p? Instead of answering this, we found it easier to figure out when there’s not a carry. And from here, we can subtract (from n + 1) to get the desired answer.

An example will help. Suppose p = 5 and, n = 133866, so, in base 5, n is

How can two numbers add to this with no carries? Reading from right to left, there are two choices for the first digit—0 and 1. If k “ends” in 0, n - k ends in 1 and vice-versa. For the “fives” place, there are 4 choices for k—it could have a 0, 1, 2, or 3 in the 5’s place (and n - k would have, respectively, a 3, 2, 1, or 0 in the same place). And so it goes. Here’s a summary of what can happen:

place	digit in n	number of choices for digits for k
1	1	2—namely, {0,1}
5	3	4—namely, {0,1,2,3}
5²	4	5—namely, {0,1,2,3,4}
5³	0	1—namely, {0}
5⁴	4	5—namely, {0,1,2,3,4}
5⁵	2	3—namely, {0,1,2}
5⁶	3	4—namely, {0,1,2,3 }
5⁷	1	2—namely, {0,1}

In general, we have the answer to our question:

Theorem 2. The number of entries in the nth row of Pascal’s triangle that are not divisible by a prime p can be determined as follows:

Write n in base p: $n = n0 + n1p + n2p2 + ...+ nsps$
The number in question is $prod s (1 + nk) = (1 + n0)(1 + n1)(1 + n2) ...(1 + ns) k=0$

So, for example, suppose p = 2. Then, looking at 100 in base 2:

100 = (1 .26) + (1 .25) + (0 .24) + (0 .23) + (1 .22) + (0 .21) + (0 .20)

1002 = 1100100

Add 1 to each digit and multiply the answers together:

(1 + 1)(1 + 1)(0 + 1)(0 + 1)(1 + 1)(0 + 1)(0 + 1) = 8

and 8 numbers in the 100th row are not divisible by 2 (that is, are odd). Try it for 3:

100 = (1 .34) + (0 .33) + (2 .32) + (0 .31) + (1 .30)

1003 = 10201

and the number of entries in the 100th row that are not divisible by 3 is

(1 + 1)(0 + 1)(2 + 1)(0 + 1)(1 + 1) = 12

But there are 101 entries in the 100th row, so
101 - 12 = 89 are divisible by 3.

Theorem 1 is due to Ernst Kummer (1810-1893), a mathematician who laid the groundwork for some of the mathematics that led to the proof of Fermat’s Last theorem. Indeed, knowing the power of a prime that divides any particular entry of Pascal’s triangle turns out to be an essential tool in that proof, and more generally, in all of number theory, so this project connects to some frontline mathematics.

See Pascal Triangle’s Math Behavior at http://ecademy.agnesscott.edu/~lriddle/ifs/siertri/pascal.htm for further discussion of the geometric and number theoretic connections in Pascal’s Triangle.

Results for some Extension Problems

1) Through row 2^n-1 – 1, we have 3^n-1odds (this claim comes from the geometric and arithmetic argument presented above that shows each pattern being copied twice in subsequent rows). Up through row r, the number of values overall is

This expression is the familiar formula for triangular numbers. So through row , the number of values in the triangle is

We can rewrite this expression as

Therefore, the portion of odds in the triangle through row 2^n-1 – 1 is

Since this last expression goes to 0 as d gets larger and it is an upper bound for the portion of numbers in the triangle that are odd, the odds represent 0% of the triangle! This surprising result seems counterintuitive as we look at all of the odd entries and consider that odds appear in every single row. However, no matter how small a percent we choose, the percent of odds will eventually sink below that target.

2) For a discussion of Pascal’s triangle with composite moduli, see Arithmetic Properties of Binomial Coefficients at http://www.math.uga.edu/~andrew/Binomial. See also Granville, Andrew (1992). Zaphod Beeblebrox’s brain and the fifty-ninth row of Pascal’s triangle. American Mathematical Monthly, 99: 318-331 and Granville, Andrew (1997). Corrigendum. American Mathematical Monthly, 104: 848-851.

3) See the Teaching Notes for a discussion.

4) Have fun!