Mathematical Induction

Mathematical Induction

Let's begin with an example.

Example: A Sum Formula

Theore. For any positive integer n, 1 + 2 + ... + n = n(n+1)/2.

Proof. (Proof by Mathematical Induction) Let's let P(n) be the statement "1 + 2 + ... + n = (n (n+1)/2." (The idea is that P(n) should be an assertion that for any n is verifiably either true or false.) The proof will now proceed in two steps: the initial step and the inductive step.

Initial Step. We must verify that P(1) is True. P(1) asserts "1 = 1(2)/2", which is clearly true. So we are done with the initial step.

Inductive Step. Here we must prove the following assertion: "If there is a k such that P(k) is true, then (for this same k) P(k+1) is true." Thus, we assume there is a k such that 1 + 2 + ... + k = k (k+1)/2. (We call this the inductive assumption.) We must prove, for this same k, the formula 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2.

This is not too hard: 1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1) = (k(k+1) + 2 (k+1))/2 = (k+1)(k+2)/2. The first equality is a consequence of the inductive assumption.

q

The Math Induction Strategy

Mathematical Induction works like this: Suppose you want to prove a theorem in the form "For all integers n greater than equal to a, P(n) is true". P(n) must be an assertion that we wish to be true for all n = a, a+1, ...; like a formula. You first verify the initial step. That is, you must verify that P(a) is true. Next comes the inductive step. Here you must prove "If there is a k, greater than or equal to a, for which P(k) is true, then for this same k, P(k+1) is true."

Since you have verified P(a), it follows from the inductive step that P(a+1) is true, and hence, P(a+2) is true, and hence P(a+3) is true, and so on. In this way the theorem has been proved.

Example: A Recurrence Formula

Math induction is of no use for deriving formulas. But it is a good way to prove the validity of a formula that you might think is true. Recurrence formulas are notoriously difficult to derive, but easy to prove valid once you have them. For example, consider the sequence a0, a1, a2, ... defined by a0 = 1/4 and an+1 = 2 an(1-an) for n ≥ 0.

Theorem. A formula for the sequence an defined above, is an = (1 - 1/22n)/2 for all n greater than or equal to 0.

Proof. (By Mathematical Induction.)

Initial Step. When n = 0, the formula gives us (1 - 1/22n)/2 = (1 - 1/2)/2 = 1/4 = a0. So the closed form formula ives us the correct answer when n = 0.

Inductive Step. Our inductive assumption is: Assume there is a k, greater than or equal to zero, such that ak = (1 - 1/22k)/2. We must prove the formula is true for n = k+1.

First we appeal to the recurrsive definition of ak+1 = 2 ak(1-ak). Next, we invoke the inductive assumption, for this k, to get

ak+1 = 2 (1 - 1/22k)/2 (1 - (1 - 1/22k)/2) = (1 - 1/22k)(1 + 1/22k)/2 = (1 - 1/22k+1)/2. This completes the inductive step.

q

Exercises

Prove each of the following by Mathematical Induction.

  1. For all positive integers n, 12 + 22 + ... + n2 = (n)(n+1)(2n+1)/6.

  2. Define a sequence a0, a1, a2 by the recurrsive formula an+1 = 2 an - an2. Then, a closed form formula for an is an = 1 - (1 - a0)2n for all n = 0, 1, 2, ....

Next==>Unwinding Definitions

<==Back To If, and Only If

Back to Proofs