Mathematics for Computer Science

6.4. Strong Induction vs. Induction vs. Well Ordering 139

So why three methods? Well, sometimes induction proofs are clearer because
they don’t require proof by contradiction. Also, induction proofs often provide
recursive procedures that reduce handling large inputs to handling smaller ones.
On the other hand, Well Ordering can come out slightly shorter and sometimes
seem more natural (and less worrisome to beginners).
So which method should you use? —whichever you find easier! But whichever
method you choose, be sure to state the method up front to help a reader follow
your proof.

Problems for Section 6.1

Class Problems

Problem 6.1.
Use induction to prove that

13 C 23 C


Cn^3 D



n.nC1/

2

 2

: (6.6)

for alln 1.
Remember to formally

1. Declare proof by induction.


2. Identify the induction hypothesisP.n/.


3. Establish the base case.


4. Prove thatP.n/)P.nC1/.


5. Conclude thatP.n/holds for alln 1.

as in the five part template.

Problem 6.2.
Prove by induction onnthat

1 CrCr^2 C


CrnD

rnC^1  1

r 1

for alln 2 Nand numbersr¤ 1.