Ayaan Barr

2022-06-29

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\left(n+1\right)/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\left(1+2+3+4+5\right)=n\left(n+1\right)$
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\left(n+1\right)$ is twice the hands shake, because we are counting twice each hand shake. So the total hand shakes must be $n\left(n+1\right)/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.

postojahob

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
$\left(\genfrac{}{}{0}{}{n+1}{2}\right)=\frac{n\left(n+1\right)}{2}$
because $\left(\genfrac{}{}{0}{}{n+1}{2}\right)$ counts the number of subsets of 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\cdot |E|=\sum _{i=1}^{n+1}deg\left(v\right)$
$2\cdot |E|=\sum _{i=1}^{n+1}n$
$2\cdot |E|=n\left(n+1\right)$
$|E|=\frac{n\left(n+1\right)}{2}$ as we wanted.

Do you have a similar question?