1.1k views
Prove by induction that the expression for the number of diagonals in a polygon of $n$ sides is $\frac{n(n-3)}{2}$
edited | 1.1k views
0

Part A

Statement:

no_of_diagonal : $D(n) = \frac{n*(n-3)}{2}$

Step 1) Basis : for $n=4,$ $\frac{4*(4-3)}{2} = 2$ is true.

Step 2) Inductive Step :

If  $D(k)$ is true. we need to prove $D(k+1)$ is also true.

We add one more vertex to the set of $k$ vertices. Assume added vertex is $C$.

Further assume $C$ will connects vertex $A$ and $B$ to close the polygon. ($A$ and $B$ already exists in k sided polygon)

From $C$, no of pairs to each $k$ vertices = $k$, out of these two will be used to close the polygon, i.e. used as sides of new $(k+1)$ sided polygon. Further more, initial connection (edge or side) between $A$ and $B$ is now becomes a diagonal.

No of Diagonals in for $(k+1)$ sided polygon = diagonal from $k$ sided polygon + $k - 2 + 1$

$\frac{k*(k-3)}{3} + k-1 \\= \frac{k^{2} - k - 2}{2} \\= \frac{(k+1)(k-2)}{2} \\ \frac{(k+1)((k+1)-3)}{2}$

$\implies D(k+1)$ holds.

Since, both the basis and the inductive step have been performed, by mathematical induction, the statement $D(n)$ holds for all natural numbers $n>3.$

edited
0
for part B

m = 1 & n = 5

Correct me if I am wrong
+1
How to approach part B ?
0

part B M = 1 & N = 15

for first digraph

R1 = { (a,b),(b,c),(c,a)}

R= {(a,c),(b,a),(c,b)}

R3 =  { (a,b),(b,c),(c,a)}

so for first digraph m=1 and n = 3

similarly for second digraph  we will let m=1 and n =5 . So to satisfy both the digraph together we will have to take LCM of (3,5) which is 15

hence m=1 and n=15

edited
+3

I think answer should be m=0,n=15

watch below video from 45 minutes onwards

The correct answer for part (B) is m = 0 and n = 15.

NOTE: For clear understanding just watch Kamala krithivasan mam video lectures on Relations.

0

Hi. You have mentioned that the answers are 0 and 15. In that case, R0 = R15. In this regard:

Can you please clarify what R0 means? What will its value be?

0

R0 = {<x,x> ∣ x ∈ A}  i.e Equality relation which is represented by only self-loop to all the elements.

0
Thanks!
0

+1

–1 vote
According to me, for part B,

The digraphs R^n where (n>=5) are all same because they only consist of self-loops. Therefore, the answer is (m,n) = (5,6).

Note: R^n = R^n-1 o R where R^n is called the power of a relation.

1
2