Regions in The Plane

With zero line the plane is in one piece (or region). One line cuts the plane into 2 regions. Two lines (not parallel) cut the plane into 4 regions. Find the number of regions formed by drawing n lines in the plane such that none of them are parallel and that no three lines intersect at a point.
Source: Julia Robinson Mathematics Festival

It is easy to see that 3 lines cut the plane into 7 regions and that 4 lines cut the plane into 11 regions as shown in the figures below.

It is harder to show a figure with 5 lines, but you can try and convince yourself that 5 lines will cut the plane into 16 regions. We tabulate the results in the following table
How many regions will a sixth line create? That depends on how many new regions the sixth line will add to the existing 16 regions. We know that the sixth line intersects the 5 existing lines at 5 different points as illustrated in the following diagram.
These 5 intersection points divide the sixth line into 6 segments. Each of those segments cuts one of the existing regions in half. Thus, the sixth line adds 6 new regions to the existing count of 16 making a total of 22 regions. We can now fill in the table as follows

Let R_n represent the number of regions formed by drawing n lines. We have just discovered an important recursive equation:
R_n=R_{n-1}+n        (1)
This recursive equation will help us find a closed-form formula for R_n. But before doing that let’s take a look at the Pascal triangle which reveals a remarkable relationship that we can exploit.

Reading from left to right
The zero diagonal: 1,1,1,1,1,1,1,1
The first diagonal: 1,2,3,4,5,6,7
The second diagonal: 1,3,6,10,15,21

If we add the entries of the zero, first, and second diagonals, we obtain the following results
Row 0: 1+0+0=1 (the Pascal triangle contains no zeros; we fill them in for completeness)
Row 1: 1+1+0=2
Row 2: 1+2+1=4
Row 3: 1+3+3=7
Row 4: 1+4+6=11
Row 5: 1+5+10=16
Row 6: 1+6+15=22
The additions yield the number of regions in our small table! But, is it true for any n?

We denote the k^{th} entry in the n^{th} row of the Pascal triangle by \binom{n}{k} the number of ways of selecting k objects from a collection of n objects. For example, referring to row 6
\binom{6}{0}=1;\;\binom{6}{1}=6;\binom{6}{2}=15;\;\binom{6}{3}=20, and so on.

We formulate the following conjecture

PROOF (by induction)
The conjecture is true for n=1.

Suppose it is true for n=k for some k,
We want to show that is also true for n=k+1.

Applying Eq. (1) to n=k+1 we have
R_{k+1}=R_k+\left (k+1\right )
=\binom{k}{0}+\binom{k}{1}+\binom{k}{2}+\left (k+1\right )
We are going to investigate the terms of the right-hand side of the above equation and show that it is equal to \binom{k+1}{0}+\binom{k+1}{1}+\binom{k+1}{2}.


\binom{k}{1}+\binom{k}{2}=\frac{k!}{1!\left (k-1\right )!}+\frac{k!}{2!\left (k-2\right )!}

=\frac{k\left (k-1\right )!}{\left (k-1\right )!}+\frac{k\left (k-1\right )\left (k-2\right )!}{2\left (k-2\right )!}
=k+\frac{k\left (k-1\right )}{2}
=\frac{k^2+k}{2}        (2)

\binom{k+1}{2}=\frac{\left (k+1\right )!}{2!\left (k+1-2\right )!}

=\frac{\left (k+1\right )\left (k\right )\left (k-1\right )!}{2\left (k-1\right )!}
=\frac{\left (k+1\right )k}{2}
=\frac{k^2+k}{2}        (3)

Comparing Eq. (2) and (3) we conclude that

\binom{k+1}{1}=\frac{\left (k+1\right )!}{1!\left (k+1-1\right )!}
=\frac{\left (k+1\right )\left (k\right )!}{k!}

Pulling all the pieces together we have
R_{k+1}=R_k+\left (k+1\right )
=\binom{k}{0}+\binom{k}{1}+\binom{k}{2}+\left (k+1\right )
The conjecture is true for n=k+1. DONE

Answer: R_n=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}


About mvtrinh

Retired high school math teacher.
This entry was posted in Problem solving and tagged , , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s