How does proof by induction work?

In: Mathematics

Think of proof by induction like those things where you line up a bunch of dominoes and they knock each other over.

You want to prove that every natural number n has some property P. The two steps of an induction proof are:

The base case: you prove that 1 (or sometimes 0) has property P. This is like knocking over the first domino.

The induction step: you show that n+1 has property P whenever n does. This is like showing that each domino is close enough to the next to knock it over.

Since you’ve knocked the first domino over, and shown that the dominoes are all close enough to each other, you know that every domino will fall over. So every n has property P.

First I set up 2 dominoes right next to each other and I push one over. It falls into the second domino and also knocks it over. After that I set up a long row of dominos. I could then tell you that if I push over the first domino, that eventually the last domino in that row will fall over. The proof lies in the fact that I already showed you that each domino will knock over the domino next to it.

When we do mathematical proof by induction we do the same thing. We have to show that every time we advance a step from n -> n+1 that the chain will continue until we get to whatever result we are proving (set up the row of dominos). After that we just have to show the initial case (push the first domino over).

The best way to explain it looking at 2 steps… let’s say you want to prove something by induction, (i.e. that something is true for every step in a sequence)…

1) Prove it works for the first step (just plug the numbers in)

2) Assume it’s true for any step. Using that assumption… prove it’ true for the next step.

So, you’ve proved it’s true for the first step… you’ve proved that the next step will be true… so the second step must be true…. by the same logic then the third step is true… and the fourth step… and so on.

The proof by induction can be applied on a set, the elements of which can all be obtained from a certain finite number of basic elements and a certain finite number of elementary operations.

On such a set, to prove that all elements of the set have a certain property, it’s sufficient to prove that all basic elements have it, and that it is stable through each elementary operation, which means that, if all operands have the property, then so does the result.

The proof by recurrence is a specific case of proof by induction, where you prove properties on all integers relying on the fact that all integers can be obtained from a basic element (zero) and an elementary operation (the successor, which to n associates n+1).