This document is here to give you several examples of good induction. While it discusses briefly how induction works, you are encouraged to read the Induction Handout for a more thorough discussion of induction.
Induction is really important, so the best thing to understand induction is to do it yourself. Of course, a few examples never hurt. Before we get to the induction proof, you need to understand how an inductively defined set works. We'll start by considering what induction means, leaving mathematics aside.
At its core, induction is simply the process of inclusion. Consider some club, such as the royal order of caribou. No one really knows what these people do, but observation tells that all they do is bowl on Wednesday nights and eat hamburgers on Sunday afternoons. To get into this oddly elite club, a person must first know someone already in the club and meet some qualifications. Whenever such a person is found, he undergoes an ceremony of induction (i.e., he's being included in the club). This new person now enjoys all the rights of being a club member, and he too can bowl on Wednesday nights and eat hamburgers on Sunday afternoons. It is also the case that once someone becomes a member of the royal order of caribou, that person is always a member.
Applying these concepts to mathematics and computer science, we find there is not much difference between the royal order of caribou and proving programs are correct.
Let the set S be the
smallest set such that:

Note that there are several important things about how an inductively defined set works:
 It is the smallest set that satisfies the base case and the inductive step. That means nothing else can be a part of the set. You'll see this in the next example.
 There can be more than one element in the base case.
 There can be more than one rule in the inductive step.
Let the set of Whole
Numbers (W) be the smallest set such that:

Note that this defines the entire whole number set. Remember that we mentioned, it's the smallest set such that the base case and inductive step are true. You can see this when you ask whether 1.5, 2.75, or pi is in the set W? Clearly, they are not. Only 0, 1, 2, 3,... are a part of the set of whole numbers.
Note that the whole numbers are often called natural numbers. Some people would get into arguments over whether, the natural numbers start at 0 or 1. Using principles of inductively defined sets, why is such an argument completely pointless?
Let the set S be the
smallest set such that:

Notice that we have defined a small subset of the ML language. Note too that the induction step has four different rules. When we get to induction proofs later, you'll need to do the induction step of the proof for each individual induction step rule of the inductively defined set. Now one more inductively defined set before we get to induction proofs.
Let the set L be the
smallest set such that:

This is the inductive definition of a properly defined list. Notice how we've used inductively defined sets to define the set of whole numbers, the syntax of subset of ML, and the structure of lists in ML.
P(n): Some statement about n.
The statement is either true or false, depending on n. Claim: Make some claim that P(n) is true for all elements of a certain set. Proof by induction on nThere are many types of induction, state which type you're using

The important thing to realize about an induction proof is that it depends on an inductively defined set (that's why we discussed this above). The property P(n) must state a property about the element n of the set you're inducting over. Now look at some examples:
Prove 
P(n): Claim: , P(n) is true Proof by induction on n
QED 
Notice that in this example we used the inductive definition of set of whole numbers. The base case of the induction proof uses the only element defined in the base case in the inductive definition of whole numbers. And also note that the induction step in the proof assumes P(n) is true for what we know to be in the set, and prove that the only rule of the inductive step in the inductively defined set maintains the property P(n).
Prove that every amount of postage of 12 cents or more can be formed using just 4cent and 5cent stamps. 
P(n): "Postage of n
cents can be formed using 4cent and 5cent stamps" Claim: , P(n) is true Proof by strong induction on n
QED 
Notice two important induction techniques in this example. First we used strong induction, which allowed us to use a broader induction hypothesis. This example could also have been done with regular mathematical induction, but it would have taken many more steps in the induction step. It would be a good exercise to try and prove this without using strong induction. Second, notice how we used many elements in the base case. What is the set that we're inducting over? In this case it is a subset of the whole numbers, and it uses 12 as its base case instead of 0. Notice how we had to prove the base case for four numbers. This was necessary because we make the assumption that postage of n  3 cents exists. If we had only proven that P(12) is true, the base case would not be sufficient to support the claim we make in the induction step.
Prove that for every positive integer n with 
P(n): Claim: , P(n) is true. Proof by induction on n
QED 
Notice that induction can be used to prove inequalities. Also take note that we began with the induction hypothesis and manipulated it to show what we wanted to prove. Something that you should never do is start with what you want to prove and go backwards to either show the Induction Hypothesis or some other known truth.
Explain what is wrong with the following
inductive argument that all horses are the same color.

The two sets are disjoint if n + 1 = 2. In fact, the implication that P(1) implies P(2) is false. 
As you can see, induction used improperly can prove ridiculous things. Often times the mistakes are subtle. It takes a good understanding of induction to use it correctly. Induction is a powerful method of proof, but in the wrong hands it can be dangerous.
Prove copy(x) = x Given: fun copy(l:'a list):'a list = case l of [] => [] x::xs => x::copy(xs) 

P(x):
copy(x) = x Claim: P(x) is true for all properly formed lists Proof by structural induction on L
QED 