This

**preview**shows pages 1-2. to view the full**7 pages of the document.**MATH 135 Winter 2009

Lectures IV/V Notes

Mathematical Induction

The second technique of proof at which we’ll look is mathematical induction. This is a technique that

is normally used to prove that a statement is true for all positive integers n.

Motivation

Why would we want to do this? Suppose that we had a sequence {xn}deﬁned by x1= 1 and

xr+1 = 2xr+ 1 for r≥1.

What is x2?x3?x4?

Do you see a pattern? (Beware of patterns!)

What if we wanted to know x2008? What would we have to do?

It doesn’t make sense to calculate x2through to x2007 individually, and it does look like we have

a pattern. Is there a way to prove that xn= 2n−1 for all positive integers n? This would allow us

to be able to state the value of x2008 or x23487 or whatever.

This is where induction comes in.

Technical Details

Induction is a technique for proving statements of the form P(n) where n∈P.

(For example, P(n) = “xn= 2n−1”.)

This technique relies on

Principle of Mathematical Induction (POMI)

Let P(n) be a statement that depends on n∈P.

If

(i) P(1) is true, and

(ii) P(k) is true ⇒P(k+ 1) is true,

then P(n) is true for all n∈P.

Why does this work? Suppose that we know (i) and (ii) to be true about P(n).

(i) says P(1) is true

(ii) says “If P(1) is true, then P(2) is true” so P(2) is true

(ii) then says “If P(2) is true, then P(3) is true” so P(3) is true

Following this along, P(n) is true for all n∈P

A couple of analogies: dominos, robot climbing ladder

Proofs by Induction

There are three parts to a proof by induction:

i) Base Case – Prove statement for smallest admissible value of n(usually n= 1)

ii) Induction Hypothesis – Suppose that P(k) is true for some k∈P

iii) Induction Conclusion – Prove that P(k+ 1) is true based on the hypothesis that P(k) is true

Only pages 1-2 are available for preview. Some parts have been intentionally blurred.

Example

A sequence {xn}is deﬁned by x1= 1 and xr+1 = 2xr+ 1 for each positive integer r≥1. Prove that

xn= 2n−1 for every positive integer n.

Proof

We prove this by induction on n.

Base Case n= 1

LS = 1 RS = 21−1=1

Therefore, the result is true for n= 1.

Induction Hypothesis

Assume the result is true for n=k. That is, assume that xk= 2k−1 for some k∈P,k≥1.

Induction Conclusion

Consider n=k+ 1. Then

xk+1 = 2xk+ 1

= 2(2k−1) + 1 (by Induction Hypothesis)

= 2k+1 −2+1

= 2k+1 −1

as required. Thus, xn= 2n−1 for all n∈Pby POMI.

###### You're Reading a Preview

Unlock to view full version