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.

Answer 1

1. Take a look at the pictures attached.

2.

i) the first line divides the plane into 2 regions

ii) the second line adds 2 more regions so we have 4 in total.

iii) the third line adds 3 more regions, so 4+3=7 regions

iv) the fourth line adds 4 more regions.

so the
`n^(th)` line adds n more regions to the ones created by the previous n-1 lines.

3.


`r_1=2`


`r_2=2+2=4`


`r_3=4+3=7`


`r_4=7+4=11`


`r_n=r_n_-_1+n`

So the recurrence relation is


`r_1=2`

`r_n=r_n_-_1+n`