Tough ( ? ) Induction Question (1 Viewer)

[GaDaMIt]

Prove that the greatest number of regions that n straight lines can divide a circle is 1/2 . (n² + n + 2), n >= 1

 

[Riviet]

Imagine a circle with k lines and therefore 1/2.(k²+k+2) regions (by assumption).

We're required to prove maximum number of regions is:

1/2.{(k+1)² + (k + 1) + 2} = 1/2.(k² + 3k + 4)

We want the (k+1)th line to create a maximum number of extra regions and this occurs when this (k+1)th line is drawn so that intersects each of the k lines. This creates an extra k+1 regions.

Therefore total maximum number of regions made by k+1 lines is equal to

1/2.(k²+k+2) + k + 1 = 1/2.(k²+k+2) + 1/2.(2k+2)

= 1/2.(k² + k + 2k + 2 + 2)

= 1/2.(k² + 3k + 4) #

 

[Affinity]

Strictly speaking you should also show that it is possible to achieve maximum intersection, it's not obvious that this could be done in a circle when there are many lines