Proof:Weak induction principle starting at k is equivalent to weak induction
Suppose you have an inductive proof in the following style:
To prove weak induction, you can prove and prove for an arbitrary , assuming .using
But you are only willing to accept the basic weak induction principle:
To prove "weak induction, you must prove (this is often called the base case), and then you must prove for an arbitrary , assuming (this is called the inductive step)." using
You can systematically convert from the first style to the second:
We actually give two different proofs:
is vacuously true, since .
- if , then we will use assumption 1 that is given in the claim. We are given .
- on the other hand, if apply to conclude . Now we know and so we can apply the second assumption given in the claim to conclude . then . This means we can
This concludes the inductive proof that . This means that , if then . This is just another way of saying , which is what we were trying to prove.
Here is the second proof, which uses the fact thatis the same as :
is the same as ; the first assumption in the claim is , so we are done.
Now, choose an arbitrary ; we want to show , assuming . In other words, we want to show assuming . Since , we have . Thus we can apply the second assumption from the claim to conclude that if holds then holds, and since we know holds, we can conclude that holds. But this is the same thing as saying that holds.This concludes the weak induction proof that for all , . Now, to show the original claim (that for all holds), we choose an arbitrary ; we will show that holds. Since , we have , so holds. But so holds, as required.