0

Find a recurrence relation for the number of regions created by n mutually intersecting circles on a piece of paper (no three circles have a common intersection point).

I need help understanding the answer to this

My work:

So after looking a while on firefox to help me figure this out. I've eventually found that the number of regions for the problem is

$n^2-n+2$ which I think is because of Euler's formula (r = e - v + 2). Am I incorrect? I'm not sure why it's $n^2$ can someone please explain?

I know the above is right for the number of regions because when I test with $n=2, n=3, n=4$ I get $ r = 4, r=8, r=14$ which when I double check by drawing the circles manually and seeing how many regions there are, I get the answers above.

so then I've found online that the recurrence relation to be $a_n=a_{n-1}+2(n-1)$ which is equivalent to $a_n=n^2-n+2$

But I don't know why this is.

Does $a_{n-1}$ represent the previous regions of $n-1$ circles? and does $2(n-1)$ represent the new regions added with each new circle?

Is the proper answer just $a_n=n^2-n+2$?

I'd really like to learn why $a_n=a_{n-1}+2(n-1)$ works and is (probably) the answer? In order to improve my understanding.

1 Answers1

1

Consider n mutually intersecting circles and no three have common intersecting points. This implies that any two will have exclusive 1/2 point of intersection.

If we take those two circles and pass a circle through both of them such that none of those two points lies on the third circle, we get 2 new regions, one with first and one with the second circle. For n mutually intersecting circles, there will be n-1 pairs of such two circles (as we can choose only those which are intersecting to each other). So total regions that can be formed are 2*(n-1)

Hence U(n+1) = U(n) + 2*(n-1)

Mihir Okte
  • 11