Chapter 2: Proofs, Induction

Section 2.2 Induction

Induction

The ideas behind induction

There is one final proof technique especially useful in computer science. To illustrate how the technique works, imagine that you are climbing an infinitely high ladder. How do you know whether you will be able to reach an arbitrarily high rung? Suppose we make the following two assertions about your climbing abilities.

1. You can reach the first rung.
2. Once you get to a rung, you can always climb to the next one up. (Notice that this assertion is an implication)

If both statement 1 and the implication of statement 2 are true, then by statement 1 you can get to the first rung and therefore by statement 2 you can get to the second; by statement 2 again, you can get to the third rung; by statement 2 again you can get to the fourth; and so on. You can climb as high as you wish. Both assertions here are necessary. If only statement 1 is true, you have no guarantee of getting beyond the first rung, and if only statement 2 is true, you may never be able to get started.

First Principle of Induction

1. P(1)                (1 has property P)
2. For any positive integer k, P(k) → P(k+1) (If any number has property P, so does the next number.)

If we can prove both assertions 1 and 2, then P(n) holds for any positive integer n.
The foundation for arguments of this type is the first principle of mathematical induction:

\[ \left. \begin{cases} \text{1. P(1) is true} \\ \text{2. P(k) → P(k+1) is true} \\ \end{cases} \right\} \text{P(n) true for all positive integers n} \] The first principle of mathematical induction is an implication. The conclusion is a statement of the form, "P(n) is true for all positive integers n." Therefore, whenever we want to prove that something is true for every positive integer n, mathematical induction is an appropriate proof technique to use.
To know that the conclusion of this implication is true, we show that the two hypotheses, statements 1 and 2, are true. To prove statement 1, we need only show that property P holds for the number 1, usually a trivial task. Statement 2 is also an implication that must hold for all k. To prove this implication, we assume for an arbitrary positive integer k that P(k) is true and show, based on this assumption, that P(k+1) is true.

Reminder: To prove something true for all \(n ≥ \) some value, think induction.

Proofs by Mathematical Induction

Suppose that the ancestral proggenitor Smith married and had two children. Let's call these two children generation 1. Now suppose each of those two children had two children; then in generation 2, there were four offspring. This trend continued from generation to generation. It appears that generation n contains \(2^n\) offspring. More formally, if we let \(P(n)\) denote the number of offspring at generation n, then we guess that:

\( P(n) = 2^n \) We can use induction to prove that our guests for \(P(n)\) is correct.

Basic step -- the proof that the statement is true for the first integer

\(P(1) = 2^1 = 2\)
This is true because we are told that Smith has two children. We now assume that our guess is correct for an arbitrary generation \(k\), \(k ≥ 1\); that is, we assume \(P(k) = 2^k\) and try to show that \(P(k+1) = 2^{k+1}\).

Induction step -- the proof that \(P(k) → P(k+1)\) is true (i.e., if it is true for some integer, then it is true for the next integer)

In this family, each offspring has two children; thus the number of offspring at generation \(k+1\) will be twice the number at generation \(k\), or \(P(k+1) = 2P(k)\). By the inductive assumption, \(P(k) = 2^k\), so

\( P(k+1) = 2*P(k) = 2*(2^k) = 2^{k+1} \)
and so indeed:

\( P(k+1) = 2^{k+1} \) This completes our proof.

Table 2.1 summarizes the three steps necessary for a proof using the first principle of induction:

Table 2.1
To Prove by First Principle of Induction
Step 1	Prove base case.
Step 2	Assume P(k).
Step 3	Prove P(k+1).

Examples

Example 1:

Prove that the following equation is true for any positive integer \(n\).

\( 1 + 3 + 5 + \dots + (2n - 1) = n^2\) (Eq. 1)
Basic Step:
The basic step is to establish \(P(1)\), which is equation (1) when \(n\) has the value 1.

P(1):

left side: \(2\times1-1 = 1\)
right side: \(1^2\)
\(P(1): 1 = 1^2\)
P(1) is true

This is certainly true. For the inductive hypothesis, we assume \(P(k)\) for an arbitrary positive integer \(k\), which is equation (1) when \(n\) has the value \(k\), or

