8.13. References 299
Problem 8.40.
We define the sequence of numbers
anD(
1; forn 3 ,
an 1 Can 2 Can 3 Can 4 ; forn > 3.Usestrong inductionto prove that remainder.an;3/D 1 for alln 0.Problems for Section 8.8
Exam Problems
Problem 8.41.
Definition.The set,P, of single variable integer polynomials can be defined re-
cursively:
Base cases:
the identity function, IdZ.x/WWDxis inP. for any integer,m, the constant function,cm.x/WWDmis inP.Constructor cases. Ifr;s 2 P, thenrCsandrs 2 P.
Prove by structural induction that for allq 2 P,jk .modn/ IMPLIES q.j/q.k/ .modn/;for all integersj;k;nwheren > 1.
Be sure to clearly state and label your Induction Hypothesis, Base case(s), and
Constructor step.
Problems for Section 8.9
Practice Problems
Problem 8.42.
(a)Given inputsm;n 2 ZC, the Pulverizer will producex;y 2 Zsuch that: