Try It Now

Exercises

1. Prove by induction that B(k) = 3k + 2, k ≥0, is a closed-form expression for the sequence B in Example 8.2.2.
   
   
3. Given k lines (k ≥0) on a plane such that no two lines are parallel and no three lines meet at the same point, let P (k) be the number of regions into which the lines divide the plane (including the infinite ones (see Figure 8.2.3). Describe how the recurrence relation P(k) = P (k − 1) + k can be derived. Given that P(0) = 1, determine P(5).
   
   
   Figure 8.2.3 A general configuration of three lines
   
   
5. Let M(n) be the number of multiplications needed to evaluate an n^thdegree polynomial. Use the recursive definition of a polynomial expression to define M recursively.

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.

Solutions

1. Answer:
   
   Basis: B(0) = 3 · 0 + 2 = 2, as defined.
   
   Induction: Assume: B(k) = 3k + 2 for some k ≥ 0.
   
   B(k + 1) = B(k) + 3
   
   = (3k + 2) + 3 by the induction hypothesis
   
   = (3k + 3) + 2
   
   = 3(k + 1) + 2 as desired
   
   
3. Answer: Imagine drawing line k in one of the infinite regions that it passes through. That infinite region is divided into two infinite regions by line k. As line k is drawn through every one of the k − 1 previous lines, you enter another region that line k divides. Therefore k regions are divided and the number of regions is increased by k. From this observation, we get P(5) = 16.
   
   
5. Answer: For n greater than zero, M(n) = M(n − 1) + 1, and M(0) = 0.