Extending Pascal's triangle beyond its starting point.
Have you heard of Pascal’s Triangle? If so, you’ll know that it can only be
extended in a single direction: downward. However, we can use pyramids,
factorials, and limits to extend Pascal’s Triangle in the opposite direction. If
you haven’t heard of Pascal’s Triangle, you might enjoy this article anyway, and
you’ll definitely learn something new.
What is Pascal’s Triangle?
If you already know what Pascal’s Triangle is, you can skip this section. If
not, it’s a pretty simple concept to grasp and you’ll be very confused if you
skip it.
When making Pascal’s Triangle, start by making a triangle with two diagonals of
1s. In theory, the triangle is limitless, but in practice, it would take a
really long time to write that out, so I’ll only include 6 rows.
11111111111
For every cell not on the edge, which should all be 1s, add the cell to the
top-left with the cell on the top-right and fill it in. Let’s start with the
third row, as the first two are all 1s.
111111211111
That wasn’t very difficult, right? Let’s fill in the fourth row.
11111312131111
I’ll skip to when all six rows are filled in.
11151413101261310141511
Cool! You now know the basics of Pascal’s Triangle.
Special conventions
For the rest of the document, I will use an alternate format to write Pascal’s
triangle. The format that uses an actual triangle is difficult to type in LaTeX
and hides a few patterns, so we’ll stick to a square shape. This new format
provides a more compact version of the original shape, yet it keeps the original
patterns. In this shape, we add the cells to the left and above a given item to
get its value. Here’s an example:
Now that we’ve got that sorted out, let’s get on to the actual content.
All the zeroes
By the rules we’ve defined, if a cell c has a value, it must be equal to the
value of the cell above it, which we’ll call a, plus the value of the cell to
the left of it, which we’ll call b.
By the rules of algebra and subtraction, we also have:
cc−ac−b10−610−4=a+b=b=a=4=6
You might be thinking, “Wow! It’s pretty cool that you can subtract numbers. But
why are we doing this?” And I know. Subtraction is pretty amazing, but we can
actually use it to discover more of Pascal’s Triangle. Let’s look at the first
row. I’ll highlight two of the 1s in the top row.
Of course, similar logic applies to the left side of the matrix. However, in the
interest of not making wide images that require horizontal scrolling on mobile
devices (since that is a horrible experience), we’re only going to focus on the
top for now.
Now that we’ve added a new top row, we can use the subtraction rule again and
find even more zeroes! Isn’t this exciting?
We’ve found everything that we can do with simple subtraction. However, there’s
one last trick we can use before we have to use complex math.
Symmetry
Before we get onto more math, I’d like to introduce a new syntax we’ll use to
identify elements of Pascal’s Triangle based on their row and column numbers.
Currently, we know that the triangle extends in all directions, so our numbers
will have to make use of negatives. Let’s name the top-left 1 as being in the
0th row and 0th column.
Now we can name the value of a given element as Pa,b, where a is the row
number and b is the column number. For example, P2,4=15 because the
cell in the 2nd row and 4th column has a 15 in it. Notice that we’re calling
the rows and columns that read 1,1,1,1,… the zeroth rows and columns.
We do this because they provide a good splitting point between the sections with
whole numbers and the sections with zeroes.
Now that we have this syntax nailed down, you’ll start to notice some patterns.
Namely, for any values of a and b, Pa,b=Pb,a. That may look weird,
but it essentially means that the table is symmetric across the top-left to
bottom-right diagonal. And it’s correct! If you look at the square, you’ll
quickly see that it’s completely symmetrical across the diagonal. The only
values that aren’t repeated are 2, 6, 20, 70, and 252, because they
are directly on the diagonal.
Of course, our rule tells us that adding these must be equal to 1, the cell
directly to the right and below the cells with a value of x. Since we know
that, we can do some basic algebra and solve for x:
This is the furthest that basic addition, subtraction, and symmetry will guide
us. From now on, we’ll need to resort to more advanced methods to compute the
numbers. However, don’t let this deter you! We’re going to find a beautiful
formula for the elements of Pascal’s Triangle and use it to solve for the rest
of the table. The “advanced methods” we’re going to use actually aren’t that
advanced; it’s just basic multiplication.
Summation notation
Actually, it’s a bit more complicated than that.
First, take a look at the following series, known as the triangular numbers.
1,3,6,10,15,21,28,…
There’s a simple rule that governs the sequence. To find it, I’ll rewrite the
sequence using sums.
136101521=1=1+2=1+2+3=1+2+3+4=1+2+3+4+5=…
Now do you notice the pattern? That’s right: you just add the next natural
number to find the next term of the sequence. Can you guess the number after
28? That’s right: it’s 36, or 28+8.
We can express this sequence by using something known as summation notation, or
sigma (Σ) notation. Here’s an example:
n=1∑4n
That may look confusing, but it’s essentially saying, “For every number n from
1 to 4 (inclusive), evaluate n and add the results,” which is
1+2+3+4, or 10.
Here’s a more complex example:
n=1∑6n2
This has a similar meaning: “For every number n from 1 to 6 (inclusive),
evaluate n2 and add the results,” which is
12+22+32+42+52+62, or 91.
Summation notation is very useful when dealing with triangular numbers, as we
can express the nth triangular number as
i=1∑ni
In fact, this sum is equal to
2n(n+1)
Why? Well, let’s imagine creating the 4th triangular number out of blocks.
44⎩⎨⎧∙∙∙∙∙∙∙∙∙∙
This almost looks like a rectangle, just with the right side missing. Let’s take
our triangle, rotate it 180 degrees, and put it on the right.
45⎩⎨⎧∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙∙
Look! We now have a 4 by 5 rectangle of blocks, and we can find its area just by
multiplying 4⋅5, for a total of 20. We already know that we have two
triangles in the rectangle, so we can just divide 20÷2 and get 10,
which is the 4th triangular number.
This reasoning works for any number n. We make a triangle with two sides of
length n, rotate it 180 degrees to make a rectangle of n×n+1
dimensions, find the area of n(n+1), and divide by 2 to get the final
result of 2n⋅(n+1).
Thus, we now know that
i=1∑ni=2n⋅(n+1)
Product notation
While many people have heard of summation notation, not nearly as many know of
product notation. It works similarly to summation notation, but we use a capital
pi (Π) instead of a capital sigma (Σ), and we multiply the results
instead of adding them.
Here’s an example.
i=1∏4i=1⋅2⋅3⋅4=24
One commonly known example of product notation is the factorial function. It
multiplies every number from 1 up to a specific whole number and is
represented by putting an exclamation mark (!) after a number or expression.
For example:
7!=i=1∏7i=1⋅2⋅3⋅4⋅5⋅6⋅7=5040
Try evaluating 5! on your own. Click this dropdown to find the answer.
5!=i=1∏5i=1⋅2⋅3⋅4⋅5=120
One useful fact about factorials is that for any number n,
(n−1)!⋅n=n!
Here’s an example.
(4−1)!⋅43!⋅41⋅2⋅3⋅4=4!=4!=1⋅2⋅3⋅4
We’ll be using factorials later, so be on the lookout for them. Here are the
first few factorials so that you can recognize them later.
1,2,6,24,120,720,…
The first column
Since we have no clue how to approach the entire triangle, let’s start by
looking for a formula for each column. First, I’ll copy and paste Pascal’s
triangle here as a reference.
For now, we’re only going to focus on finding cells whose row and column numbers
are both positive or zero. A formula for the first column is easy, as the
numbers in the column, by definition, are all 1.
Px,1=1
The second column seems to be the natural numbers, but let’s see if we can
express more rigorously why that happens. We know that each cell is equal to the
value of the cell above it added to the value of the cell to the left of it. But
the cell above it has the value of the cell above it plus the value of the cell
to the left of it, and so on. Basically,
Px,2=Px,1+P(x−1),1+P(x−2),1+⋯+P0,1
Let’s show a specific example. I’ll highlight a specific cell in the triangle.
Technically, the top 1 ends the sequence, but for convenience we’ll represent
it as 1+0. It doesn’t change anything, because 1+0=1, but it helps
with the math.
Because of the process we used, we know that we just have to add up all of these
values to get the final value of 4. And guess what’s good at summing values?
That’s right: our old friend ∑. We’ll represent each term using
Prow,column notation, so check back to that section if you forget what it
is. Without further ado, here is our formula for the 1st column.
Px,1=i=0∑xPi,0
Let’s try it on the 4th row of the 1st column. We already know that we should
get 5.
We can see that we just get the row number plus 1, or x+1 for a generic row
x in the 1st column.
Px,1=i=0∑xPi,0=x+1
The second column
Great! Now let’s find a formula for the second column. We’re going to use the
same summation trick as earlier. To show why it still works, I’m going to
highlight a cell in the 2nd column.
And yet again, we have shown that we can just add up the values in the previous
column, so we can write down a formula for the second column. This will be
very similar to the formula for the first column, but with 2 and 1 instead
of 1 and 0.
Px,2=i=0∑xPi,1
Let’s plug in the value of Pi,1.
Px,2=i=0∑x(i+1)
It looks like we’re stuck, but we can use a clever trick. Instead of adding one
to each value of i, let’s just increase the lower and upper bounds by 1,
effectively doing the same thing.
Px,2=i=1∑x+1i
But wait! We already know how to sum up these numbers; it’s just the triangular
number formula.
Px,2=2(x+1)⋅(x+2)
You may notice we’re writing (x+1)⋅(x+2) instead of
x⋅(x+1). That’s because we’re finding the x+1th triangular number,
not the xth, so we need to increase everything by 1.
Why? We can use a similar geometric proof to what we did with the triangular
numbers, this time with a rectangular prism of side lengths n, n+1, and
n+2, but it’s difficult to put into an image, so you’ll have to take my word
for it. If you want, prove it on your own at home.
By the way, this formula generates a sequence known as the tetrahedral numbers.
Just thought you should know.
Now we can start on a formula for the third column.
Px,3Px,3=i=0∑xPi,2=i=0∑x2(i+1)⋅(i+2)
But wait! This looks exactly like the formula we found above, just with i+1
instead of i. Thus, we find that
Px,3=6(x+1)⋅(x+2)⋅(x+3)
We can test this formula by plugging in 5, for the fifth row and third column.
Using similar logic to the above, we can find the formula for the fourth column.
Px,4=24(x+1)⋅(x+2)⋅(x+3)⋅(x+4)
Or the fifth.
Px,5=120(x+1)⋅(x+2)⋅(x+3)⋅(x+4)⋅(x+5)
Everything about this formula seems reasonable except the denominators. They
seem to change randomly from column to column. I’ll list the first few for
convenience.
2,6,24,120,…
Wait. Do you recognize those numbers from somewhere? Because I sure do. They’re
the first few factorial numbers!
In fact, this is a provable pattern. We can go on and on for as many columns as
we like and prove that the denominators follow this sequence. In fact, even the
first column, for which we thought the formula was x+1, could really be
represented as 1x+1, where 1 is the first factorial number!
We’re not going to prove it here, as it takes too long, and frankly, I have no
idea how to do it.
A formula for all cells
We can use the pattern from the previous section to deduce that for any row x
and column y,
Px,y=y!(x+1)⋅(x+2)⋅⋯⋅(x+(y−1))⋅(x+y)
And here we have an opportunity to use the product notation that we learned
about so long ago!
Px,y=y!∏i=1y(x+i)=y!1⋅i=1∏y(x+i)
We can reduce the complexity of the ∏ symbol by adding x to the bounds
and removing it from the expression.
Px,y=y!1⋅i=1+x∏y+xi
Remember that a simple product like this is basically a factorial. There’s one
problem, however: the lower bound starts at 1+x, not 1. We can remedy this
by changing the lower bound to 1 and dividing by ∏i=1xi.
Px,y=y!1⋅∏i=1xi∏i=1y+xi
And of course, we can change both of these into factorials.
Px,y=y!1⋅x!(x+y)!
Let’s multiply these into a single fraction.
Px,y=x!⋅y!(x+y)!
And we’re done! We finally have a formula that works for any cell. Before we get
too much confidence, however, let’s test our formula. Let’s find the cell in the
fourth row and sixth column.
The formula provides a very simple explanation for the symmetry we see in
Pascal’s Triangle. Notice how all the operations in the expression
x!⋅y!(x+y)! all commutative. We can switch x+y to y+x
and flip the order of the factorials in the denominator from x!⋅y! to
y!⋅x!. However, none of these operations change the result of the
expression, giving Pascal’s Triangle its mirrored structure.
You might ask, “Doesn’t this break for the rows and columns of 1s? We’d have
to evaluate 0!, but you can’t multiply zero numbers together.” And you have a
valid point. However, mathematicians have decided that, yes, it does make sense
to multiply zero numbers together, and that the result is 1. Thus, 0!=1,
and we can evaluate the formula for those numbers and get the reasonable answer
of 1 if x=0 or y=0.
We can also prove that this formula obeys the law that
Pa−1,b+Pa,b−1=Pa,b. If you want to skip this part, you can go to
the section titled
Introducing the gamma function.
First, let’s represent the equation above using our formulas.