Sum of first n natural numbers proof

Question

I know how to prove this by induction but the text I'm following shows another way to prove it and I guess this way is used again in the future. I'm confused by it.

So the expression for first n numbers is: $$\frac{n(n+1)}{2}$$

And this second proof starts out like this. It says since:

$$(n+1)^2-n^2=2n+1$$

Absolutely no idea where this expression came from, doesn't explain where it came from either.

Then it proceeds to say: \begin{align} 2^2-1^2&=2*1+1 \\ 3^2-2^2&=2*2+1\\ &\dots\\ n^2-(n-1)^2&=2(n-1)+1\\ (n+1)^2-n^2&=2n+1 \end{align} At this point I'm completely lost. But it continues to say "adding and noting the cancellations on the left, we get" \begin{align} (n+1)^2-1&=2(1+2+...+n)+n \\ n^2+n&=2(1+2+...+n) \\ (n(n+1))/2&=1+2+...+n \end{align}

Which proves it but I have no clue what has happened. I am entirely new to these math proofs. Im completely lost. I was great at high school math and calculus but now I haven't got the slightest clue of what's going on. Thanks

Answer 1

A simple way to "prove" the formula you give is to note that you can pair

$1$ with $n-1$

$2$ with $n-2$

$3$ with $n-3$

... and so on. Then you can see that the sum will be $(n+1)/2$ (the $+1$ coming from the fact that we basically pair $n$ with zero) of these pairs, each of which is the number $n$.

Answer 2

This is a telescoping sum. The use of $(n+1)^2 - n^2 = 2n + 1$ is a clever trick, and it is only clear why we use it once you understand the whole argument. The idea is to first find $\sum_1^n (2k+1) = 2(1+\dots+n)+(1+\dots+1)$ and use this to find $\sum_1^n k =1+\dots+n$.

I'm going to colour code the given text above, as well as add a few lines which will hopefully make things clearer.

\begin{align} \color{blue}{2^2}-1^2&=2\times 1+1 \\ \color{red}{3^2}-\color{blue}{2^2}&=2\times 2+1\\ \color{green}{4^2}-\color{red}{3^2}&=2\times 3+1\\ \color{orange}{5^2}-\color{green}{4^2}&=2\times 4+1\\ &\dots\\ \color{brown}{n^2}-(n-1)^2&=2(n-1)+1\\ (n+1)^2-\color{brown}{n^2}&=2n+1 \end{align}

Hopefully you can see, when you add each coloured pair together, e.g. since one is $+\color{blue}{2^2}$ and the other is $-\color{blue}{2^2}$, they cancel out completely. The same happens with every number you can pair. The only ones that don't cancel are the $-1^2 $ at the start, and also the $(n+1)^2$ at the end. So by adding up all these equations (there are $n$ of them) we get

$$ (n+1)^2 - 1 = 2(1+\dots+n) + (1+\dots+1) = 2(1+\dots+n) + n$$

Does this help? (Tell me if the remainder of the argument isnt clear as well.)

Answer 3

The proof is a trick, of course. Working in the opposite direction, the idea is to write $$2\sum_{r=1}^nr=\sum 2r=\sum \left ((2r+1)-1\right)=\sum (2r+1)-\sum 1=\sum (2r+1)-n$$

This seems elaborate, but the point is to write as much of the sum as possible in a form which cancels. We use $2r+1$ for this because we know that the difference between successive squares is an odd number, so $$\sum_{r=1}^n (2r+1)=\sum_{r=1}^n ((r+1)^2-r^2)=\sum_{r=2}^{n+1}r^2-\sum_{r=1}^n r^2=(n+1)^2-1$$because all the other terms cancel. Then $$2\sum_{r=1}^nr=(n+1)^2-1-n=n(n+1)$$

---

Note that $(n+1)^k-n^k=kn^{k-1}+\text{ terms of lower degree in }n$, because the terms in $n^k$ cancel - so if you know the sums of $(k-1)^{th}$ powers and below, the sums of the $k^{th}$ powers can be worked out using the difference trick. The factor $k$ makes it easy to see that the leading term in $\sum_{r=1}^nr^k$ is $\cfrac {n^{k+1}}{(k+1)!}$.

This strategy - where spotted - can be used to simplify problems, and is well worth knowing. If you are using it you don't need to know where it came from - the justification for using it is that it works. But having an idea where it came from can help you to spot other possible uses.

It isn't quite as simple as saying this method avoids induction - rather the induction gets hidden in the fact that terms cancel instead of being made explicit.