## Exercises #### Section B.1 1. Use induction to verify the candidate solution to each of the following recurrence equations. 1. *tn* = 4*t**n* − 1 for *n* > 1 *t*1 = 3 The candidate solution is *tn* = 3(4*n* − 1). 2. *tn* = *t**n* − 1 + 5 for *n* > 1 *t*1 = 2 The candidate solution is *t**n* = 5*n* − 3. 3. *t**n* = *t**n* − 1 + *n* for *n* > 1 *t*1 = 1 The candidate solution is *tn* = 3 (4*n*-1) 4. *t**n* = *t**n* − 1 + *n*2 for *n* > 1 *t*1 = 1 The candidate solution is  5.  *t*1 = ½ The candidate solution is  6. *t**n* = 3*t**n* − 1 + 2*n* for *n* > 1 *t*1 = 1 The candidate solution is *t**n* = 5 (3*n* − 1) − 2*n* + 1. 7. *t**n* = 3*t**n*/2 + *n* for *n* > 1, *n* a power of 2 *t*1 = ½ The candidate solution is  8. *t**n* = *nt**n* − 1 for *n* > 0 *t*0 = 1 The candidate solution is *tn* = *n*!. 2. Write a recurrence equation for the *n*th term of the sequence 2, 6, 18, 54, …, and use induction to verify the candidate solution *sn* = 2 (3*n*-1). 3. The number of moves (*mn* for *n* rings) needed in the Towers of Hanoi problem (see Exercise 17 in [Chapter 2](LiB0014.html#141)) is given by the following recurrence equation  Use induction to show that the solution to this recurrence equation is *mn* = 2*n* - 1. 4. The following algorithm returns the position of the largest element in the array *S*. Write a recurrence equation for the number of comparisons *tn* needed to find the largest element. Use induction to show that the equation has the solution *tn* = *n* - 1. ``` index max_position (index low, index high) { index position; if (low == high) return low; else{ position = max_position (low + 1, high); if (S[low] > S[position]) position = low; return position; } } ``` The top-level call is *max\_position* (1, *n*). 5. The ancient Greeks were very interested in sequences resulting from geometric shapes such as the following traingular numbers:  Write a recurrence equation for the *n*th term in this sequence, guess a solution, and use induction to verify your solution. 6. Into how many regions do *n* lines divide a plane so that every pair of lines intersect, but no more than two lines intersect at a common point? Write a recurrence equation for the number of regions for *n* lines, guess a solution for your equation, and use induction to verify your solution. 7. Show that  is the solution to the following recurrence equation:  8. Write and implement an algorithm that computes the value of the following recurrence, and run it using different problem instances. Use the results to guess a solution for this recurrence, and use induction to verify to your solution.  #### Section B.2 1. Indicate which recurrence eqations in the problems for [Section B.1](LiB0102.html#1371) fall into each of the following categories. 1. Linear equations 2. Homogeneous equations 3. Equations with constant coefficients 2. Find the characteristic equations for all of the recurrence equations in [Sections B.1](#ap-blev3sec1) that are linear with constant coefficients. 3. Show that if *f* (*n*) and *g* (*n*) are both solutions to a linear homogeneous recurrence equation with constant coefficients, then so is *c* × *f* (*n*) + *d × g* (*n)*, where *c* and *d* are constants. 4. Solve the following recurrence equations using the characteristic equation. 1.  2.  3.  4.  5. Complete the solution to the recurrence equation given in [Example B.15](LiB0103.html#1410). 6. Complete the solution to the recurrence equation given in [Example B.16](LiB0103.html#1412). 7. Solve the following recurrence equations using the characteristic equation. 1.  2.  3.  4.  8. Complete the solution to the recurrence equation given in [Example B.17](LiB0103.html#1414). 9. Show that the recurrence equation  can be written as  10. Solve the recurrence equation in Exercise 17. The solution gives the number of derangements (nothing is in its right place) of *n* objects. 11. Solve the following recurrence equations using the characteristic equation. 1.  2.  3.  4.  5.  #### Section B.3 1. Solve the recurrence equations in Exercise 1 using the substitution method. #### Section B.4 1. Show that 1. *f* (*n*) = *n*3 is a strictly increasing function. 2. *g* (*n*) = 2*n*3 - 6*n*2 is an eventually nondecreasing function. 2. What can we say about a function *f* (*n*) that is both nondecreasing and nonincreasing for all values of *n*? 3. Show that the following functions are smooth. 1. *f* (*n*) = *n* lg *n* 2. *g* (*n*) = *nk*, for all *k* ≥ 0. 4. Assuming in each case that *T* (*n*) is eventually nondecreasing, use [Theorem B.5](LiB0105.html#1438) to determine the order of the following recurrence equations. 1.  2.  3.  5. Assuming in each case that *T* (*n*) is eventually nondecreasing, use [Theorem B.6](LiB0105.html#1443) to determine the order of the following recurrence equations: 1.  2.  6. We know that the recurrence  has solution  in the case *a* > *c*, provided that *g* (*n*) ∊ Θ (*n*). Prove that the recurrence has the same solution if we assume that