Very Hard Question I've seen this question answered before on this website, but I did not understand how they did it. So essentially, the question is as follows:
Given $n$ lines in the plane such that $m$ are parallel and no three lines intersect at a single point. These $n$ lines with $m$ parallel lines form $\binom{n-m}{3} + \binom{n-m}{2}\cdot m$ triangles. 
How would you prove this using simple induction. Please show steps as well so I can better understand it.
 A: You can easily check that the formula is valid for some simple starting configuration (for example, for $n=3$, I leave it up to you).
Here is the induciton step:
Suppose that the formula is correct for some number of lines $n$ with $m$ of them being parallel:
$$f(n,m)={n - m \choose 3}+{n - m \choose 2}m$$
We have to prove that the formula is still correct if we add:


*

*one more line that is parallel with existing $m$ lines

*one more line that is not parallel with existing $m$ lines


Note that whenever you add a new (black) line you are adding one new (brown) triangle whenever a new line intersect a pair of non-parallel (red) lines, but not in the case when the new line intersects a pair of parallel (blue) lines:

Case 1: Adding one more line that is parallel with $m$ existing lines. We are going to end up with $n+1$ lines with $m+1$ lines being parallel. 
In this case the new line will add a new triangle whenever a new line interesects a pair of non-parallel lines. There are ${n-m \choose 2}$ such pairs so the total number of triangles is:
$$f(n,m)+{n-m \choose 2}={n - m \choose 3}+{n - m \choose 2}m+{n-m \choose 2}=$$
$${n - m \choose 3}+{n - m \choose 2}(m+1)=$$
$${(n+1) - (m+1) \choose 3}+{(n + 1) - (m+1) \choose 2}(m+1)=f(n+1,m+1)$$
So the formula is correct in this case too.
Case 2: Adding one more line that is not parallel with $m$ existing lines. We are going to end up with $n+1$ lines with $m$ lines being parallel.
How many triangles are we adding by adding one non-parallel line? In total, the new line will intersect ${n \choose 2}$ pairs of lines. Intersection with each pair of lines will add a new triangle except when the line intersect a pair of parallel lines. And there are ${m \choose 2}$ such pairs.
So the increment in nummber of triangles is:
$$\Delta={n \choose 2}-{m \choose 2}=\frac{n(n-1)}{2}-\frac{m(m-1)}{2}$$ 
$$\Delta=\frac{n^2-m^2-n+m}{2}=\frac{(n-m)(n+m)-(n-m)}{2}=\frac{(n-m)(n+m-1)}{2}$$ 
$$\Delta=\frac{(n-m)(n-m-1+2m)}{2}=\frac{(n-m)(n-m-1)}{2}+(n-m)m$$ 
$$\Delta=\binom{n-m}{2}+\binom{n-m}{1}m$$ 
New number of triangles is:
$$f(n,m)+\Delta={n - m \choose 3}+{n - m \choose 2}m+\binom{n-m}{2}+\binom{n-m}{1}m=$$
$$\left[{n - m \choose 3}+\binom{n-m}{2}\right] + \left[{n - m \choose 2}+\binom{n-m}{1}\right]m=$$
$${n+1 - m \choose 3}+{n+1 - m \choose 2}m=f(n+1,m)$$
In the last step we have used a known identity:
$$\binom{p}{q}+\binom{p}{q-1}=\binom{p+1}{q}$$
Conclusion: You can construct all possible configurations either by adding parallel or non-parallel line, one by one, and in both cases we have proved the the $f(n,m)$ formula is correct. So the formula is valid for any given $n,m$. 
