Proof of triangles made with n lines where m of them are parallel

Question

So suppose that you have n lines where m of them are parallel. I know that the equation is $${{n-m}\choose3} + m{{n-m}\choose2}$$ However I am confused on how I can prove this using induction. Would I have to use double induction and prove n when I set m and prove m when I set n or is there a way to prove this without double induction?

I know for the base case I would have to prove when $n = 3$ and when $m = 0$ but how would you prove this using induction. And when I say induction I mean that I can incorporate explanations and observations into the proof, this proof is not supposed to be algebraic or anything. However it should have the base cases, inductive hypothesis and inductive step.

Answer 1

Let $T(n,m)$ be the number of triangles made with $n$ lines, $m$ of which are parallel.

Here's how to prove your formula using a single induction. Let $P(k)$ be the following proposition:

$P(k)$: For all $m\ge 2$, and $m=0$, $T(m+k,m)= \binom{k}3+m\binom{k}2. $

Using a single induction, you can show that $P(k)$ is true for all $k\ge 0$.

To do this, use the fact that $$ T(n+1,m) = T(n,m)+m(n-m)+\binom{n-m}2 $$ because adding a new line creates $m(n-m)$ triangles involving a parallel line, and $\binom{n-m}2$ triangles not involving a parallel line. I think you should be able to use the above to show $P(k)$ implies $P(k+1)$.