# elementary prove thru induction - dumb stumbling

i am trying to prove this statement for all $n \in \mathbb{N}$ with the help of induction:

$4 \sum_{k=1}^{n} (-1)^kk=(-1)^n(2n+1)-1$

base case: n=1

$4 \sum_{k=1}^{1} (-1)^11=-4=(-1)^1(2*1+1)-1$ .. OK

induction hypothesis: for all $n \in \mathbb{N}$ let be $4 \sum_{k=1}^{n} (-1)^kk=(-1)^n(2n+1)-1$

inductive step: $n \rightarrow n+1$

$4 \sum_{k=1}^{n+1} (-1)^kk=4 \sum_{k=1}^{n} (-1)^kk+(-1)^{n+1}(n+1)=(-1)^n(2n+1)-1+(-1)^{n+1}(n+1)=...help...=(-1)^{n+1}(2(n+1)+1)-1$

i need help for $..help..$

thanks a lot

-
Sometimes when you are working with expressions that involve $(-1)^n$, and $(-1)^{n+1}$, and perhaps some other minus signs, it can be helpful to deal separately with $n$ even and with $n$ odd. – André Nicolas Nov 17 '12 at 16:48

Is : $$4 \sum_{k=1}^{n+1} (-1)^kk=4 \sum_{k=1}^{n} (-1)^kk+4(-1)^{n+1}(n+1)=(-1)^n(2n+1)-1-(-1)^n(4n+4)=(-1)^n(2n+1-4n-4)-1=(-1)^n(-2n-3)-1=(-1)^{n+1}(2n+3)-1=(-1)^{n+1}(2(n+1)+1)-1.$$

-
great :D, thanks Pambos – doniyor Nov 17 '12 at 16:39
You are welcome. – P.. Nov 17 '12 at 16:39
Remark $\$ The above algebra calculation can be viewed more conceptually as checking that both sides are the solution of the same recurrence with the same initial condition -- see my answer. @doniyor This completely eliminates said "dumb stumbling" for the inductive step since the telescopy tells you what you need to check - the rest is simple rote (mechanical) algebra (it can be done by a computer - no insight is required). – Bill Dubuque Nov 17 '12 at 16:48
Thanks Bill, you are right – doniyor Nov 17 '12 at 16:52

Hint $\$ Check both sides are solutions of the recurrence $\rm\: f(n) - f(n\!-\!1) = (-1)^n 4n,\,\ f(1) =4,$ therefore they are equal for all $\rm\:n\:$ by a simple induction (which amounts to the uniqueness theorem for such recurrences -- see my many posts on telescopy).

Remark $\$ For completeness I sketch the trivial inductive proof of said uniqueness theorem, sometimes called the fundamental theorem of difference calculus

Theorem  If $\rm\:f_1,f_2,g,h\:$ are functions on $\Bbb N,\,$ and $\rm\:f_1,f_2\:$ satisfy $\rm\:f(n\!+\!1) \color{#C00}= g(n) f(n) + h(n)\:$ for all $\rm\:n\ge 1,\:$ then $\rm\: f_1(1) = f_2(1)\:\Rightarrow\:f_1(n) = f_2(n)\:$ for all $\rm\:n \ge 1.$

Proof $\$ Induct on $\rm\:n.\:$ The base case $\rm\:n=1\:$ is true by hypothesis, and the inductive step is

$$\rm \color{blue}{f_1(n)} = \color{#0A0}{f_2(n)}\ \Rightarrow\ f_1(n\!+\!1) \color{#C00}= g(n)\color{blue}{f_1(n)}+h(n) = g(n) \color{#0A0}{f_2(n)}+h(n) \color{#C00}= f_2(n\!+\!1)$$

-
wow, powerful way! thanks Bill – doniyor Nov 17 '12 at 16:48