\(P(k): 1 + 3 + 5 + \dots + (2k-1) = k^2\)
Induction Step:
Using the inductive hypothesis, we want to show \(P(k+1)\), which is equation (1) when \(n\) has the value \(k+1\), or

\(P(k+1): 1 + 3 + 5 + \dots + [2(k+1)-1] = (k+1)^2\)
The left side of \(P(k+1)\) can be rewritten to show the next-to-last term:

\(1 + 3 + 5 + \dots + [2(k+1)-1]\)
\( = 1 + 3 + 5 + \dots + (2k-1) + [2(k+1)-1]\)
\( = k^2 + [2(k+1)-1]\)
\( = k^2 + [2k + 2 - 1]\)
\( = k^2 + 2k + 1\)
\( = (k+1)^2 \)
Therefore,
\(1 + 3 + 5 + \dots + [2(k+1) - 1] = (k+1)^2\) This completes our proof.

Example 2:

Prove that for any positive integer \(n ≥ 1\),
\(1 + 2^1 + 2^2 + \dots + 2^n = 2^{n+1}-1 \) (Eq. 2)
Basic Step:
The basic step is to establish \(P(1)\), which is equation (2) when \(n\) has the value 1.

P(1):

left side: \(1 + 2^1\) = 3

right side: \(2^{1+1}-1\) = 3
\(P(1): 1 + 2^1 = 2^{1+1} - 1 = 2^2 - 1\)
which is true. We take \(P(k) = 1 + 2^1 + 2^2 + \dots + 2^k = 2^{k+1} -1\) as the inductive hypothesis and try to establish:

\( P(k+1): 1 + 2^1 + 2^2 + \dots + 2^{k+1} = 2^{k+1+1} - 1\)
Induction Step:
Rewrite the sum on the left side of \(P(k+1)\) reveals how the inductive assumption can be used:

\( 1 + 2^1 + 2^2 + \dots + 2^{k+1} \)
\( = 1 + 2^1 + 2^2 + \dots + 2^k + 2^{k+1}\)
\( = 2^{k+1} - 1 + 2^{k+1} \)
\( = 2\times2^{k+1} - 1\)
\( = 2^{k+1+1} - 1\) Therefore:
\( 1 + 2^1 + 2^2 + \dots + 2^{k+1} = 2^{k+1+1} - 1\)
which completes our proof.

Not all proofs by induction involve formulas with sums. Other algebraic identities about the positive integers, as well as nonalgebraic assertions like the number of offspring in generation n of the Smith family, can be proved by induction.

Example 3:

Prove that the following equation is true for any positive integer \(n\).

\( 2^n > n\) (Eq. 3)
Basic Step:
The basic step is to establish \(P(1)\), which is equation (3) when \(n\) has the value 1.

P(1):

left side: \(2^1\)
right side: \(1\)
\(P(1): 2^1 > 1\)
This is certainly true. For the inductive hypothesis, we assume \(P(k)\) for an arbitrary positive integer \(k\), which is equation (3) when \(n\) has the value \(k\), or
\(P(k): 2^k > k\)
Induction Step:
Using the inductive hypothesis, we want to show \(P(k+1)\), which is equation (3) when \(n\) has the value \(k+1\), or

\(P(k+1): 2^{k+1} > k + 1\)
The left side of \(P(k+1)\) can be rewritten:

\( 2^{k+1} = 2^k \times 2^1 = 2^k\times2 = 2\times2^k\) (exponential rule: \(a^{m+n} = a^m + a^n \))
\( 2^{k+1} = 2\times2^k > 2\times k \) (Multiplication Property of Inequality)
\( 2\times k= k + k ≥ k + 1\) (because k ≥ 1)
\(\)
Since we established that:
\( 2^{k+1} > 2\times k \)
and that:
\( 2\times k ≥ k + 1 \)
Therefore, we can conclude by the Transitive Property that:
\( 2^{k+1} > k+1 \) This completes our proof.

Practice

1. Prove that for any positive integer n: \(1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}\)
2. Prove that for all n > 1: \( 2^{n+1} < 3^n \)

Reference

saylor academy