Ytukyg

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.

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:

1. one more line that is parallel with existing $m$ lines


2. 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$.