COLLECTED BY

Organization:

Alexa Crawls
Starting in 1996,

Alexa Internet has been donating their crawl data to the Internet Archive. Flowing in every day, these data are added to the

Wayback Machine after an embargo period.

Starting in 1996,

Alexa Internet has been donating their crawl data to the Internet Archive. Flowing in every day, these data are added to the

Wayback Machine after an embargo period.

TIMESTAMPS

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