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 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 represent the number of regions formed by drawing lines. We have just discovered an important recursive equation:

(1)

This recursive equation will help us find a closed-form formula for . 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:

The first diagonal:

The second diagonal:

If we add the entries of the zero, first, and second diagonals, we obtain the following results

Row 0: (the Pascal triangle contains no zeros; we fill them in for completeness)

Row 1:

Row 2:

Row 3:

Row 4:

Row 5:

Row 6:

The additions yield the number of regions in our small table! But, is it true for any ?

**Conjecture**

We denote the entry in the row of the Pascal triangle by the number of ways of selecting objects from a collection of objects. For example, referring to row 6

, and so on.

We formulate the following conjecture

PROOF (by induction)

The conjecture is true for .

Suppose it is true for for some ,

We want to show that is also true for .

Applying Eq. (1) to we have

We are going to investigate the terms of the right-hand side of the above equation and show that it is equal to .

(2)

(3)

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

Finally

Pulling all the pieces together we have

The conjecture is true for . DONE

**Answer**: