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

a) The recursion formula is
`R_n = R_(n-1)+n`.

b)
`R_n = 1 + (n(n+1))/(2)`.

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+(n(n+1))/(2).`