0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Wouldn't m have to be either 0 or greater than 1 and not equal to 1 because you can't have 1 parallel line. Parallel lines have to be at least a pair or you don't have parallel lines. $\endgroup$ – Geralt Dec 1 '18 at 1:28
  • $\begingroup$ Also, wouldnt k have to be at least 3 because otherwise you wouldn't have any triangles to count. $\endgroup$ – Geralt Dec 1 '18 at 1:30
  • $\begingroup$ @Geralt The formula works for all $k\ge 0$; when $k=0$ or $1$, the formula correctly says there are $0$ triangles. When $k=2$, the formula correctly says there are $m$ triangles, which is zero when $m=0$. $\endgroup$ – Mike Earnest Dec 1 '18 at 1:36
  • $\begingroup$ @Geralt I've changed the condition on $m$ because of your comment. $\endgroup$ – Mike Earnest Dec 1 '18 at 1:41
  • $\begingroup$ I am a bit confused on the proposition P(k). How can you say that P(k) is true for m greater than 1 and equal to 0 without proving that first. Or is it unnecessary? $\endgroup$ – Geralt Dec 1 '18 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.