91Ó°ÊÓ

Give a recursive definition of a) the set of even integers. b) the set of positive integers congruent to 2 modulo 3 . c) the set of positive integers not divisible by 5 .

In Exercises 29 and \(30, H_{n}\) denotes the \(n\) th harmonic number. Prove that \(H_{2^{n}} \leq 1+n\) whenever \(n\) is a nonnegative integer.

Let \(S\) be the subset of the set of ordered pairs of integers defined recursively by Basis step: \((0,0) \in S\) . Recursive step: If \((a, b) \in S,\) then \((a, b+1) \in S\) \((a+1, b+1) \in S,\) and \((a+2, b+1) \in S\) a) List the elements of \(S\) produced by the first four ap- plications of the recursive definition. b) Use strong induction on the number of applications of the recursive step of the definition to show that \(a \leq 2 b\) whenever \((a, b) \in S .\) c) Use structural induction to show that \(a \leq 2 b\) whenever \((a, b) \in S .\)

Use mathematical induction to show that a rectangu- lar checkerboard with an even number of cells and two squares missing, one white and one black, can be covered by dominoes.

Use the well-ordering property to show that if \(x\) and \(y\) are real numbers with \(x1 /(y-x)\) . Then show that there is a rational number \(r\) with denominator \(A\) between \(x\) and \(y\) by looking at the numbers \(\lfloor x\rfloor+ j / A,\) where \(j\) is a positive integer.]

Give a recursive definition of the set of bit strings that are palindromes.

Give a recursive algorithm for tiling a \(2^{n} \times 2^{n}\) checkerboard with one square missing using right triominoes.

Use a merge sort to sort 4, 3, 2, 5, 1, 8, 7, 6 into increasing order. Show all the steps used by the algorithm.

Use mathematical induction in Exercises \(38-46\) to prove results about sets. Prove that a set with \(n\) elements has \(n(n-1) / 2\) subsets containing exactly two elements whenever \(n\) is an integer greater than or equal to \(2 .\)

In Exercises 47 and 48 we consider the problem of placing towers along a straight road, so that every building on the road receives cellular service. Assume that a building receives cellular service if it is within one mile of a tower. Devise a greedy algorithm that uses the minimum number of towers possible to provide cell service to \(d\) buildings located at positions \(x_{1}, x_{2}, \ldots, x_{d}\) from the start of the road. [Hint: At each step, go as far as possible along the road before adding a tower so as not to leave any buildings without coverage.]