Alternative proof for the sum of first n natural numbers (Gauss formula) The known formula for the

Ayaan Barr 2022-06-29 Answered
Alternative proof for the sum of first n natural numbers (Gauss formula)
The known formula for the sum of the first n natural numbers n ( n + 1 ) / 2 is not intuitive at all. One proof for that formula is to duplicate the numbers and arrange it in pairs which sums up to n + 1 and then sum up all the numbers:
1 + 2 + 3 + 4 + 5 + 5 + 4 + 3 + 2 + 1 = 2 ( 1 + 2 + 3 + 4 + 5 ) = n ( n + 1 )
It is a really nice proof and also very direct and intuitive. But I have come up with this alternative:
Suppose there are n + 1 people meeting and they all shake hands with each other. To count how many hand shakes are in total, one can start counting the hand shakes for one person which is n. Then for a second person count her hand shakes, but don't count the hand shake with the first person, because that one was already counted, so in total, for the second person, we count n 1, and so on. The total hand shakes is then the sum of the first n natural numbers.
But now we can count the hand shakes in a simpler way. There are n + 1 people in total, and each of them shakes hand with n people. Then n ( n + 1 ) is twice the hands shake, because we are counting twice each hand shake. So the total hand shakes must be n ( n + 1 ) / 2
The two ways of counting have to arrive to the same number so the formula holds.
I wonder how can this proof be formalized so it would be accepted as a real mathematical proof.
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

postojahob
Answered 2022-06-30 Author has 13 answers
Step 1
You can do it very nicely using graphs. Let G be an undirected complete graph on n + 1 vertices. each vertice represents one of the people in your meeting, and each edge represents a handshake between two people. We want to count the number of edges in this graph. It is simply
( n + 1 2 ) = n ( n + 1 ) 2
because ( n + 1 2 ) counts the number of subsets of {1,2,...,n+1}  with cardinality 2, and we can match each subset to an edge between these 2 vertices and as a handshake between these two people the vertices are representing.
Step 2
Another fascinating way to get this is by the degree sum formula, where we get that the number of edges is:
2 | E | = i = 1 n + 1 d e g ( v )
2 | E | = i = 1 n + 1 n
2 | E | = n ( n + 1 )
| E | = n ( n + 1 ) 2 as we wanted.

We have step-by-step solutions for your answer!

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-08-15
How many elements are in the set { 0, { { 0 } }?
asked 2020-11-09
Use proof by Contradiction to prove that the sum of an irrational number and a rational number is irrational.
asked 2021-08-02
Suppose that A is the set of sophomores at your school and B is the set of students in discrete mathematics at your school. Express each of these sets in terms of A and B.
a) the set of sophomores taking discrete mathematics in your school
b) the set of sophomores at your school who are not taking discrete mathematics
c) the set of students at your school who either are sophomores or are taking discrete mathematics
Use these symbols:
asked 2021-08-18
Discrete Mathematics Basics
1) Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where (a,b)R if and only if
I) everyone who has visited Web page a has also visited Web page b.
II) there are no common links found on both Web page a and Web page b.
III) there is at least one common link on Web page a and Web page b.
asked 2021-08-10
F0, F1, F2 is the Fibonacci sequence.
Prove that Fk+12Fk2=Fk1Fk+2, for all integers k1
asked 2022-06-22
Is this true for chromatic numbers?
If we take the graph G = ( V ( G ) , E ( G ) ) and partition the edges E(G) into k sets, forming k subgraphs of the form H i = ( V ( G ) , E ( H i ) ) for i { 1 , . . . , k } such that | E ( H i ) | 1 for each subgraph H i . Furthermore, we let χ(G) be the chromatic number of the graph G.
Does it hold that i = 1 k χ ( H i ) χ ( G )? How would we prove it? I know that this holds when k = 2. How about other values k 3?
For the case k = 2 we can take H , H ¯ G such that H = ( V ( G ) , E ( H ) ) and H ¯ = ( V ( G ) , E E ( H ) ). If the coloring C H : V ( G ) [ χ ( H ) ] is a coloring of H and C H ¯ : V ( G ) [ χ ( H ¯ ) ] is a coloring of H ¯ , we are able to construct a coloring C G of G with at most χ ( H ) χ ( H ¯ ) colors by letting C G ( v ) = ( C H ( v ) , C H ¯ ( v ) ). We can also observe that every edge (u,v) in G belongs to either H or H ¯ and hence C G ( u ) differs from C G ( v ) in at least one of the coordinates.
Can this same argument potentially be generalized for the case of partitioning G into k subgraphs such that | E ( H i ) | 1 for each subgraph?
asked 2022-07-09
Prove that no graph has exactly 2 spanning trees.
This question is why I must go second time to the final exam in discrete mathematics.
The original question was:
For which n exists a graph with n spanning trees?
I know, that for n > 2 there exists a graph with n spanning trees, because if we take C 3 , which is a cycle with 3 vertices, it has exactly 3 spanning trees. Cycle on 4 vertices has 4 spanning trees and so on. I know that if a graph is not connected, than it has 0 spanning trees, and if I have a graph on 1 vertex, it has exactly 1 spanning tree.
So the question remains, how do I prove, that no graph exists, which has exactly 2 spanning trees.

New questions

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question