Mathematics for Computer Science

5.4. State Machines 147

False Theorem.For alln 0 ,

2 C 3 C 4 C


CnD

n.nC1/

2

Proof. We use induction. LetP.n/be the proposition that 2 C 3 C 4 C


CnD
n.nC1/=2.
Base case:P.0/is true, since both sides of the equation are equal to zero. (Recall
that a sum with no terms is zero.)
Inductive step:Now we must show thatP.n/impliesP.nC1/for alln 0. So
suppose thatP.n/is true; that is, 2 C 3 C 4 C


CnDn.nC1/=2. Then we can
reason as follows:

2 C 3 C 4 C


CnC.nC1/DΠ2 C 3 C 4 C


CnçC.nC1/

D

n.nC1/

2

C.nC1/

D

.nC1/.nC2/

2

Above, we group some terms, use the assumptionP.n/, and then simplify. This
shows thatP.n/impliesP.nC1/. By the principle of induction,P.n/is true for
alln 2 N. 

Where exactly is the error in this proof?

Homework Problems

Problem 5.8.
The Fibonacci numbersF.0/;F.1/;F.2/;:::are defined as follows:

F.0/WWD0;

F.1/WWD1;

F.n/WWDF.n1/CF.n2/ forn2:

Thus, the first few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, and 21. Prove by
induction that for alln 1 ,

F.n1/
F.nC1/F.n/^2 D.1/n: (5.9)

Problem 5.9.
For any binary string, ̨, let num. ̨/be the nonnegative integer it represents in
binary notation. For example, num. 10 /D 2 , and num. 0101 /D 5.