## Try It Now

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

### Exercises

- Prove by induction that
*B*(*k*) = 3*k*+ 2*, k*≥0, is a closed-form expression for the sequence*B*in Example 8.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 - Let
*M*(*n*) be the number of multiplications needed to evaluate an*n*degree polynomial. Use the recursive definition of a polynomial expression to define^{th}*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.