Mathematical Induction - Stanford University

Mathematical Induction

Part Two

Announcements

Problem Set 1 due Friday, October 4 at the start of class.

Problem Set 1 checkpoints graded, will be returned at end of lecture.

Afterwards, will be available in the filing cabinets in the Gates Open Area near the submissions box.

The principle of mathematical induction states that if for some P(n) the following hold:

If it starts true...

P(0) is true

and

...and it stays true...

For any n , we have P(n) P(n + 1)

then

...then it's

always true.

For any n , P(n) is true.

n-1

Theorem: For any natural number n, 2i=2n-1 i=0

Proof: By induction. Let P(n) be n-1 P(n) 2i=2n-1 i=0 For our base case, we need to show P(0) is true, meaning that -1 2i=20-1 i=0 Since 20 ? 1 = 0 and the left-hand side is the empty sum, P(0) holds.

For the inductive step, assume that for some n , that P(n)

holds, so

n-1

2i=2n-1

i=0

We need to show that P(n + 1) holds, meaning that

n

2i=2n+1-1

i=0

To see this, note that

n

n-1

2i=( 2i)+2n=2n-1+ 2n=2(2n)-1=2n+1-1

i=0

i=0

Thus P(n + 1) holds, completing the induction.

Induction in Practice

Typically, a proof by induction will not explicitly state P(n).

Rather, the proof will describe P(n) implicitly and leave it to the reader to fill in the details.

Provided that there is sufficient detail to determine

what P(n) is, that P(0) is true, and that whenever P(n) is true, P(n + 1) is true,

the proof is usually valid.

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download