O'Reilly logo

Good Math by Mark C. Chu-Carroll

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required