Proof $1+2+3+4+\cdots+n = \frac{n\times(n+1)}2$

Apparently $1+2+3+4+\ldots+n = \dfrac{n\times(n+1)}2$.

How? What's the proof? Or maybe it is self apparent just looking at the above?

PS: This problem is known as "The sum of the first $n$ positive integers".

Solution 1:

Let $$S = 1 + 2 + \ldots + (n-1) + n.$$ Write it backwards: $$S = n + (n-1) + \ldots + 2 + 1.$$ Add the two equations, term by term; each term is $n+1,$ so $$2S = (n+1) + (n+1) + \ldots + (n+1) = n(n+1).$$ Divide by 2: $$S = \frac{n(n+1)}{2}.$$

Solution 2:

My favourite proof is the one given here on MathOverflow. I'm copying the picture here for easy reference, but full credit goes to Mariano Suárez-Alvarez for this answer.

Takes a little bit of looking at it to see what's going on, but it's nice once you get it. Observe that if there are n rows of yellow discs, then:

1. there are a total of 1 + 2 + ... + n yellow discs;
2. every yellow disc corresponds to a unique pair of blue discs, and vice versa;
3. there are ${n+1 \choose 2} = \frac 12 n(n+1)$ such pairs.

Solution 3:

What a big sum! This is one of those questions that have dozens of proofs because of their utility and instructional use. I present my two favorite proofs: one because of its simplicity, and one because I came up with it on my own (that is, before seeing others do it - it's known).

The first involves the above picture:

In short, note that we want to know how many boxes are in the outlined region, as the first column has 1 box, the second 2, and so on (1 + 2 + ... + n). One way to count this quickly is to take another copy of this section and attach it below, making a $n*(n+1)$ box that has exactly twice as many squares as we actually want. But there are $n*(n+1)$ little squares in this area, so our sum is half that: $$ 1 + 2 + ... + n = \dfrac{n(n+1)}{2}. $$

Second proof, same as the first but a little bit harder and a little bit worse:

Let us take for granted the finite geometric sum $1 + x + x^2 + ... + x^n = \dfrac{x^{n+1} - 1}{x-1}$ (If you are unfamiliar with this, comment and I'll direct you to a proof). This is a polynomial - so let's differentiate it. We get $$ 1 + 2x + 3x^2 + ... + nx^{n-1} = \dfrac{ (n+1)x^n (x-1) - x^{n+1} + 1}{ (x-1)^2 }$$ Taking the limit as x approaches 1, we get

$$ \lim_{x \to 1} \dfrac{ (n+1)x^n (x-1) - x^{n+1} + 1}{ (x-1)^2} = \dfrac{ (n+1) [ (n+1)x^n - nx^{n-1} ] - (n+1)x^n }{2(x-1)} = $$ $$ \lim_{x \to 1} \dfrac{ (n+1)[(n+1)(n)x^{n-1} - n(n-1)x^{n-2}] - (n+1)(n)x^{n-1} } {2}$$

where we used two applications of l'Hopital above. This limit exists, and plugging in x = 1 we see that we get $$ \dfrac{1}{2} * (n+1)(n) [ (n+1) - (n-1) - 1] = \dfrac{ (n)(n+1)}{2}.$$

And that concludes the second proof.

Solution 4:

How many ways are there to choose a $2$-element subset out of an $n$-element set?

On the one hand, you can choose the first element of the set in $n$ ways, then the second element of the set in $n-1$ ways, then divide by $2$ because it doesn't matter which you choose first and which you choose second. This gives $\frac{n(n-1)}{2}$ ways.

On the other hand, suppose the $n$ elements are $1, 2, 3, ... n$, and suppose the larger of the two elements you choose is $j$. Then for every $j$ between $2$ and $n$ there are $j-1$ possible choices of the smaller of the two elements, which can be any of $1, 2, ... j-1$. This gives $1 + 2 + ... + (n-1)$ ways.

Since the two expressions above count the same thing, they must be equal. This is known as the principle of double counting, and it is one of a combinatorialist's favorite weapons. A generalization of this argument allows one to deduce the sum of the first $n$ squares, cubes, fourth powers...

Solution 5:

Gathering as many proofs as we can? Write the series recursively:

$$S(n) = S(n - 1) + n \tag{1}$$

Substitute $n \to n+1$ :

$$S(n + 1) = S(n) + n + 1\tag{2}$$

Equation (2) subtract Equation (1):

$$S(n+1) - S(n) = S(n) + 1 - S(n - 1) \tag{3}$$

And write it up:

$$\begin{cases} S(n+1) &= 2S(n) -S(n-1) + 1 \\ S(n) &= S(n) \end{cases} \tag{4}$$

Which can now be written in matrix form:

$$ \begin{bmatrix} S(n+1) \\ S(n) \end{bmatrix} = \begin{bmatrix} 2 & -1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} S(n) \\ S(n-1) \end{bmatrix} + \begin{bmatrix} 1 \\ 0 \end{bmatrix} \tag{5}$$

And then converting the affine equation (5) to the linear equation (6):

$$ \begin{bmatrix} S(n+1) \\ S(n+0) \\ 1\end{bmatrix} = \begin{bmatrix} 2 & -1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} S(n) \\ S(n-1) \\ 1\end{bmatrix} \tag{6}$$

And closing the equation:

$$ \begin{bmatrix} S(n+1) \\ S(n) \\ 1\end{bmatrix} = \begin{bmatrix} 2 & -1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix}^n \begin{bmatrix} S(1) \\ S(0) \\ 1\end{bmatrix} \tag{6}$$

Then finding the Jordan form of the 3x3 matrix:

$$\begin{align} \begin{bmatrix} S(n+1) \\ S(n) \\ 1\end{bmatrix} &= \left(\begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix}^{-1}\right)^n \begin{bmatrix} S(1) \\ S(0) \\ 1\end{bmatrix} \\ &= \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1\end{bmatrix}^n \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix}^{-1} \begin{bmatrix} S(1) \\ S(0) \\ 1\end{bmatrix} \\ &= \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} 1 & \binom{n}{1} & \binom{n-1}{2} \\ 0 & 1 & \binom{n}{1} \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} 0 & 1 & 0 \\ 1 & -1 & 0 \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} S(1) \\ S(0) \\ 1\end{bmatrix} \end{align} \tag{7}$$

And multiplying the matrices out:

$$\begin{bmatrix} S(n+1) \\ S(n) \\ 1\end{bmatrix} = \begin{bmatrix} \frac{ (2n+2)S(1) - 2nS(0) + {n}^{2} + n}{2} \\ \frac{ 2nS(1) + (2 - 2n)S(0)+{n}^{2}-n}{2} \\ 1 \end{bmatrix} \tag{8}$$

And given that $S(0) = 0$ and $S(1) = 1$, we get that:

$$S(n) = \frac{n^2 + n}{2} \tag{9}$$