Hi could some do this question for me I have never derived a recurrence before
For an integer $n \geq 1$, draw $n$ straight lines, such that no two of them are parallel and no three of them intersect in one single point. These lines divide the plane into regions (some of which are bounded and some of which are unbounded). Denote the number of these regions by $R_n$.
Derive a recurrence for the numbers $R_n$ and use it to prove that for $n \geq 1$,
$$ R_n = 1 + n(n+1)/2 $$
Recurrence relation will be
$$a_n = a_{n-1} + n$$
Initial condition, $a_1=2$ (1 line divides the plane in 2 regions)
solving this we will get the result,
$$a_n = 1+n(n+1)/2$$
Explanation:
Let $a_n$ be the number of regions, n lines divide the plane, now when you draw the next $(n+1)th$ line, such that it intersects all other previous drawn lines, new regions formed would be $(n+1)$
(Try intersecting 4th line on previous 3 lines, new regions formed are 3)
so, $(n+1)th$ line will make $n$ new regions each time.
previously we had $a_n$ regions, now the new number of regions formed are
$$a_{n+1} = a_n+(n+1)$$
or simply $$a_n = a_{n-1} + n$$
This is a linear homogeneous recurrence relation of degree 1, you can solve it by recursively, add $n + (n-1) +...+ 3+2+2 = 1+n(n+1)/2$