Proof by beads

See a pattern? It looks like the following formula holds for integers :

There is an intuitive geometric explanation for this formula. Consider arranging an by square lattice of beads. There is a total of beads in this lattice. We can imagine many different ways to walk through the lattice and count them; all such ways will lead to the answer . One way to walk through the lattice is to start at a corner and count along the diagonals. If we walk through the entire square lattice of beads like this, for , we would count – where the contribution comes from the main diagonal and the contributions come from the two opposing corners– and get since this is the total number of beads.

Applied Mathematician Steven Strogatz posted a photo on Twitter that illustrates this geometric interpretation of the formula . Each type of bead classifies a diagonal on the square lattice of beads.

The more rigorous way to prove

is by Mathematical induction.

The base case is . Of course, , i.e., is true.

The inductive step is to assume that holds and then show that this implies .

Somehow, we need to construct on the right-hand side of . Noting that , we can add to both sides

The left-hand side can be rewritten by noting that :

Can you recognize this as ? We have just proven that starting with . That is, we have proven:

completing the proof by induction.

The geometric interpretation is much nicer right?

comments powered by Disqus