Friday, April 29, 2011

How many regions (open or closed) can n straight lines give at the maximum?

Let f(n) denote the number of regions for n lines no three of which coincide in one point. This latter condition will guarantee the maximum. Obviously, f(0)=1, f(1)=2, f(2)=4, f(3)=7, etc.

Now, given n-1 lines, there are already f(n-1) regions. With the introduction of the n-th line, imagine the points of intersection of the pre-existing n-1 lines fall on one side of the n-th line. So, on one side of the n-th line -- where the points of intersection lie -- you still have f(n-1) regions, whereas on the other side of the n-th line, you now have n regions. So, for these n lines before us, the total number f(n) of regions must be equal to f(n-1)+n.

So, f(n)=f(n-1)+n. With the initial condition(s) given earlier, this gives us f(n)=1+n(n+1)/2.

we can use induction to prove the same,

Base case:
if n = 1, regions (planes) = 2

Induction Hypothesis:
Addition of a new line adds

regions to the regions formed by previous
lines, i.e.

f(n) = n + f(n-1)

Upon simplifying the above, we get f(n) = 1 + n(n+1)/2

No comments: