The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 votes
Prove by induction that the expression for the number of diagonals in a polygon of $n$ sides is $\frac{n(n-3)}{2}$
asked in Set Theory & Algebra by Veteran (59.7k points)
edited by | 1k views
@Happy part (B) please

4 Answers

+11 votes
Best answer

Part A


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

answered by Veteran (57.6k points)
edited by
for part B

m = 1 & n = 5

Correct me if I am wrong
How to approach part B ?
+2 votes

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

answered by Active (1.2k points)
edited by

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

watch below video from 45 minutes onwards

+1 vote
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.

answered by Loyal (7.2k points)

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?


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




Please provide the link for the video


sutanay3  Video link: 

–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.
answered by Active (1.6k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,456 questions
49,913 answers
65,897 users