Tricky Induction

**tukeywilliams** · June 16th 2007, 11:19 AM

Suppose that $n$ points lie on a circle are all joined in pairs. The points are positioned so that no three joining lines are concurrent in the interior of the circle. Let $a_n$ be the number of regions into which the interior of the circle is divided. Draw diagrams to find $a_n$ is given by the following formula $a_n = n + \binom{n-1}{2} + \binom{n-1}{3} + \binom{n-1}{4} = 1+ \frac{n(n-1)(n^{2}-5n+18)}{24}$ .

I am pretty sure that I can do the induction part. I tried plugging in $n = 2,3$ and the number of regions were 2 and 4. The diagrams also had 2 and 4 regions respectively. But when I plugged in $n = 4$ $a_n = 8$ . However, when I drew it I got $a_n = 9$ .

Here are the circles:

Am I drawing the points wrong in the third circle?

**tukeywilliams** · June 16th 2007, 11:34 AM

actually I think I know what I am doing wrong. I was overconnecting points.

**tukeywilliams** · June 16th 2007, 05:58 PM

Also, I think depending on where you put the points $a_n$ will be different?

**snfitz** · June 16th 2007, 06:49 PM

I believe that the points in your diagrams would lie along the perimeter of the circle, not inside of it. Also, your formula works when each point is connected to every other point, so in your n=4 diagram, there would be a total of 6 lines. Doing that, my n=2,3,4 worked out to the desired number of regions. Hope that helps a little!

**tukeywilliams** · June 16th 2007, 08:49 PM

To prove the inductive step is it as simple as just plugging in $k+1$ for $a_k$ ?

**snfitz** · June 16th 2007, 09:58 PM

I'm actually having difficulty proving this, since I can't seem to figure out how it's true. Have you tried n=6? When I plug it into the formula, I get 31, but when I actually draw it out, I get 30 areas. (I encountered this while exploring the powers of two pattern, did you notice that?) Maybe I'm not clear on the definition of concurrent lines, but I just took that part of the problem to mean that no two lines connected the same two points. Any new thoughts?

**tukeywilliams** · June 16th 2007, 10:46 PM

Here are the drawings I got:

I think the concurrent lines mean that no three lines intersect. I got 31 for $n = 6$

Yeah the pattern was:1,2,4,8,16,31,57,99,163. We might have to use strong induction. But I cant see how $a_{k-1}$ and $a_k$ relate to $a_{k+1}$ . Seeing that there is no pattern, I was wondering if this is valid.

Our induction hypothesis is: $a_{k} = k + \binom{k-1}{2} + \binom{k-1}{3} + \binom{k-1}{4} = 1 + \frac{k(k-1)(k^{2}-5k+18)}{24}$ for $n \leq k$ points joined in pairs. It really doesnt matter if we use strong induction or not, since regular induction is just a special case of strong induction. So our goal is to show that $a_{k} = k + \binom{k-1}{2} + \binom{k-1}{3} + \binom{k-1}{4} = 1 + \frac{k(k-1)(k^{2}-5k+18)}{24}$ $\Rightarrow a_{k+1} = k+1 + \binom{k}{2} + \binom{k}{3} + \binom{k}{4} = 1 + \frac{(k+1)k((k+1)^{2}-5(k+1)+18)}{24}$

So then would it be valid to substitute $k+1$ for $k$ ? I dont think we can do this since we have to use the induction hypothesis.

Is this valid: $a_{k+1} = a_{k} + \frac{1}{6}k^{3} - \frac{1}{2}k^{2}+\frac{4}{3}k$ ?

**tukeywilliams** · June 17th 2007, 12:55 AM

To get $P(k) \Rightarrow P(k+1)$ we need to use the inductive hypothesis. Maybe we have to use the definition of the binomial coefficient: $\binom{n}{r} = \frac{n!}{r!(n-r)!}$ ?

**tukeywilliams** · June 17th 2007, 06:47 AM

anybody know how to prove the inductive step?

**tukeywilliams** · June 17th 2007, 07:39 AM

I have an inkling that strong induction is needed, but cant see the relationships.

**ThePerfectHacker** · June 17th 2007, 09:32 AM

The correct formula is given here.

**tukeywilliams** · June 17th 2007, 10:08 AM

Isnt the formula that I gave also correct?

**tukeywilliams** · June 17th 2007, 01:07 PM

I know why nobody can answer this. This is a very difficult problem I believe.

Thread: Tricky Induction

LinkBack

Thread Tools

Display

Tricky Induction

Point locations and connections

counterexample?

Similar Math Help Forum Discussions

Strong induction vs. structural induction?

Rigorously prove the principle of complete induction from mathematical induction??

Mathemtical Induction Proof (Stuck on induction)

Tricky induction proof

Tricky seperable DE. At least it's tricky to me

Search Tags