Thread by @RamanujansDosa

1/

Math is amazing.

Pascal's Triangle is one of the core ideas of math.

It's used in probability, combinatorics and algebra.

In this thread, you'll learn about how this triangle can be applied to counting paths, the choose coefficients, and the binomial theorem.

2/

The setup of this problem starts with simplicity, as is often common in math.

We will start with an infinitely large city named Euclidtown.

This city has perfectly straight streets, all intersecting at 90˚ angles.

3/

Now, our friend Ramanujan has just attended an all-time mathematicians' reunion at Euclid's huge house.

In the party, Pierre de Fermat gave Ramanujan a difficult number theory problem.

4/

In fact, Ramanujan pondered this problem for so long during the party that, on the way back, he forgot where his apartment was!

However, he recalls that he only went WEST and SOUTH when walking to the party, so he must travel NORTH and EAST to get back to his apartment.

5/

Let's assume that Ramanujan has equal probability of going North (N) or East (E) at *any* intersection that he arrives at.

Also, suppose he takes one minute to cross each block (thus, he reaches an intersection and makes a decision to go N or E *every* minute).

6/

After one minute, where could the lost Ramanujan be?

Well, he could have decided to go N one block or he could have decided to go E one block.

At both these locations that Ramanujan could have arrived at, write the number of ways he could have gotten there (which is 1).

7/

Now, after two minutes, there are three places where Ramanujan could be:
2 blocks to the north,
2 blocks to the east,
OR 1 block to the north and 1 block to the east (there are two ways for this case to happen)

We write these cases as:

NN
EE
NE/EN

8/

Suppose one more minute has passed. Now, there are four more locations where he can be (see below).

Two of these locations (3 blocks E and 3 blocks N) have only one possible route leading to them.

However, the other two locations have *three* possible routes!

9/

After *four* minutes, there are now *five* possible places where Ramanujan could be.

He is MOST likely to end up 2 blocks to the East and 2 blocks to the North - there are SIX routes leading here.

He is again LEAST likely to end up exactly 4 blocks E or 4 blocks N.

10/

This process seems kind of weird and unpredictable! We'll systematize it to get a better idea of what's happening:

Is there a RULE to get Ramanujan's possible locations - and the number of paths to those locations - from the data collected in the previous minute?

11/

Here's the core observation that reveals this:

Suppose that Ramanujan wants to reach the red circle below in 5 minutes.

The number of ways to get there is exactly the number of ways to get to the DIAMOND plus the number of ways to get to the CROSS (x).

12/

Thus, we see that the number of ways to get to any particular location in the 5th minute is exactly a SUM of two routes that we've already calculated from the 4th minute!

This really simplifies our work calculating the number of routes to possible locations.

13/

This rule is *recursive*, and we can use it to predict his possible locations after many, many minutes through calculating the number of ROUTES to possible DESTINATIONS.

14/

After continuing this process, we observe that the resulting grid of routes has a lot of patterns (see if you can prove some of them):

-It is symmetric about a line
-The numbers are largest towards y = x.
-It is bordered on the left and bottom by 1's.

15/

There are also some more subtle patterns, however, that need to be investigated.

You see, after n minutes, the SUM of the possible routes to ANY (!) of the locations is exactly 2 to the power of n!

16/
This can be proved quite easily: after n minutes, Ramanujan has reached exactly n intersections.
At each intersection, he has TWO choices: whether to go NORTH or EAST.
Thus, he has 2^n possible routes.

See below for a formal proof if you love induction.

17/

All of these patterns are great, but now we transition to the next step in the story: moving from paths to the choose coefficients.

The numbers that appear in this lattice, forming triangles that get larger and larger, might have some deeper meaning.

18/

All of the locations on this triangle that Ramanujan could be at are *uniquely* determined by the number of times he has turned EAST at any previous intersections.

(We could also determine these locations by the number of times he has turned NORTH, due to symmetry).

19/

Suppose that after 5 minutes, Ramanujan arrives at a point that is 3 blocks to the east.

He has made 5 choices; he elected to go east in 3 of these choices.

Thus, the number of possible routes to the point A below is the number of ways to choose 3 Easts from 5 decisions.

20/

To reiterate, the number of paths to point A is EXACTLY the number of ways to choose 3 things (anything, really!) out of 5 decisions. We call this "5 choose 3."

This observation generalizes - see if you can figure out the general formula, then see the next tweet!

21/
The generalization is:
The number of paths to a location that is *k* blocks to the East of Euclid's house after *n* minutes is exactly n CHOOSE k.

There is a formula for these numbers in terms of n and k; but it's not important for this thread (see below if you're curious)

22/

Sidenote. We can also rotate our triangular array (and erase the streets of Euclidtown) to get the common version of this equilateral triangle, called *Pascal's triangle.*

Each entry in the triangle is the SUM of the two entries above it (see below for precise explanation).

23/

Now, we will show how Pascal’s triangle will help in the derivation of the binomial theorem:

How would one *expand* (x + y)^n using the distributive law for *any* n?

This is called a "binomial expansion."

24/

We begin by considering a few special cases, for n = 0 to 4.

Recognize anything vaguely familiar about the coefficients (constants) in the expansions of the binomials?

25/

Indeed, the coefficients in the binomial expansion are the entries of Pascal's triangle!

Why might this be true?

Well, for any particular n, let's investigate how the coefficient in the kth term of the expansion of (x + y)^n relates to n and k.

26/

In the kth term of the expansion, the exponent on x is k and the exponent on y is n - k. So we can write this kth term in a compact form (see below).

27/

However, this constant is exactly equal to the number of ways to *select* k x's from a list of n x's (see below).

That's why the coefficient on the x^k * y^(n-k) term is exactly n CHOOSE k: we are making n choices and choosing k x's.

28/

Thus, we have arrived at a way to write the binomial expansion of (x + y)^n using Pascal's triangle: each term has a very elegant, direct formula!

This is called the binomial theorem.

Note: this certainly isn't a proof of the theorem.

29/

Wow!

We have derived three neat concepts, from counting paths to the binomial theorem, just from Ramanujan forgetting where his apartment was.

This is one of the most beautiful stories of math: it starts from a simple idea and branches out into advanced areas.

30/

Congratulations! You made it through this thread that connects many ideas in the heart of math.

This certainly isn't the end of the Pascal story. There are other applications that come from this beautiful triangle: for a start, try this problem. projecteuler.net/problem=67.