Class Notes (1,100,000)
US (480,000)
UMD (9,000)
CMSC (300)
Lecture 1

CMSC 250 Lecture Notes - Lecture 1: Mathematical Induction


Department
Computer Science
Course Code
CMSC 250
Professor
Jason Filippou
Lecture
1

This preview shows pages 1-2. to view the full 6 pages of the document.
Spring 2018: CMSC250 Notes on Mathematical Induction Proofs
General Comments
on Proofs by Mathematical Induction
All proofs by Mathematical Induction should be in one of the styles below. If not there should
be a good reason.
Our proofs have three separate sections: Base Case, Inductive Hypothesis (IH), and Inductive
Step (IS). You must do it this way. (The book combines IH and IS into one section.)
Because the Base Case is usually trivial and obvious, the justification must be very detailed.
Proofs must explicitly state the Inductive Hypothesis. It is not sufficient to say “Assume true
for n” (although in real life it is sufficient). The book always introduces a predicate P(k) for
the statement to be proved. We do not. It is not sufficient to write “P(k)” for the IH.
If a proof is by Weak Induction the Induction Hypothesis must reflect that. I.e., you may
NOT write the Strong Induction Hypothesis.
The Inductive Step MUST explicitly state where the Inductive Hypothesis is used. (Some-
thing like “by IH” is good.)

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

2
Example Proof by Weak Induction
Theorem. For n1, Pn
i=1 4i2 = 2n2.
BASE CASE: Let n= 1. The summation gives
n
X
i=1
4i2 =
1
X
i=1
4i2 = 4 ·13 = 2 .
The formula gives
2n2= 2 ·12= 2 .
The two values are the same.
INDUCTIVE HYPOTHESIS [Choice I: From n1to n]:
Assume that the theorem holds for n1 (for arbitrary n > 1). Then
n1
X
i=1
4i2 = 2(n1)2.
[It is optional to simplify the right side. If not, it will have to be done inside the Induction
Step.]
INDUCTIVE STEP: [Choice Ia: Start with the sum we care about.]
Pn
i=1 4i2 = Pn1
i=1 i+ (4n2) by splitting sum
= 2(n1)2+ (4n2) by IH
= 2(n22n+ 1) + (4n2) by algebra
= 2n2.by algebra
So the theorem holds for n.
INDUCTIVE STEP: [Choice Ib: Start with the induction hypothesis.]
Pn1
i=1 4i2 = 2(n1)2by IH
Pn1
i=1 4i2 + (4n2) = 2(n1)2+ (4n2) adding 4n2 to both sides
Pn
i=1 4i2 = 2(n22n+ 1) + (4n2) merging the sum on left side
... and algebra on the right side
= 2n2.by algebra on the right side
So the theorem holds for n.
INDUCTIVE HYPOTHESIS: [Choice II: From nto n+ 1]
Assume that the theorem holds for arbitrary n1. Then
n
X
i=1
4i2 = 2n2.
You're Reading a Preview

Unlock to view full version