Divide and Conquer

Let the maximum region of $n$ line in a plane be $R_{n}$ .

By doing observation, it is easy to see that $\color{#D61F06}{ ^*}$ if we add a new line to a plane consist of $n-1$ line, we will have maximum $n$ new region $\color{#D61F06}{ ^*}$ .

$\color{#D61F06}{ ^*} R_{n}=R_{n-1}+n \color{#D61F06}{ ^*}$

We know that $R_{0}=1$ . Then we can construct formula of $R_{n}$ .

$\begin{aligned} R_{n} & =1+1+2+3+...+n \\ R_{n} & =1+(1+2+3+...+n) \\ R_{n} & =1+\frac{n(n+1)}{2} \\ R_{n} & =\frac{ 2+n(n+1)}{2} \\ R_{n} & =\frac{n^{2}+n+2}{2} \end{aligned}$

Putting $n=2016$

$\begin{aligned} \implies R_{2016} & =\frac{2016^{2}+2016+2}{2} \\ R_{2016} & =\frac{4064256+2016+2}{2} \\ R_{2016} & =\frac{4066274}{2} \\ R_{2016} & =\boxed{2033137} \end{aligned}$

Note: in order to get maximum number of region, no more than two line are allowed to intersect in a point.

( We get minimum number of regions when the lines are concurrent )

If we observe the pattern then this k is recursively defined by

$k_{n} = k_{n-1} + (n-2)$ with $k_{2} = 0$

Evaluating the above expression we have the following formula for $k_{n}$

$k_{n}= \frac{(n-2) \times (n-1) }{2}$

Thus the maximum number of regions in which the plane is divided is

$2n + k_{n}$

$2n + \frac{(n-2) \times (n-1) }{2}$

$\frac{n^{2}+n+2}{2}$

So, with n=2016 we have 2033137 non-overlapping regions.