Could really use some help with this.
For an integer $m \geq 1$ and $n \geq 1$, consider $m$ horizontal lines and $n$ non-horizontal lines, such that no two of the non-horizontal lines are parallel and no three of the $m+n$ lines intersect in one single point. These lines divide the plane into regions (some of which are bounded and some of which are unbounded). Denote the number of these regions by $R_{m,n}$. For example, $R_{4,3} = 23$.
Derive a recurrence for the numbers $R_{m,n}$ and use it to prove that
$$R_{m,n} = 1 + m(n+1) + \binom{n+1}{2}$$
Think about what happens each time you add a line of each type. If you add a horizontal line, it will intersect each of the $n$ non-horizontal lines, but none of the $m$ horizontal lines. On the other hand, if you add a non-horizontal line, it will intersect all of the existing $m + n$ lines. After drawing a couple pictures of small cases, you will see that $l + 1$ regions are added when a new line intersects $l$ lines at $l$ distinct points. Since no three lines meet at the same point by assumption in the problem statement, we know each new intersection intersects at a new, distinct point.
Thus we have our recurrences:
$\begin{align} R_{m,n} &= R_{m-1,n} + (n + 1)\\ &= R_{m,n-1} + (m + (n-1)) + 1 \end{align} $
We will now prove that $$R_{m,n} = 1 + m(n+1) + \binom{n+1}{2}$$ via double induction.
Let $\mathbf{P}(m,n)$ be the statement that the assertion holds for $m, n$
Base Case $\mathbf{P}(1,1):$
It is not hard to see that we have $R_{1,1} = 1 + 1(1 + 1) + {1 + 1 \choose 2} = 1 + 2 +1=4$ regions.
$\mathbf{P}(m-1,1) \Rightarrow \mathbf{P}(m,1):$
$$\begin{align} R_{m,n} &= R_{m-1,n} + (n + 1)\hspace{3mm}\text{ gives us,}\\ R_{m,n} &= 1 + (m-1)(n+1) + \binom{n+1}{2} + (n+1)\hspace{3mm}\text{so we show,} \end{align}$$ $$\begin{align} R_{m-1,1} + (1+1) &= 1 + (m-1)2 + \binom{2}{2} + 2=1 + (m-1 + 1)2 + \binom{2}{2}\\&=1 + m(1+1) + \binom{1+1}{2} \hspace{3mm}\text{as desired.} \end{align} $$ $\mathbf{P}(m,n-1) \Rightarrow \mathbf{P}(m,n):$
$$\begin{align} R_{m,n} &= R_{m,n-1} + (m + (n-1)) + 1 \hspace{3mm}\text{gives us,}\\ &= 1 + m(n) + \binom{n}{2} + (m + (n-1) + 1)\\ &= 1 + m(n+1) + {n(n-1) \over 2} + n\\ &= 1 + m(n+1) + {n(n-1+2) \over 2}\\ &= 1 + m(n+1) + \binom{n+1}{2} \end{align}$$ Thus by induction the formula holds for all $m,n\in\mathbb{N}$