Mathematics for Computer Science

Chapter 5 Induction150

Prove the Distributive Law of intersection over the union ofnsets by induction:

A\

[n

iD 1

BiD

[n

iD 1

.A\Bi/: (5.15)

Hint:Theorem 4.1.2 gives thenD 2 case.

Problem 5.12.
Here is an interesting construction of a geometric object known as theKoch snowflake.
Define a sequence of polygonsS 0 ;S 1 recursively, starting withS 0 equal to an equi-
lateral triangle with unit sides. We constructSnC 1 by removing the middle third
of each edge ofSnand replacing it with two line segments of the same length, as
illustrated in Figure 5.13.

Figure 5.13 S 0 ;S 1 ;S 2 andS 3.

Letanbe the area ofSn. Observe thata 0 is just the area of the unit equilateral
triangle which by elementary geometry is

p

3=4.

Prove by induction that forn 0 , the area of thenthsnowflake is given by:

anDa 0



8

5

3

5



4

9

n

: (5.16)