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


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

  • $\begingroup$ 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. $\endgroup$ – Daniel Cook Nov 12 '13 at 19:53
  • $\begingroup$ Because you add a triangle for each pair of existing lines. That feels a bit like the non-inductive proof to me, though. $\endgroup$ – Ross Millikan Nov 12 '13 at 19:55
  • $\begingroup$ 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. $\endgroup$ – Daniel Cook Nov 15 '13 at 22:38
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Nov 15 '13 at 23:09
  • $\begingroup$ 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. $\endgroup$ – Daniel Cook Nov 15 '13 at 23:33

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.