Powered by Blogger.

Solving a Recursion

Prerequisites: Induction

For those of you who have never heard of it, the Putnam exam is a test for college students (mostly math majors) that universities throughout the country compete in. The test is hard- there are 12 questions (in two sets of 6, for which you get three hours per set), and the median score is 0. I've taken it a few times myself, and I think my record was 2 questions correct, which I was pretty pleased with.

Anyway, a lot of schools have a team that prepares for this test (at Dartmouth, this consisted of a bunch of people gathering for free Raymunto's pizza, which is a surefire way to get folks to show up there), and consequently, you can find a lot of the practice problems on the internet. In fact, you can find archives of past Putnam exams and solutions online, for example, here.

Anyway, the reason I mentioned all this is that I found the following problem in a Putnam practice document from Northwestern:

There are $n$ great circles drawn on the surface of a sphere such that no more than 2 intersect at any point. Into how many regions do the circles divide the surface of the sphere?


Now, I'll get to explaining what a great circle is in a second, but first, I'll explain what made me want to write a post about this problem in the first place. Obviously, the solution must be some function of $n$. Ok, great. But what really #GroundMyGears was that in the solutions in this document, they basically looked at the first few cases, $n=1,2,3,4,...$, guessed the answer, and then proved it was correct by induction. Don't get me wrong- this was all correct and everything, but I just felt like guessing the answer and then proving it works by induction was kind of a cop-out in this case. So I worked out the same answer in what I thought was a more satisfying way, and that's what I'm going to show you here. This method works for other recursions as well, so it may actually be useful to you some day.

Ok, first of all, I just said it, and it's in the title of the post, so what is a recursion? A recursion defines an object in terms of itself.

What???

Ok, maybe best to use an example here, and I promise you'll see what I mean: the factorial of a positive integer $n$, denoted $n!$, is defined as the product of the positive integers 1 through $n$. In symbols, $n! = n(n-1)(n-2)...(3)(2)(1)$, or more succinctly, $n! = \prod_{i=1}^{n}{i}$. Here's where it gets interesting: factorials can be defined in terms of themselves as follows: $$
1! = 1 \\
\forall n > 1, n! = n \cdot (n-1)!
$$ Clearly, this gives the same definition as above, but now we've defined the factorial function in terms of itself, but for smaller values of the input variable. This is crucial in computer science, where we can use this method to specify infinitely many (or more precisely, an arbitrarily large number of) objects in a finite number of steps.

Recursion is also very closely related to induction. Properties of recursively defined functions and sets can often be proved by an induction argument that follows the recursive definition (sentence copy/pasted from Wikipedia, thank you very much). A recursive function definition always needs a base case whose value is specified, and then an inductive definition of the function for greater input values, in terms of the values of the function for smaller inputs.

Hopefully the above got the point across (if not, leave a question in the comments section). Let's shift gears now and talk about great circles.

A great circle of a sphere is a circle drawn on the surface of the sphere, whose center coincides with the sphere's center. All great circles have the same radius and diameter as the sphere itself. Another way to put it is that a great circle is the intersection of a sphere and a plane which passes through its center. These are the largest circles that can be drawn on the surface of a sphere. Smaller circles (called small circles) arise when a plane intersects a sphere and does not pass through its center. In the diagram below, the red circle is a great circle, and the blue one is a small circle:

The equator and meridian are examples of great circles on the surface of the earth. While I'm talking about great circles, it's worth mentioning, though we won't need it in this post, that the shortest path between any two points on the surface of a sphere is the great circle arc (i.e. piece of the great circle) connecting them. It's also worth mentioning (and we will need this fact) that any two great circles intersect at two points (can you see why?).

On that note, let's get back to the question about $n$ great circles on the surface of the sphere. Let's call the number of regions on the surface after we've drawn $n$ great circles $R(n)$. With one circle, the sphere is divided into 2 halves, or hemispheres (hemi- is a prefix that means half, as do demi- and semi- by the way, but for some reason, the word turned out to be hemisphere and not semisphere or demisphere...). So $R(1)=2$.

If we add a second circle, it will intersect the first at 2 points, cutting the existing two regions into 4, so $R(2)=4$. Now, a third great circle will intersect the first two at 2 points each. Remember that the question prohibited an intersection at the existing intersection points (if it hit one, it would hit both), so the third circle again cuts the existing regions each in two, implying $R(3)=8$.

Things get trickier on the fourth circle, which is tougher to picture without a diagram. See the green and red circles in the below diagram, which are the fourth and fifth great circles drawn on the surface after the first 3 black ones:
Note first of all that the fourth circle (and each one thereafter) does not intersect every existing region. The fourth circle intersects 6 of the 8 existing regions, and in fact, since each great circle is the intersection of a plane with the sphere, the fact that the fourth circle hits 6 regions is explained in the post The Plane in ${\Bbb R}^3$- I'll leave it to you to explore the connection there (and it actually does not depend on the angles the first three planes make with each other). So the fourth circle adds 6 new regions (one for each of the 6 it intersected and thus cut into two) so that $R(4)=8+6=14$.

In general, we can see by the same logic that the $n^{\scr th}$ circle intersects each of the existing $n-1$ circles twice. Since none of those intersection points existed before drawing the $n^{\scr th}$ circle (because if one had, then we'd have three circles intersecting at one point, which isn't allowed), there must be $2(n-1)$ intersection points of the $n^{\scr th}$ circle with the original $n-1$ circles.

Also, you can see from the diagram that when we draw the $n^{\scr th}$ circle, each set of two new intersection points breaks the $n^{\scr th}$ circle into an arc which cuts one of the existing $R(n-1)$ regions into two new ones. The number of regions the circle intersects (and thus cuts into two) is $2(n-1)$, because if we walk around the $n^{\scr th}$ circle, there is one region after each of the $2(n-1)$ intersection points with the other circles.

The above two paragraphs give us our recursion: $$
\begin{align}
R(n) &= R(n-1) + 2(n-1), n \geq 2 \tag{1}\\[2mm]
R(1) &= 2 \tag{2}
\end{align}
$$ Note that we need only one initial condition because there is only an $R(n-1)$ term in the recursion equation. If there were also an $R(n-2)$ in there, we'd need both $R(1)$ and $R(2)$ to determine the value of $R$ for all values of $n$. So now that we have our recursion, let's solve the thing. For $n \geq 2$, rearranging $(1)$ gives $$R(n) - R(n-1) = 2(n-1) \tag{3}
$$ Since $(3)$ holds for every $n \geq 2$, we have $$
\begin{align}
R(n-1) - R(n-2) &= 2(n-2) \\[3mm]
R(n-2) - R(n-3) &= 2(n-3) \\[3mm]
\vdots \\[3mm]
R(2) - R(1) &= 2(1)
\end{align}
$$ Therefore: $$
\begin{align}
R(n) &= R(n) + 0 \\[3mm]
&= R(n) + (-R(n-1)+R(n-1)) + (-R(n-2)+R(n-2)) + \cdots + (-R(2)+R(2)) + (-R(1)+R(1)) \\[3mm]
&= (R(n)-R(n-1)) + (R(n-1)-R(n-2)) + \cdots + (R(2)-R(1)) + R(1) \\[3mm]
&\overset{(3)}{=} 2(n-1) + 2(n-2) + \cdots + 2(1) + R(1) \\[3mm]
&\overset{(2)}{=} 2(n-1) + 2(n-2) + \cdots + 2(1) + 2 \\[3mm]
&= \left( 2 \sum_{i=1}^{n-1}{i} \right) + 2 \\[3mm]
&= 2 \left( \dfrac{(n-1)(1+(n-1))}{2} \right) + 2 \tag{$\spadesuit$}\\[3mm]
&= (n-1)n+2 \\[3mm]
&= n^2 - n + 2
\end{align}
$$ where the equality $(\spadesuit)$ is because of the fact that an arithmetic series, i.e. a sum of $N$ terms, the first of which is $a_1$, the last of which is $a_N$, and with the difference between successive terms being a constant, has $\dfrac{N(a_1 + a_N)}{2}$ as its sum. Can you prove why?

So now we've solved for $R(n)$ for every value of $n$ using the recursion equation $(1)$ and the initial condition $(2)$.

I hope you found this interesting and maybe even useful. Thanks for reading, and please post any questions or comments in the comments section.


5 comments:

  1. Oops. This post is complicated. As soon as I see the big big mathematical notations & sigma signs, my head starts spinning infinite circles:)
    Just curious, why math folks (even my friend) always talk in notations, instead of plain simple English?

    //f we add a second circle, it will intersect the first at 2 points, cutting the existing two regions into 4, so R(2)=4//

    How?

    If we draw the circles in concentric fashion, what about the 5th region (the region between those 2 circles, like a Saturn ring)?
    Because the Putnam question says "no more than 2 intersect at any point", which means there can be 0 intersecting points also, right? Sorry, I am confused (as ever)

    ReplyDelete
    Replies
    1. Looks like some one is commenting even before me:)

      To answer your question,
      Your question is based on just a "Circle", but what Greg discusses here is " Great Circle", Both are different.

      Yes, u will have an annular region like Saturn ring, if u draw "any" circle in a parallel fashion.
      Actually u can draw infinite number of "any" circles on a sphere.

      But "Great Circle" is different. A great circle, is when circle's center is the same as sphere's center.
      In your case of saturn ring parallel circles, that center won't coincide with sphere's center.

      Anyways, you can still have the Raymunto's Pizza, Rag:)

      Delete
  2. It's Ramunto's Pizza, not Raymunto's Pizza!

    ReplyDelete
  3. Lovely!
    n(n-1)+2 regions
    Arithmetic series is always fun!

    BTW, congrats on your Putnam score 2:)

    ReplyDelete
  4. //N(a1+aN)/2 as its sum. Can you prove why?//

    Can I try?:)

    Let $d$ be the constant which is the difference between successive terms.
    So, the sum of 1st $n$ terms is
    $S_n = a_1 + (a_1+d) + (a_1+2d) + ... + (a_1+(n-1)d)$

    Let's write this in a reverse fashion now, with the last number $a_n$ and not the first number $a_1$
    $S_n = (a_n-(n-1)d) + (a_n-(n-2)d) + ... + (a_n-2d) + (a_n-d) + a_n$

    Now if we add both the equations, (front to back).. all the (n-1)d 's will cancel out & hence..
    $2S_n = n(a_1 + a_n)$
    which means..
    $S_n = \frac{n(a_1 + a_n)}{2}$

    Am I right, Greg? What abt a free pizza for me?:)

    ReplyDelete