Mathematics for Computer Science

6.5. Induction in Computer Science 195

Definition. The set RAF ofrational functionsof one real variable is the set of
functions defined recursively as follows:
Base cases:

 The identity function, id.r/WWDrforr 2 R(the real numbers), is an RAF,

 any constant function onRis an RAF.

Constructor cases:Iff;gare RAF’s, then so isf ~g, where~is one of the
operations

1. addition,C,


2. multiplication,
   , and


3. division=.

(a)Prove by structural induction that RAF is closed under composition. That is,
using the induction hypothesis,

P.h/WWD8g 2 RAF:hıg 2 RAF; (6.26)

prove thatP.h/holds for allh 2 RAF. Make sure to indicate explicitly

each of the base cases, and

each of the constructor cases.Hint:One proof in terms of~covers all three

cases.

(b)Briefly indicate where a proof would break down using the very similar induc-
tion hypothesis
Q.g/WWD8h 2 RAF:hıg 2 RAF:

Problems for Section 6.2

Practice Problems

Problem 6.12.
Define the setsF 1 andF 2 recursively:

 F 1 :

• 52 F 1 ,


• ifn 2 F 1 , then5n 2 F 1.