# Try It Now

Site: | Saylor Academy |

Course: | CS202: Discrete Structures |

Book: | Try It Now |

Printed by: | Guest user |

Date: | Wednesday, August 14, 2024, 10:28 AM |

## Description

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.

## Solutions

- Answer:

Basis:*B*(0) = 3*·*0 + 2 = 2, as defined.

Induction: Assume:*B*(*k*) = 3*k*+ 2 for some*k*≥ 0.*B*(*k*+ 1) =*B*(*k*) + 3

= (3*k*+ 2) + 3 by the induction hypothesis

= (3*k*+ 3) + 2

= 3(*k*+ 1) + 2 as desired - 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. - Answer: For
*n*greater than zero,*M*(*n*) =*M*(*n −*1) + 1, and*M*(0) = 0.