Proof by Story Telling

One day, you randomly decide to write down the first few lines of Pascal’s Triangle:

$$1$$ $$1\quad1$$ $$1\quad2\quad1$$ $$1\quad3\quad3\quad1$$ $$1\quad4\quad6\quad4\quad1$$ $$1\quad5\quad10\quad10\quad5\quad1$$

Adding up the horizontal rows, we get 1, 2, 4, 8, 16, and 32, respectively. Curiously, these sums are powers of 2. We notice that if $n$ denotes the row (we start at the 0th row), the sum of each row is $2^n$. Let’s prove this by story telling!

Without loss of generality, we look at the sixth row. Suppose we have five distinct frogs (charmingly named A, B, C, D, and E) to bring to the FrogShow™. The number of frogs we can bring to the FrogShow™ ranges from 0 to 5. We wonder how many ways there are to bring the frogs. Holding up frog A, we realize that we can either bring A or not bring A, which gives us two possibilities. Likewise, we can either bring B or not bring B. Thus, we have $2^5 = 32$ ways of bringing our frog friends.

But there’s another way of choosing the frogs! From the five frogs, we can choose 0, 1, 2, 3, 4 and 5 frogs randomly. By definition,

$$n \choose k$$

is the notation for the number of ways to choose $k$ things out of $n$. Thus, there are

$${5 \choose 0}+{5 \choose 1}+{5 \choose 2}+{5 \choose 3}+{5 \choose 4}+{5 \choose 5}$$

ways to choose 0, 1, 2, 3, 4, or 5 frogs from our 5 frogs. But, how do we calculate, let’s say, $5 \choose 3$? There are $5$ ways to pick the first frog, $4$ ways to pick the second frog, and $3$ ways to pick the third frog, giving us $5 \cdot 4 \cdot 3$. However, the order of the frogs don’t matter, so we end up with repeats, like $A, B, C$ but also $B, C, A$! So, we calculate the number of ways to rearrange the three frogs. There are $3$ ways to pick the first frog, $2$ ways to pick the second frog, and $1$ way to pick the third frog, giving us $3!$ ways to rearrange the three frogs. Thus,

$${5 \choose 3} = {3!} = 10.$$

This process can be generalized to

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

Applying this to

$${5 \choose 0}+{5 \choose 1}+{5 \choose 2}+{5 \choose 3}+{5 \choose 4}+{5 \choose 5},$$

we have $1 + 5 + 10 + 10 + 5 + 1 = 32$ ways of choosing our frogs.

Scrutinizing our work, our eyes widen with astonishment as we realize that $1 + 5 + 10 + 10 + 5 + 1$ is the sum of the sixth row of Pascal’s Triangle! It turns out that this can be generalized so that Pascal’s Triangle can be written as:

$$0 \choose 0$$ $${1 \choose 0} {1 \choose 1}$$ $${2 \choose 0} {2 \choose 1} {2 \choose 2}$$ $${3 \choose 0} {3 \choose 1} {3 \choose 2} {3 \choose 3}$$ $${n \choose 0} {n \choose 1} {n \choose 2} \cdots {n \choose n}$$

Because both ways of choosing $0, 1, 2, 3, 4$ or $5$ frogs out of $5$ frogs are equivalent,

$$2^5 = {5 \choose 0} + {5 \choose 1} + {5 \choose 2} + {5 \choose 3} + {5 \choose 4} + {5 \choose 5}.$$

This can be generalized to

$$2^n = {n \choose 0}+{n \choose 1}+{n \choose 2}+ \cdots +{n \choose n},$$

which is why the sum of the rows of the Pascal’s Triangle are equal to powers of $2$.

Interestingly, this is an application of the $<b>Binomial Theorem</b>$⁠, which states that

$$(a+b)^n = ^n {n \choose k} a^{n-k}b^k.$$

When $a = 1$ and $b=1$⁠, by the Binomial Theorem, we have

$$(1+1)^n &= ^n {n \choose k} 1^{n-k}1^k, 2^n &= ^n {n \choose k},$$

which is what we just proved!

In the world of mathematics, there are many elegant proofs. But sometimes, you may just need to tell a story.