The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
1.2k views
Prove by induction that the expression for the number of diagonals in a polygon of $n$ sides is $\frac{n(n-3)}{2}$
in Set Theory & Algebra by Veteran (52.1k points)
edited by | 1.2k views

6 Answers

+13 votes
Best answer

Statement:

No. of diagonals : $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.$

by Veteran (56.8k points)
edited by
0
for part B

m = 1 & n = 5

Correct me if I am wrong
+1
How to approach part B ?
0
can you please elaborate your approach of solving part B
+4 votes
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.

by Loyal (7.7k points)
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

@Warrior

Please provide the link for the video

+2

sutanay3  Video link: 

0

Watch mam's video for 00:00 to 15:07, part second will be cleared.

Thanks @sourav Basu for video link. 

+3 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

by Junior (951 points)
edited by
+3

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

watch below video from 45 minutes onwards

0

@Sourav Basu

In the video mam has noted down

R0= R3= R6

R1= R4= R7

R2= R5= R8

This symmetry arises because it has 3 elements?

0 votes
Without induction---

We know that for a simple graph having n vertices, maximum number of edges $=^nC_2=\frac{n(n-1)}{2}$

So for diagonals of a polygon $(n \ge 3)$  we remove the boundary edges..

So $\frac{n(n-1)}{2} -n=\frac{n(n-3)}{2}$
by Boss (10.5k points)
0 votes
Part B
m=0 n=15
For first graph R1 repeat itself after a cycle of 3 i.e R1^0=R1^3.
Similarly, R2^0=R2^5
So, both will repeat themselves after LCM(3,5)=15.
Therefore,m=0 and n=15
by (217 points)
–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.
by Active (1.7k 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
50,288 questions
55,716 answers
192,103 comments
90,099 users