## 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

SOLUTION
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.

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$?

Conjecture
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
$R_n=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}$

PROOF (by induction)
$n=1$
$R_1=\binom{1}{0}+\binom{1}{1}+\binom{1}{2}$
$=1+1+0$
$=2$
The conjecture is true for $n=1$.

Suppose it is true for $n=k$ for some $k$,
$R_k=\binom{k}{0}+\binom{k}{1}+\binom{k}{2}$
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}{0}=1=\binom{k+1}{0}$

$\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{2k+k^2-k}{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}+\binom{k}{2}=\binom{k+1}{2}$

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

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 )$
$=\binom{k+1}{0}+\binom{k+1}{1}+\binom{k+1}{2}$
The conjecture is true for $n=k+1$. DONE

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