2.5. Recursion and Induction 33

(ii) For every positive integer n,

21

+

22

+ . . . +

2n

=

2n+1

− 2.

(iii) For every positive integer n,

n3

3

+

n5

5

+

7n

15

is an integer.

(iv) For every positive integer n,

4n

− 1 is divisible by 3.

(v) The sequence a0,a1,a2,... defined by a0 = 0, an+1 =

an+1

2

is

bounded above by 1.

Exercise 2.5.5. Recall that, for a binary operation ∗ on a set A,

associativity is defined as “for any x, y, z, (x∗y)∗z = x∗(y ∗z).” Use

induction to prove that for any collection of n elements from A put

together with ∗, n ≥ 3, any grouping of the elements that preserves

order will give the same result.

Exercise 2.5.6. A graph consists of vertices and edges. Each edge

has a vertex at each end (they may be the same vertex). Each vertex

has a degree, which is the number of edge endpoints at that vertex

(so if an edge connects two distinct vertices, it contributes 1 to each

of their degrees, and if it is a loop on one vertex, it contributes 2 to

that vertex’s degree). It is possible to prove without induction that

for a graph the sum of the degrees of the vertices is twice the number

of edges. Find a proof of that fact using

(i) induction on the number of vertices;

(ii) induction on the number of edges.

Exercise 2.5.7. The Towers of Hanoi is a puzzle consisting of a

board with three pegs sticking up out of it and a collection of disks

that fit on the pegs, each with a different diameter. The disks are

placed on a single peg in order of size (smallest on top), and the goal

is to move the entire stack to a different peg. A move consists of

removing the top disk from any peg and placing it on another peg; a

disk may never be placed on top of a smaller disk.

Determine how many moves it requires to solve the puzzle when

there are n disks, and prove your answer by induction.

2.5.2. Recursion. To define a class recursively means to define it

via a set of basic objects and a set of rules, called closure operators,