Sunday, July 3, 2016

calculus - Proof of sum formula, no induction



$$\sum_{k=1}^n k=\frac{n(n+1)}2$$



So I was trying to prove this sum formula without induction. I got some tips from my textbook and got this.



Let $S=1+2+\cdots+n-1+n$ be the sum of integers and $S=n+(n+1)+\cdots+2+1$ written backwards. If I add these $2$ equations I get $2S=(1+n)+(1+n)\cdots(1+n)+(1+n)$ $n$ times.




This gives me $2S=n(n+1) \Rightarrow S=\frac{n(n+1)}2$ as wanted.



However if I changed this proof so that n was strictly odd or strictly even, how might I got about this. I realize even means n must be $n/2$. But I haven't been able to implement this in the proof correctly.



Edit: error in question fixed, also by $n/2$ I mean should I implement this idea somewhere in the proof, cause even means divisible by $2$.


Answer



Method 1: (requires you to consider whether $n$ is odd or even.)



$S = 1 + 2 + ...... + n$.




Join up the first to term to the last term and second to second to last and so on.



$S = \underbrace{1 + \underbrace{2 + \underbrace{3 +....+(n-2)} + (n-1)} + n}$.



$= (n+1) + (n+1) + .....$.



If $n$ is even then:



$S = \underbrace{1 + \underbrace{2 + \underbrace{3 +..+\underbrace{\frac n2 + (\frac n2 + 1)}+..+(n-2)} + (n-1)} + n}$




And you have $\frac n2$ pairs that add up to $n+1$. So the sum is $S= \frac n2(n+1)$.



If $n$ is odd then:



$S = \underbrace{1 + \underbrace{2 + \underbrace{3 +..+\underbrace{\frac {n-1}2 + [\frac {n+1}2] + (\frac {n+1}2 + 1)}+..+(n-2)} + (n-1)} + n}$



And you have $\frac {n-1}2$ pairs that also add up to $n+1$ and one extra number $\frac {n+1}2$ which didn't fit into any pair. So the sum is $\frac {n-1}2(n+1) + \frac {n+1}2 =(n-1)\frac {n+1}2 + \frac {n+1}2 = (n-1 + 1)\frac {n+1}2n=n\frac {n+1}2$.



Method 1$\frac 12$ (Same as above but waves hands over doing tso cases).




$S = average*\text{number of terms} = average*n$.



Now the average of $1$ and $n$ is $\frac {n+1}2$ and the average of $2$ and $n-1$ is $\frac {n+1}2$ and so on. So the average of all of them together is $\frac {n+1}2$. So $S = \frac {n+1}2n$.



Method 2: (doesn't require considering whether $n$ is odd or even).



$S = 1 + 2 + 3 + ...... + n$



$S = n + (n-1) + (n-2) + ...... + 1$.




$2S = S+S = (n+ 1) + (n+1) + ..... + (n+1) = n(n+1)$>



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



Note that by adding $S$ to itself this doesn't matter whether $n$ is even or odd.



And lest you are wondering why can we be so sure that $n(n+1)$ must be even (we constructed it so it must be true... but why?) we simply note that one of $n$ or $n+1$ must be even.



So no problem.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...