School

University of MarylandDepartment

Computer ScienceCourse Code

CMSC 250Professor

Jason FilippouLecture

1This

**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 justiﬁcation must be very detailed.

•Proofs must explicitly state the Inductive Hypothesis. It is not suﬃcient to say “Assume true

for n” (although in real life it is suﬃcient). The book always introduces a predicate P(k) for

the statement to be proved. We do not. It is not suﬃcient to write “P(k)” for the IH.

•If a proof is by Weak Induction the Induction Hypothesis must reﬂect 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 n≥1, Pn

i=1 4i−2 = 2n2.

BASE CASE: Let n= 1. The summation gives

n

X

i=1

4i−2 =

1

X

i=1

4i−2 = 4 ·1−3 = 2 .

The formula gives

2n2= 2 ·12= 2 .

The two values are the same.

•INDUCTIVE HYPOTHESIS [Choice I: From n−1to n]:

Assume that the theorem holds for n−1 (for arbitrary n > 1). Then

n−1

X

i=1

4i−2 = 2(n−1)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 4i−2 = Pn−1

i=1 i+ (4n−2) by splitting sum

= 2(n−1)2+ (4n−2) by IH

= 2(n2−2n+ 1) + (4n−2) by algebra

= 2n2.by algebra

So the theorem holds for n.

– INDUCTIVE STEP: [Choice Ib: Start with the induction hypothesis.]

Pn−1

i=1 4i−2 = 2(n−1)2by IH

Pn−1

i=1 4i−2 + (4n−2) = 2(n−1)2+ (4n−2) adding 4n−2 to both sides

Pn

i=1 4i−2 = 2(n2−2n+ 1) + (4n−2) 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 n≥1. Then

n

X

i=1

4i−2 = 2n2.

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

Unlock to view full version