Chapter 6 Recursive Data Types192
Homework Problems
Problem 6.6.
Letm;nbe integers, not both zero. Define a set of integers,Lm;n, recursively as
follows:
Base cases:m;n 2 Lm;n. Constructor cases: Ifj;k 2 Lm;n, then1. j 2 Lm;n,
2.jCk 2 Lm;n.LetLbe an abbreviation forLm;nin the rest of this problem.
(a)Proveby structural inductionthat every common divisor ofmandnalso di-
vides every member ofL.
(b)Prove that any integer multiple of an element ofLis also inL.(c)Show that ifj;k 2 Landk¤ 0 , then rem.j; k/ 2 L.(d)Show that there is a positive integerg 2 Lwhich divides every member ofL.
Hint:The least positive integer inL.
(e)Conclude thatgDGCD.m;n/forgfrom part (d).Problem 6.7.
Definition.Define the number, #c.s/, of occurrences of the characterc 2 Ain the
stringsrecursively on the definition ofs 2 A:
base case: #c./WWD 0.
constructor case:
#c.ha;si/WWD(
#c.s/ ifa¤c;
1 C#c.s/ ifaDc:Prove by structural induction that for alls;t 2 Aandc 2 A#c.st/D#c.s/C#c.t/: