m = 1 & n = 5

Correct me if I am wrong

The Gateway to Computer Science Excellence

+17 votes

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

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

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

+5 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.

0

Hi. You have mentioned that the answers are 0 and 15. In that case, R^{0} = R^{15}. In this regard:

Can you please clarify what R^{0} means? What will its value be?

0

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

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

R_{1 = }{ (a,b),(b,c),(c,a)}

R_{2 }= {(a,c),(b,a),(c,b)}

R_{3 = }{ (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

+1 vote

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

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

52,345 questions

60,497 answers

201,859 comments

95,315 users