Mathematics for Computer Science

5.4. State Machines 151

Exam Problems

Problem 5.13.
Prove by induction:

Xn

iD 0

i^3 D



n.nC1/

2

 2

; 8 n0: (5.17)

using the equation itself as the induction hypothesis,P.n/.

(a)Prove the

base case.nD0/.

(b)Now prove the

inductive step.

Problem 5.14.
SupposeP.n/is a predicate on natural numbers and suppose

8 k: P.k/IMPLIESP.kC2/: (5.18)

ForP’s that satisfy (5.18), some of the assertions belowCan hold for some,
but not all, suchP, other assertionsAlways hold no matter what theP may be,
and someNever hold for any suchP. Indicate which case applies for each of the
assertions and briefly explain why.

(a) 8 n0: P.n/

(b) NOT.P.0//AND 8 n1: P.n/

(c) 8 n0: NOT.P.n//

(d). 8 n100: P.n//AND. 8 n > 100:NOT.P.n///

(e). 8 n100: NOT.P.n///AND. 8 n > 100: P.n//

(f)P.0/IMPLIES 8 n:P.nC2/

(g)Œ 9 n:P.2n/çIMPLIES 8 n: P.2nC2/

(h)P.1/IMPLIES 8 n:P.2nC1/

(i)Œ 9 n:P.2n/çIMPLIES 8 n: P.2nC2/