Question

(1)The following two claims are similar to the claim in the triangle problem discussed in lecture, but there are subtle differences. Either prove or disprove each claim.

(a) Let T(n) be: C(n, 3) triangles are formed by n lines in the plane if no three of the lines intersect at a single point. ∀n ∈ N, n ≥ 3, T(n).

(b) Let R(n) be: C(n, 3) triangles are formed by n non-parallel lines in the plane. ∀n ∈ N, n ≥ 3, R(n).

Answer 1

1. If the no three lines intersect at a single point. Then in this condition, tes may be parallel. Therefore, the number of triangles formed in this case will be less than C (n, 3). For example, for n = 4 (four lines), two of the four   lines are parallel. The number of triangles formed = 2.

2. Let us prove it by induction.

Basis Step: For n =3, only one triangle can be formed, with the thre non-parallel lines.

Thus, R (n) holds (is true) for n=3.

Induction Step: Let the property R(n) holds for n = m, i.e. there are C (m, 3) triangles which can be formed with m non-parallel lines, then for n = m+1, we have

Since, the (m+1)^th line added is not parallel to the already existing m lines, hence this additional line will form a triangle with any two lines out of the m lines.This selection of 2 lines from m lines can be done in C(m, 2). Therefore, the total triangles formed with (m+1) lines

= Already existing C (m, 3) triangles + Additional Triangles formed with addition of m+1^th line = C (m, 3) + C (m, 2) = C (m+1, 3)

Therefore, R(n) also holds for n = m+1.

Hence, R(n) holds for all n > 2.