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 a_{0}, a_{1}, a_{2}, ... defined by a_{0} = 1/4 and a_{n+1} = 2 a_{n}(1-a_{n}) for n ≥ 0.
**Theorem.** A formula for the sequence a_{n} defined above, is a_{n} = (1 - 1/2^{2n})/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/2^{2n})/2 = (1 - 1/2)/2 = 1/4 = a_{0}. 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 a_{k} = (1 - 1/2^{2k})/2. We must prove the formula is true for n = k+1.

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

a_{k+1} = 2 (1 - 1/2^{2k})/2 (1 - (1 - 1/2^{2k})/2) = (1 - 1/2^{2k})(1 + 1/2^{2k})/2 = (1 - 1/2^{2k+1})/2. This completes the inductive step.

q

##
Exercises

Prove each of the following by Mathematical Induction.
- For all positive integers n, 1
^{2} + 2^{2} + ... + n^{2} = (n)(n+1)(2n+1)/6.
- Define a sequence a
_{0}, a_{1}, a_{2} by the recurrsive formula a_{n+1} = 2 a_{n} - a_{n}^{2}. Then, a closed form formula for a_{n} is a_{n} = 1 - (1 - a_{0})^{2n} for all n = 0, 1, 2, ....

** Next==>**Unwinding Definitions

**<==Back To **If, and Only If

Back to Proofs