Mathematics for Computer Science

5.4. State Machines 155

Then by strong induction hypothesis, Even.n/and Even.n1/are true, that is,
F.n/andF.n1/are both even. But by the defining equation (5.21),F.nC1/
equals the sum,F.n/CF.n1/, of two even numbers, and so it is also even. This
proves Even.nC1/as required.
Hence,F.m/is even for allm 2 Nby the Strong Induction Principle.


Problem 5.20.
Alice wants to prove by induction that a predicate,P, holds for certain nonnegative
integers. She has proven that for all nonnegative integersnD0;1;:::

P.n/IMPLIESP.nC3/:
(a)Suppose Alice also proves thatP.5/holds. Which of the following proposi-
tions can she infer?

1.P.n/holds for alln 5

2.P.3n/holds for alln 5

3.P.n/holds fornD8;11;14;:::

4.P.n/does not hold forn < 5

5. 8 n: P.3nC5/


6. 8 n > 2: P.3n1/
   7.P.0/IMPLIES 8 n: P.3nC2/
   8.P.0/IMPLIES 8 n: P.3n/

(b)Which of the following could Alice prove in order to conclude thatP.n/holds
for alln 5?

1.P.0/

2.P.5/

3.P.5/andP.6/

4.P.0/,P.1/, andP.2/

5.P.5/,P.6/, andP.7/

6.P.2/,P.4/, andP.5/

7.P.2/,P.4/, andP.6/

8.P.3/,P.5/, andP.7/