Multi-Page Printing

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,