4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is a proof by induction. A great article on this site is here Induction is a technique that many people find difficult, but knowing that word can help you search out explanations. $\endgroup$ – Ross Millikan Sep 11 '15 at 2:30
  • $\begingroup$ Search 'telescoping sum' on google. $\endgroup$ – Calvin Khor Sep 11 '15 at 2:33
  • $\begingroup$ The reason $(n+1)^2-n^2=2n+1$ is because we can expand $(n+1)^2=n^2+2n+1$, so $(n+1)^2-n^2=n^2+2n+1-n^2=2n+1$ $\endgroup$ – ASKASK Sep 11 '15 at 2:45
  • $\begingroup$ Yea I've figured that out but how does that $(n+1)^2$ relate to the problem? $\endgroup$ – user3258845 Sep 11 '15 at 2:50
  • $\begingroup$ I've neatened up your post a little, hope you don't mind. Also please read my answer and tell me what you think :) $\endgroup$ – Calvin Khor Sep 11 '15 at 3:02
2
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ So why not add $-(n-1)^2$ And $(n+1)^2$ ? I'm starting to get the idea now thank you but still not quite sure $\endgroup$ – user3258845 Sep 11 '15 at 5:41
  • $\begingroup$ That is also doable, but the cancelations are a lot more complicated since there is a difference of 2 between n-1 and n+1. Here, the next equation cancels with a term from the previous equation. I suggest you try writing it out like the above for (n+1)^2 - (n-1)^2 to appreciate how much harder that would be! $\endgroup$ – Calvin Khor Sep 11 '15 at 5:45
  • $\begingroup$ So what did you do instead then? $\endgroup$ – user3258845 Sep 11 '15 at 5:48
  • $\begingroup$ I did what your notes did, I wrote out (n+1)^2 - n^2 = 2n+1 for n=1,2,3,4. $\endgroup$ – Calvin Khor Sep 11 '15 at 5:49
  • $\begingroup$ When you add up all the equations you get from the two equations to $(n+1)^2-1$ $\endgroup$ – user3258845 Sep 11 '15 at 5:59
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.