We start with a simple version of the claim, which I will refer to as claim 2 (for reasons that will become apparent):
We now graduate to claim 3:
Notice that we used claim 2 to prove claim 3. Similarly, we can use claim 3 to prove claim 4:
You may have noticed the proofs of claim 3 and claim 4 are almost identical. You might imagine that you could use claim 4 to prove claim 5, and claim 5 to prove claim 6, and so on. Indeed you can, and this is the idea behind induction.
Because this pattern is so common, there is some stylized language. Typically, instead of "claim n", people often write P(n); this is referred to as the inductive hypothesis. The first proof (in our case, the proof of claim 2) is referred to as the base case. The general proof (using P(n) to prove P(n+1)) is called the inductive step. Here is a stylized induction proof:
We must showand assuming .
In the base case, when , we want to show to show that every is also in . Choose an arbitrary in the right hand side. Then and . This means either (1) or (2) . In case (1), we have and , so , and thus . B_2ase (2) is similar. In either case, , as required.