Mathematics for Computer Science

7.5. Induction in Computer Science 177

(a)Write out (using angle brackets and labelsbintree,leaf, etc.) the binary-2PTG,
G, pictured in Figure 7.1.

The value of flatten.G/forG 2 binary-2PTG is the sequence of labels inLof
the leaves ofG. For example, for the binary-2PTG,G, pictured in Figure 7.1,

flatten.G/D.win;lose;win;win/:
(b)Give a recursive definition of flatten. (You may use the operation ofconcate-
nation(append) of two sequences.)

(c)Prove by structural induction on the definitions of flatten and size that

2 
length.flatten.G//DjGjC1: (7.23)

Homework Problems

Problem 7.6.

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.scdott/D#c.s/C#c.t/:

Problem 7.7.
Fractals are example of a mathematical object that can be defined recursively. In
this problem, we consider the Koch snowflake. Any Koch snowflake can be con-
structed by the following recursive definition.

 base case: An equilateral triangle with a positive integer side length is a

Koch snowflake.

 constructor case: LetKbe a Koch snowflake, and letlbe a line segment

on the snowflake. Remove the middle third ofl, and replace it with two line

segments of the same length as is done in Figure 7.2

The resulting figure is also a Koch snowflake.