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,
Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2012 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.