# Proof:Weak induction principle starting at k is equivalent to weak induction

Suppose you have an inductive proof in the following style:

To prove using weak induction, you can prove and prove for an arbitrary , assuming .

But you are only willing to accept the basic weak induction principle:

To prove "" using 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).

You can systematically convert from the first style to the second:

Suppose you know the following: Then you can conclude , using only the basic weak induction principle.

We actually give two different proofs:

Proof: Using vacuous truth
We will assume that , because if then the two inductive principles are identical.

Assume the statements that are given in the claim. Let be the statement "if then ." We will show and for an arbitrary , assuming .

is vacuously true, since .

Now choose an arbitrary , and assume ; we will show , i.e. that if then . Assume that ; we want to show . There are two cases to consider:

• if , then we will use assumption 1 that is given in the claim. We are given .
• on the other hand, if then . This means we can apply to conclude . Now we know and so we can apply the second assumption given in the claim to conclude .

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 that is the same as :

Proof: By changing variables
Assume the statements that are given in the claim. Let . We will show and for an arbitrary , assuming .

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.