The book explains the ideas behind induction rather well. However, the actual proofs using induction in the book take (in my opinion) steps that are a bit too large, which makes it difficult to see for someone who has never seen induction proofs what is going on.

Here, I present induction proofs for some of the examples in the book in the way I think they should be written. And the way you should write them in the answers to the weekly assignments and the exam. You can find more examples in the answers of the exercises for week 3.

Important principles we try to always follow are the following:

1. Always write down in the proof that are you are induction, what kind of induction you are doing, and over what variable.

2. Induction proofs really work the same way as proofs by case distinction. In proofs by case distinction, we (1) cleary state what cases we are considering, and (2) what we know in each case. We do the same in induction proofs. The only difference is that we have an extra bit of information we may use in the step case, namely the induction hypothesis (I.H.). In the step case, we therefore always explicitly write down what the induction hypothesis is.

3. The induction hypothesis says that we can use the fact that we have already proved the thing we are proving for one (or several) previous values. Thus, we have two "points of reference" we are talking about in the step of an induction proof: (1) the variable for which we are proving the thing (usually called n in the below examples), and (2) the variable for which we assume we have already proved the thing (usually called k in the examples below). In simple induction (what the book calls the first induction principle), we have n=k+1.

To prove: 1 + 2 + ... + n = n(n+1)/2,    for n ≥ 1

Proof: By induction over n.

Base case: n=1: Then we have 1 = 1(1+1)/2. OK!

Step case: n=k+1, k ≥ 1.

1. By the induction hypothesis (I.H.), we know that 1 + 2 + ... + k = k(k+1)/2.

2. Consider

       1 + 2 + ... + n

    = 1 + 2 + ... + k + (k+1)

    = (1 + 2 + ... + k) + (k+1)

    = k(k+1)/2 + (k+1)       [ by the I.H. ]

    = k(k+1)/2 + 2(k+1)/2

    = (k+1)(k+2)/2

    = n(n+1)/2

Which is what we had to prove!

To prove: 1 + x² + ... + xⁿ = (xⁿ⁺¹-1)/(x-1),    for x /= 0, x /= 1, n ≥ 0

Proof: By induction over n.

Base case: n=0: Then we have 1 = (x-1)/(x-1). OK!

Step case: n=k+1, k ≥ 0.

1. By the induction hypothesis (I.H.), we know that 1 + x² + ... + x^k = (x^k+1-1)/(x-1).

2. Consider

       1 + x² + ... + xⁿ

    = 1 + x² + ... + x^k + x^k+1

    = (x^k+1-1)/(x-1) + x^k+1       [ by the I.H. ]

    = (x^k+1-1)/(x-1) + x^k+1(x-1)/(x-1)

    = (x^k+1 - 1 + x^k+1(x-1))/(x-1)

    = (x^k+1 - 1 + x^k+2 - x^k+1)(x-1))/(x-1)

    = (x^k+2 - 1)(x-1))/(x-1)

    = (xⁿ⁺¹-1)/(x-1)

Which is what we had to prove!

To prove: √2 is an irrational number.

Proof: What we are actually going to prove is that for any n ≥ 0, p ≥ 1 in ℕ, √2 /= (n/p).

We are going to do this by strong induction over n.

Base case: n=0: √2 /= (0/p), for any p ≥ 1. OK!

Step case: n ≥ 1.

1. By the induction hypothesis (I.H.), we know that for any 0 ≤ k < n, and any 1 ≤ q, it is the case that √2 /= (k/q).

    [ Note: not only k, but also q is forall-quantified in the above! We have switched names with p to make this explicit. ]

2. We have to show that √2 /= (n/p), for any p ≥ 1. We do this by proof by contradiction. So, we imagine that we have p ≥ 1 such that √2 = (n/p).

3. We know that p < n, because √2 > 1.

4. We also know that 2 = n² / p², which means that n² = 2p².

5. This means that n is even. Let us introduce m such that n = 2m.

6. Now we know that (2m)² = 2p², which implies that 4m² = 2p², which means that 2m² = p².

7. In other words, 2 = p² / m², and thus √2 /= (p/m). In other words, we have found a new way of writing √2 as a rational number! This time, the numerator (here, p) is smaller than the previous numerator (then, n).

8. But 1 ≤ p < n, and by the IH we know that no such p can exist. In other words, what we assumed was false and there are no n and p such that √2 = (n/p).