Try It Now

Work these exercises to see how well you understand this material.


  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.

  2. 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

  3. Let M(n) be the number of multiplications needed to evaluate an nthdegree polynomial. Use the recursive definition of a polynomial expression to define M recursively.


Source: Al Doerr and Ken Levasseur,
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.