Mathematical induction with examples

Mathematical induction is a powerful tool we should have in our toolbox. Here I’ll explain the basis of this proof method and will show you some examples.

Table of Contents

• The theory behind mathematical induction
• Example 1: Proof that 1 + 3 + 5 + · · · + (2n − 1) = n2, for all positive integers
• Example 2: Proof that 12 +22 +···+n2 = n(n + 1)(2n + 1)/6, for the positive integer n

The theory behind mathematical induction

You can be surprised at how small and simple the theory behind this method is yet so powerful.

In general, mathematical induction can be used to prove statements that assert that P(n) is true for all positive integers n, where P(n) is a propositional function.  Notice the underlined phrase because the proof will depend on it. Sometimes, the propositional function does not hold for all positive integers, for instance, for all

• integers greater than 4,
• non-negative integers
• etc.

Identifying the first (smaller) value for which the propositional function holds, is the first step of the proof.

To create a proof using mathematical induction, we must do to steps:

• First, we show that the statement holds for the first value (it can be 0, 1 or even another number). This step is known as the “basis step”.
• Second, we show that if the statement holds for a positive integer k (inductive hypothesis) then it must also hold for the next larger integer k+1.  This step is known as the “inductive step”.

That’s it, that is all we need to know about the theory behind this method. Quite simple, isn’t it?

Mathematical induction is based on the rule of inference that tells us that if P (1) and ∀k(P(k) → P (k + 1)) are true for the domain of positive integers (sometimes for non-negative integers), then ∀nP(n) is true.

Example 1: Proof that 1 + 3 + 5 + · · · + (2n − 1) = n², for all positive integers

Remember we must follow two steps to create the proof.

Basis step:

Because we must that the propositional function holds for all positive integers, then we have to prove that it holds for n=1 (the first/smaller positive integer number. Notice that 0 is not considered a positive number).

On the left side, we have 1+3+5+…+(2n-1), so for n=1, we will have only one term (the first one), in this case, 1.

On the right side (n²) we will have 1²=1

Therefore, we completed the basis step.

Inductive step:

First, we assume P(k) holds. Remember P(k) is known as the inductive hypothesis, we will use it later in the proof.

P(k): 1+3+5+…+(2k-1) = k²

We just substitute n by k.

Now, we have to prove that if P(k) is true, then P(k+1) is also true (P(k)-> P(k+1)).

P(k+1): 1+3+5+…+(2k-1) + (2(k+1)-1) = (k+1)²

Again, we just substitute k by k+1. For convenience (and we should always do this), on the left side, we keep the two last terms.

Now, we use P(k) to prove that P(k+1) is true. If you check the left side of P(k), you will see it also in P(k+1). Now we start transforming the left side of P(k+1) to prove that is equal to the right side.

P(k):     1+3+5+…+(2k-1) = k²

P(k+1): 1+3+5+…+(2k-1) + (2(k+1)-1) = (k+1)²

Transforming only the left side of P(k+1).

P(k+1): k² + (2(k+1)-1), by inductive hypothesis. Here we just apply the inductive hypothesis.

= k² + 2k+2-1

= k² + 2k + 1

= (k+1)²

Notice that transforming the left side only, and using the inductive hypothesis P(k), we got the same as on the right side of P(k+1).

That result completes the inductive step.

We can now affirm that, 1 + 3 + 5 + · · · + (2n − 1) = n², for all positive integers, because of mathematical induction.

It is always important to write the previous sentence, even though it seems like a repetition.

Example 2: Proof that 1² +2² +···+n² = n(n + 1)(2n + 1)/6, for the positive integer n

In this section, I will just write the proof. If you want to see the explanation of each step please refer to the previous example.

Basis step:

The first integer (“for the positive integer n”) is 1.

Left side, 1²=1

Right side, 1(1 + 1)(2×1 + 1)/6= 2×3/6=6/6=1

The basis step is completed.

Inductive step:

P(k): 1² +2² +···+k² = k(k + 1)(2k + 1)/6. (Inductive hypothesis)

P(k+1): 1² +2² +···+k² + (k+1)²= (k+1)(k+2)(2k+3)/6

Transforming the left side.

P(k+1): k(k + 1)(2k + 1)/6 + (k+1)²,  inductive hypothesis

= [k(k+1)(2k+1)+6(k+1)²]/6, notice (k+1) is a common factor

= (k+1)[k(2k+1) + 6(k+1)]/6

= (k+1)[2k²+k + 6k + 6]/6

= (k+1)[ 2k² + 7k + 6]/6

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

Because we transformed the left side using the inductive hypothesis P(k) and obtained the right side, we proved that P(k+1) is true.

Therefore, 1² +2² +···+n² = n(n + 1)(2n + 1)/6, for the positive integer n, because of mathematical induction.

Related pots:

• a) Find a formula for the sum of the first n even positive integers. Prove the formula that you conjectured in part (a)
• Prove that 1·1!+2·2!+···+n·n!=(n+1)!−1 whenever n is a positive integer. 
• Prove that 1^2 +3^2 +5^2 +···+(2n+1)^2 =(n+1) (2n + 1)(2n + 3)/3 whenever n is a nonnegative integer
• Prove that 1^2−2^2+3^2−···+(−1)^(n−1)n^2=(−1)^(n−1) n(n + 1)/2 whenever n is a positive integer