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

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

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

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

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