Chapter 7 Recursive Data Types174
7.5 Induction in Computer Science
Induction is a powerful and widely applicable proof technique, which is why we’ve
devoted two entire chapters to it. Strong induction and its special case of ordinary
induction are applicable to any kind of thing with nonnegative integer sizes –which
is an awful lot of things, including all step-by-step computational processes.
Structural induction then goes beyond natural number counting by offering a
simple, natural approach to proving things about recursive data types and recursive
computation. This makes it a technique every computer scientist should embrace.
Problems for Section 7.1
Class Problems
Problem 7.1.
Prove that for all stringsr;s;t 2 A
.rs/tDr.st/:
Problem 7.2.
Thereversalof a string is the string written backwards, for example, rev.abcde/D
edcba.
(a)Give a simple recursive definition of rev.s/based on the recursive defini-
tion 7.1.1 ofs 2 Aand using the concatenation operation 7.1.3.
(b)Prove that
rev.st/Drev.t/rev.s/;
for all stringss;t 2 A.
Problem 7.3.
The Elementary 18.01 Functions (F18’s) are the set of functions of one real variable
defined recursively as follows:
Base cases:
The identity function, id.x/WWDxis an F18,
any constant function is an F18,
the sine function is an F18,
