0

Prove with induction: Given n non parallel lines such that no three intersect at a point, there are c(n,3) triangles formed.

so I have n!/(n-3)!3! triangles if this condition holds, that is all I understand how to do from this question

SSS
  • 41

1 Answers1

1

The non-inductive proof is that you can choose any three lines and they will form a triangle.

The inductive proof is to start with the base case: with three lines you get one triangle. Now assume it is true for $k$ lines, so there are $C(k,3)$ triangles . Add another line. It will form $\frac 12 k(k-1)$ new triangles. Add these in and show that this gives a total of $C(k+1,3)$

Ross Millikan
  • 374,822
  • Hm..why does adding one extra line to k lines form $1/2k (k+1)$ lines? I thought of a strong induction proof but this seems better. – Daniel Cook Nov 12 '13 at 19:53
  • Because you add a triangle for each pair of existing lines. That feels a bit like the non-inductive proof to me, though. – Ross Millikan Nov 12 '13 at 19:55
  • Are you sure the number of new triangles formed depends on the number of lines? I think it depends on how many new triangles $k$ lines form. If the number of new triangles $k$ lines form is $x$, then the number of triangles formed by $k+1$ lines is $1/2x(x+1)$. Am I mistaken? I apologize if I am. – Daniel Cook Nov 15 '13 at 22:38
  • Each new line will cross all the previous lines. It will therefore make a new triangle with each pair of existing lines. But I just realized that the plus sign should be a minus, because from $k$ lines one can form $\frac 12k(k-1)$ pairs. Incidentally, please write it as $k(k+1)/2$ or $(1/2)k(k+1)$ or use \frac to stack the fraction. With the slash it is not clear what is in the denominator. We get various things on this site. – Ross Millikan Nov 15 '13 at 23:09
  • That makes a lot more sense now! Because $\frac 12 k(k+1)$ is the $k^{th}$ triangular number, I got confused. The triangular numbers actually represent how many new triangles are formed, don't they? And, I will from now on, thank you so much. – Daniel Cook Nov 15 '13 at 23:33
  • The triangular numbers are named that for a different reason-if you make a triangle with $1,2,3,4,\dots,k$ items, they are the number of items. They show up often in combinatoric problems. My original was a triangular number, too, just one notch too large. – Ross Millikan Nov 15 '13 at 23:47
  • why are we multiplying by 1/2? – SSS Nov 16 '13 at 18:09
  • When you count the triangles formed by line $k+1$, you get one for each pair of earlier lines. You have $k$ choices for the first line and $k-1$ for the second. But we get each pair twice this way, so have to divide by $2$. This is exactly $C(k,2)$ – Ross Millikan Nov 16 '13 at 22:22