Good Math

Using Peano Induction

One simple but fun proof using the natural numbers with addition is this one: suppose I have a natural number N. What’s the sum of all of the integers from 1 to N? It’s N times N + 1 divided by 2. So how can we prove that using the induction rule?

We start with what’s called a base case. That means we need to start with one case that we can prove all by itself, and then that case will be used as the base on which we build the induction. In the induction rule, the first clause says that the fact we want to prove needs to start by showing it for 0, so 0 is our base case. It’s easy to prove this for zero: (0*(0 + 1))/2 is 0. So our equation is true when N = 0. That’s it: that’s our base case done.

Now comes the inductive ...