Lesson 6

Third Proof: Pascal's Triangle with a Wall.

Recall that in Pascal's triangle, each cell contains the number of ways to reach that cell.

We are now interested not in all such paths but only in paths ending on the central vertical line and not entering the left half of the triangle. Along the central vertical line, the Catalan numbers will appear.

In our truncated triangle, the property “the value in a cell equals the sum of the two values directly above it” holds for all cells except the cells on the central vertical line. However, it is not hard to adjust so that it holds for them as well.

Now comes the trick: reflect half of the triangle across the vertical line with zeros.

This view is convenient: the usual Pascal triangle grows (by Pascal's rule) from a single vertex labeled 1. Now instead of this vertex, we have two vertices—1 and -1. We grow the triangle by the same rule or equivalently grow two triangles—one from \(1\) and the other from \(-1\). Each cell contains the sum of the values in the two corresponding cells from these triangles.

Thus, the value we are interested in equals the difference between the central value and its neighbor to the right: \[\binom{2n}{n}-\binom{2n}{n+1}\ .\]