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,
