Consider n circles in the plane such that each intersects every other, and no three circles met at a point. I need to find a recurrence for the number of regions formed then solve the recurrence.
I started by diving the plane into rn regions. I then added a new circle and tried figuring out how many new regions that added to get an idea but struggle with the concept.
Hint: Suppose you have an arrangement of $n$ circles, and you add a new circle, $C$. For each intersection point of $C$ with a previous circle, one of the previous regions will be split in two (if this is unclear, look at some small examples). Therefore, if $r_n$ is the number of regions, you have $$ r_{n+1}=r_n+\text{# of intersections of $C$ with previous circles}. $$ All that is left is to count the number of intersections.
You can take cue from Venn diagram. Take this for $3$ circles as an example.
Every circle is getting divided into $3$ regions but only one region of each circle is not shared. So that gives you $3$ regions that are not shared.
Then the next $3$ are shared between each of the two circles.
The last one is shared among all of them and that is only one.
So while there are $3$ regions for each circle, there are only $7$ different regions in total.
Similarly for $4$ circles, you get $13$ different regions.
$a(1) = 1$
$a(2) = a(1) + 2 \times 1 = 3$
$a(3) = a(2) + 2 \times 2 = 7$
$a(4) = a(3) + 2 \times 3 = 13$
$a(n+1) = a(n) + 2n$
It translates to $n(n-1) + 1$ regions for $n$ intersecting circles.
