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.

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

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

[tex]R_n = R_{n-1}+n[/tex].

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

[tex]R_n = R_{n-1}+n=R_{n-2} + (n-1) + n = R_{n-3}+(n-2) + (n-1) + n.[/tex]

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

[tex]R_n = R_{n-3}+(n-2) + (n-1) + n = R_1 + 2+3+\cdots+(n-2) + (n-1) + n.[/tex]

Using that [tex]R_1 = 2[/tex]:

[tex]R_n = R_1 + 2+3+\cdots+(n-2) + (n-1) + n = 2 +2+3+\cdots+(n-2) + (n-1) + n.[/tex]

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,

[tex]R_n = 1 +(1+2+\cdots+ (n-1) + n) = 1+\frac{n(n+1)}{2}.[/tex]