Find the recurrence relation satisfied by $R_n$, where $R_n$ is the number of regions into which the surface of a sphere is divided by $n$ great circles (which are the intersections of the sphere and planes passing through the center of the sphere), if no three of the great circles go through the same point.
I've been trying to find a recurrence relation for this question. I've read the answers on Slader.com and Math.SE, but I can't seem to understand them.
I can tell $f_1=2$, $f_2=4$, $f_3=8$, but other than that, I cannot seem to get $f_4$ (my answer to $f_4$ is $18$, which is wrong), and can't seem to spot the pattern.
I don't understand how the splitting occurs and why it is a summation rather than multiplication. Since it cuts every circle at 2 points does it not split the regions into 2? So we now have twice the number of regions? I don't understand the $2(n-1)$ part as well.
I know it's an old answered question, but I'm asking because unlike how the answerer put it, it is neither obvious nor simple to me.
Thank you very much for your help.
Best Answer
I’ll expand the answer at your Math.SE link; see if that makes it more understandable.
Suppose that you already have $n$ great circles; they have divided the sphere into $R_n$ regions. Now you add an $(n+1)$-st great circle, $C$. Any two distinct great circles must intersect in two points, so $C$ must intersect each of the original $n$ great circles in two points. Let these points be $p_1,p_2,\ldots,p_{2n}$ in order around the great circle $C$.
Now imagine that you start at $p_1$ and walk all the way around $C$, going from $p_1$ to $p_2$ to $p_3$ and so on, finally passing through $p_{2n}$ and finishing back at $p_1$. In the course of this walk you traverse $2n$ segments of $C$: the first is from $p_1$ to $p_2$, the second from $p_2$ to $p_3$, and so on, the $2n$-th and last being from $p_{2n}$ to $p_1$. Each of these segments crosses one of the $R_n$ regions into which the sphere is divided by the original $n$ great circles, and by crossing it, the segment cuts that region into two regions, one to your left as you walk and the other to your right.
The regions through which $C$ does not pass are not affected by the addition of $C$, but each of the regions through which $C$ does pass is cut into $2$ regions. Since $C$ passes through $2n$ regions, this produces a total of $2\cdot2n=4n$ regions adjacent to the great circle $C$: $n$ on the left as you traverse it, and $n$ on your right. The other $R_n-2n$ regions remain unchanged, so you end up with a total of
$$R_{n+1}=(R_n-2n)+4n=R_n+2n$$
regions formed by the original $n$ great circles together with the $(n+1)$-st great circle $C$.