I am a beginning proof writer and just began Abstract AlgebraI last week. I\'m r
ID: 2938713 • Letter: I
Question
I am a beginning proof writer and just began Abstract AlgebraI last week. I'm really lost on how to begin someproofs.... I am to prove using mathematical induction that the completegraph on n points has exactly n(n-1) / 2 lines. I don't evenknow how to begin. What would this proof look like? Thanks for all your help! I am a beginning proof writer and just began Abstract AlgebraI last week. I'm really lost on how to begin someproofs.... I am to prove using mathematical induction that the completegraph on n points has exactly n(n-1) / 2 lines. I don't evenknow how to begin. What would this proof look like? Thanks for all your help!Explanation / Answer
suppose p(n) = n(n-1) / 2 where n is the number of verticesand n(n-1)/2 are the number of lines in the graph. putting n = 1 , we have p(1) = 0 is true while there cannot bean edge or a line when there is only one vertex in the graph. so, p(1) is true.--------------(1) suppose p(k) is true. i.e. p(k) = k(k-1) /2-------------(2) when n = k+1 , p (k+1) = there are k+1 vertices in the graph. so each of the k+1vertices are having an edge to all the other vertices. i.e. one vertex is attached to k vertices. in other words , one vertex has k lines. k+1 vertices have (k+1) k lines. but each line is counted two times at the starting as well asat the ending. so, halving the total , we get k(k+1)/2 . i.e. p(k+1) = k(k+1)/2 . or, p(k+1) = ( (k+1)-1) ( k+1)/2 . this is in the requiredform. so, p(k+1) is true. ---------------(3) (1),(2),(3) satisfy the hypothesis of mathematicalinduction. so, by the proof of induction, the given statement is true forall natural values of n.Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.