Question

Find the recurrence relation satisfied by Rn,where Rn is the number of regions that a plane is divided into by n lines, if no two of the lines are parallel and no three of the lines go through the same point. b) Find Rn using iteration.

Answer 1

Answer:

a) The recursion formula is $R_n = R_{n-1}+n$.

b) $R_n = 1 + \frac{n(n+1)}{2}$.

Step-by-step explanation:

a) Let us explore the recurrence. A plane with only one line is divided in two regions, so $R_1 = 2$. If we add another line under the restrictions of the problem, $R_2 = 4$.

Notice that each line intersects the other n-1 lines, because there are no parallel lines. Assume we have n-1 lines and $R_{n-1}$ regions in the plane. If we add a new one we will have the previous $R_{n-1}$ plus n new regions. Because, for each line crossed by the new one there are a new region. Therefore,

$R_n = R_{n-1}+n$.

b) The method here is to develop the recurrence and find some pattern. Hence, using the formula for $R_n$, $R_{n-1}$ and $R_{n-2}$ we obtain

$R_n = R_{n-1}+n=R_{n-2} + (n-1) + n = R_{n-3}+(n-2) + (n-1) + n.$

Notice that for each step back in the recurrence we add a new term in th sum. If we repeat the procedure n-1 times we will have

$R_n = R_{n-3}+(n-2) + (n-1) + n = R_1 + 2+3+\cdots+(n-2) + (n-1) + n.$

Using that $R_1 = 2$:

$R_n = R_1 + 2+3+\cdots+(n-2) + (n-1) + n = 2 +2+3+\cdots+(n-2) + (n-1) + n.$

Here the smart step is to split the first 2 in 1+1, in order to obtain the sum of the first n natural numbers, and the expression for this last sum it is well known. Therefore,

$R_n = 1 +(1+2+\cdots+ (n-1) + n) = 1+\frac{n(n+1)}{2}.$