Circles chords and number of regions

[DanaAJames]

What is the maximum number of regions into which n chords can divide a circle?


I have gotten all my data, and I am having trouble with writing the equation.


I notice that the first difference is not constant, but the second difference is. The second difference is +1. I know that this is a quadratic equation.

I believe the equation is r=(n(n +1))/2, if r=maximum number of regions. However, using that equation I am off by 1. Where am I going wrong? Can someone walk me through how to write the equation correctly?

 

[ksdhart]

The formula you came up with is almost correct, as that is the sum of the first n integers. However, you're off by 1 with that formula, because you started with r(0) = 1, and added 1, then added 2, etc. Think about this:

0 + 1 + 2 + 3 + ... + n = 1/2 * n * (n+1)
1 + 1 + 2 + 3 + ... + n = 1 + [1/2 * n * (n+1)]

 

[DanaAJames]

Okay, so the equation is really r=(1/2)n²+n+2). Correct me if I'm wrong, but this is because the starting value f(1)=2, so f(2)=2+f(1). So then f(n)=2+f(n)?

 

[ksdhart]

I could be wrong here, but it seems like you're starting to doubt your own answer. The starting value is when you have zero chords. The circle is then "divided" into just 1 region. When you add the first chord, the maximum number of regions increases by 1, so f(1) = 1 + f(0). When you add a second chord, the maximum number of regions increases by 2, so f(2) = 2 + f(1). When you add a third chord, the maximum number of regions increases by 3, so f(3) = 3 + f(2). Do you notice a pattern?

 

[daon2]

This might be easier to visualize in the plane, instead of a circle. Given n lines, you can draw a new line which crosses them each once. If they are all independent (no single point is a point of intersection to more than two lines), you will create a new partition having n+1 additional pieces. Try it for n=2, n=3, n=4. This can be proven by induction.

If P(n) is the number of pieces formed by drawing the nth line, then the increase is n+1, so, f(n+1)=f(n)+n+1. Since P(0)=1, we have

P(1)=P(0)+1 = 2
P(2)=P(1)+2 = 4
P(3)=P(2)+3 = 7

etc

Now notice P(n)-P(n-1)=n. Then

$\displaystyle \displaystyle P(N)-P(0) = \sum_{n=1}^{N} (P(n) - P(n-1)) = \sum_{n=1}^{N} n = \dfrac{N(N+1)}{2}$

(if this is unclear, consider: [P(3)-P(2)]+[P(2)-P(1)]+[P(1)-P(0)])

So

$\displaystyle P(N) = P(0) + \dfrac{N(N+1)}{2}$