It has been a while since I last posted something about proof methods, but lets dig that up again and take a look at a fourth method. The first three were direct proof, proof by contradiction and contrapositive proofs. Proof by induction is a somewhat different nature.
I have been reading quite a few blog posts recently and they all seem to be witty and clever, so I really wanted to add a joke right here on induction. But I honestly couldn’t find one I think was funny enough. So if you could just laugh or smirk for a few seconds before reading on, my day is saved.
Back to the induction part. Induction usually has it’s strength on statements of the type “For all integers k greater than b, P(k) is true”. For some statements we could prove it with some of the already covered methods, but for others it would mean that we had to prove an infinity of cases.
The analogy I see everywhere and which I find quite fitting is to compare induction to dominoes (and I don’t mean the pizza thing) which are lined up. As soon as you knock the first one over it knocks all the remaining once over one by one. Induction works in much the same way.
We need to prove two things and for explanatory purposes I will explain them in reverse order
- Induction step: We assume that P(k) is true and then we need to show that P(k+1) is true as well. That is the same as saying if we knock an arbitrary domino over, then the next one will fall as well.
- Base Case: We need to prove the base case (P(b) – or in other words we need to show that we can knock over the first domino.
Once we shown these two cases then if b=1 we have shown P(1), which by the induction step implies that P(2) is true, which by the induction step implies P(3)….. all the way to infinity.
Induction Proof Example
Let us start out with proving something Gauss figured out very early in his childhood.
Proposition: For all the following is true
I know this could be proven as a direct proof, but it is rather easy to and therefore well suited for an example. The question is rather easy to understand, so I wont do a whole lot to explain the idea.
Base case: The base case in this situation is N = 1, so we need to show that the statement holds for that
The sum of n from 1 to 1 is…. 1, so the left hand side is rather easy. The right hand side is easy to calculate using the basic arithmetic taught in 1st-4th grade, so we can reduce the statement to
Which is true.
Induction step: We assume that the statement holds for N = k such that it holds for
and need to show that the statement is also true for
Let us do this part as a direct proof.
The first step just pulls k+1 out of the summation. the second part of the last statement is by assumption equal to so we have
which proofs the proposition that
Thereby we have proven that it holds for the base case of n=1 and that it holds for all n by induction.
I have kept this blog post a tad short with only one example. I have a few more topics regarding induction that I want to blog about but that will be in a later blog post.
I have found a few good sources for reading about proof by induction. As always The book of proofs is a good choice, and also this 21 page pdf file which in my opinion gives a great covering of the topic.
The metaphor of dominoes also gave rise to the chosen post photo, which was kindly shared under the creative common license by Malkav. My crop of the photo is of course shared under the same conditions.