Class Notes (1,100,000)
CA (650,000)
UW (20,000)
MATH (2,000)
MATH135 (300)
Lecture 4

# Lecture 4-5 notes Lecture 4-5 notes including proof by induction

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 r1.
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= 2n1 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 nP.
(For example, P(n) = “xn= 2n1”.)
This technique relies on
Principle of Mathematical Induction (POMI)
Let P(n) be a statement that depends on nP.
If
(i) P(1) is true, and
(ii) P(k) is true P(k+ 1) is true,
then P(n) is true for all nP.
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 nP
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 kP
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 r1. Prove that
xn= 2n1 for every positive integer n.
Proof
We prove this by induction on n.
Base Case n= 1
LS = 1 RS = 211=1
Therefore, the result is true for n= 1.
Induction Hypothesis
Assume the result is true for n=k. That is, assume that xk= 2k1 for some kP,k1.
Induction Conclusion
Consider n=k+ 1. Then
xk+1 = 2xk+ 1
= 2(2k1) + 1 (by Induction Hypothesis)
= 2k+1 2+1
= 2k+1 1
as required. Thus, xn= 2n1 for all nPby POMI.