Results 1 to 9 of 9

Thread: Proof by induction.

  1. #1
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782

    Proof by induction.

    I tried this last night and i'm looking at it this mornng. I'm still stuck on a bit of it:

    Observe that:

    1=1
    1-4=-(1+2)
    1-4+9=1+2+3
    1-4+9-16=-(1+2+3+4)

    Guess the general law and prove it by induction.
    My method is like this:

    $\displaystyle 1-2^2+3^2-4^2+.........-(n-1)^2+n^2=(-1)^{n+1}(\frac{n}{2})(2+(n-1))$

    $\displaystyle 1-2^2+3^2-4^2+..........-(n-1)^2+n^2=(-1)^{n+1}(\frac{n}{2})(n+1)$

    For n=1:

    $\displaystyle 1^2=(-1)^2(\frac{1}{2})(2)$

    $\displaystyle 1=1$

    Hence true for n=1.

    Assume true for n=k:

    $\displaystyle 1-2^2+3^2-4^2+..........-(k-1)^2+k^2=(-1)^{k+1}(\frac{k}{2})(k+1)$

    For n=k+1:

    $\displaystyle 1-2^2+3^2-4^2+..........-k^2+(k+1)^2=(-1)^{k+2}(\frac{k+1}{2})(k+2)$

    $\displaystyle 1-2^2+3^2-4^2+..........+(k-1)^2-k^2+(k+1)^2=(-1)^{k+2}(\frac{1}{2})(k^2+3k+2)$

    $\displaystyle 1-2^2+3^2-4^2+........+(k-1)^2-k^2+(k+1)^2=(-1)^{k+2}(\frac{1}{2})(k)(k+1)+(-1)^{k+2}(\frac{1}{2})(2k+2)$

    $\displaystyle 1-2^2+3^2-4^2+.........+(k-1)^2-k^2+(k+1)^2=-(-1)^{k+1}(\frac{1}{2})(k)(k+1)-(-1)^{k+1}(k+1)$

    At this point it's clear that the LHS does not equal the right RHS. This implies that my initial expression for the sum is incorrect. However, it works for n=1 and n=2 so I think it's right.

    Can anyone see what i'm doing wrong?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    earboth's Avatar
    Joined
    Jan 2006
    From
    Germany
    Posts
    5,854
    Thanks
    138
    Quote Originally Posted by Showcase_22 View Post
    I tried this last night and i'm looking at it this mornng. I'm still stuck on a bit of it:



    My method is like this:

    $\displaystyle 1-2^2+3^2-4^2+.........-(n-1)^2+n^2=(-1)^{n+1}(\frac{n}{2})(2+(n-1))$

    $\displaystyle 1-2^2+3^2-4^2+..........-(n-1)^2+n^2=(-1)^{n+1}(\frac{n}{2})(n+1)$

    ...
    In my opinion you must use the factor $\displaystyle (-1)^{n+1}$ at the LHS too. Otherwise you must examine the equation for 2 different cases: n is even or n is odd.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    How do you mean?

    Like this:

    $\displaystyle 1-2^2+3^2-4^2+..........+(-1)^{n+1}(n-1)^2+(-1)^{n+1}n^2=(-1)^{n+1}(\frac{n}{2})(n+1)$

    ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,410
    Thanks
    1
    Exactly, since each even term has a negative sign in front of it which must be taken into account.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    Hello, Showcase_22!


    We have: .$\displaystyle 1^2 - 2^3 + 3^2 - 4^2 + \cdots + (\text{-}1)^{n-1}n^2 \;=\;(\text{-}1)^{n-1}\frac{n(n+1)}{2}$

    Verify $\displaystyle S(1)\!:\quad (\text{-}1)^01^2 \:=\:(\text{-}1)^0\frac{1(2)}{2}$ . . . True

    Assume $\displaystyle S(k)\!:\quad 1^2 - 2^2 + 3^2 - 4^2 + \cdots + (\text{-}1)^{k-1}k^2 \;=\;(\text{-}1)^{k-1}\frac{k(k+1)}{2}$


    Add $\displaystyle (\text{-}1)^k(k+1)^2$ to both sides.

    . . $\displaystyle \underbrace{1^2-2^2+3^2 - 4^2 + \cdots + {\color{blue}(\text{-}1)^k(k+1)^2}}_{\text{Left side of }S(k+1)} \;=\;(\text{-}1)^{k-1}\frac{k(k+1)}{2} + {\color{blue}(\text{-}1)^k(k+1)^2}$


    We must show that the right side is the right side of $\displaystyle S(k+1)$
    . . which looks like this: .$\displaystyle (\text{-}1)^k\frac{(k+1)(k+2)}{2} $


    The right side is: .$\displaystyle (\text{-}1)^{k-1}\frac{k(k+1)}{2} + (\text{-}1)^k(k+1)^2 $

    Factor: .$\displaystyle (\text{-}1)^{k-1}\cdot\frac{k+1}{2}\cdot\bigg[k + (\text{-}1)2(k+1)\bigg] \;=\;(-1)^{k-1}\cdot\frac{k+1}{2}\cdot[-k-2]$

    Factor: .$\displaystyle (\text{-}1)^{k-1}\cdot\frac{k+1}{2}\cdot(\text{-}1)\cdot(k+2) \;=\;(\text{-}1)^k\cdot\frac{k+1}{2}\cdot(k+2)$

    . . And we have: .$\displaystyle (\text{-}1)^k\frac{(k+1)(k+2)}{2}\quad\hdots\quad \text{ta-}DAA!
    $

    The inductive proof is complete.

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    earboth's Avatar
    Joined
    Jan 2006
    From
    Germany
    Posts
    5,854
    Thanks
    138
    Quote Originally Posted by Showcase_22 View Post
    How do you mean?

    Like this:

    $\displaystyle 1-2^2+3^2-4^2+..........+(-1)^{n+1}(n-1)^2+(-1)^{n+1}n^2=(-1)^{n+1}(\frac{n}{2})(n+1)$

    ?
    Quite. The exponent of the factor (-1)^{n+1} is exactly greater than n by 1. Therefore the LHS should be:

    $\displaystyle 1-2^2+3^2-4^2+..........+(-1)^{\bold{{\color{red}n}}}(n-1)^2+(-1)^{n+1}n^2=(-1)^{n+1}(\frac{n}{2})(n+1)$
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2

    Lightbulb Grouping terms

    I would like to give a different way for the proof.
    It is not by induction, its by direct computation.
    This may be useful for other problems.

    We want to prove that
    $\displaystyle \sum\limits_{j=1}^{n}(-1)^{j+1}j^{2}=(-1)^{n}\sum\limits_{j=1}^{n}j=(-1)^{n}\frac{n(n+1)}{2}$ for any $\displaystyle n\in\mathbb{N}$.
    I will only consider the case where $\displaystyle n\in\mathbb{N}$ is odd because the case where $\displaystyle n$ is even is very similar.
    Since $\displaystyle n$ is odd, we may find $\displaystyle k\in\mathbb{N}$ such that $\displaystyle n=2k-1$ holds.
    $\displaystyle \sum\limits_{j=1}^{2k-1}(-1)^{j+1}j^{2}=1+\sum\limits_{j=1}^{k-1}\big[(2j+1)^{2}-(2j)^{2}\big]$
    ....................$\displaystyle =1+\sum\limits_{j=1}^{k-1}\big[(2j+1)^{2}-(2j)^{2}\big]$
    ....................$\displaystyle =1+\sum\limits_{j=1}^{k-1}\big[4j+1\big]$
    ....................$\displaystyle =k+4\sum\limits_{j=1}^{k-1}j$
    ....................$\displaystyle =k+4\frac{(k-1)k}{2}$
    ....................$\displaystyle =\frac{2k}{2}+\frac{(2k-2)2k}{2}$
    ....................$\displaystyle =\frac{(2k-1)2k}{2}$
    ....................$\displaystyle =\frac{n(n+1)}{2}.$
    Hence the proof for this case is completed.
    Let $\displaystyle n$ be even and pick $\displaystyle k\in\mathbb{N}$ to satisfy $\displaystyle n=2k$.
    Then, we have
    $\displaystyle \sum\limits_{j=1}^{2k}(-1)^{j+1}j^{2}=-\sum\limits_{j=1}^{k}\big[(2j)^{2}-(2j-1)^{2}\big]$.
    The rest is similar.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    Oh WOW!

    I wasn't expecting quite so much help. I was trying it myself and I was still getting a bit stuck on it (my typo when I wrote $\displaystyle (-1)^{n+1}$ was really throwing me).

    Anyway, thanks a bundle. I'm going to attempt this question and solve it like there's no tomorrow!!!

    After trying and SUCESSFULLY solved the problem: I used a method similar to Soroban's except I did it a little differently:

    $\displaystyle (-1)^k \frac{(k+1)(k+2)}{2}+(-1)^k(k+1)^2-(-1)^k (k+1)^2 $

    After a lot of working you end up with the required result (edit: I just noticed this is exactly what Soroban did. Rather than add it to both sides I added it to the same side).

    I like your method bkarpuz. Direct computation is a method I haven't heard of before. It took me a few read-throughs but I finally got it. =D
    Last edited by Showcase_22; Oct 4th 2008 at 11:22 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2
    Quote Originally Posted by Showcase_22 View Post
    Oh WOW!

    I wasn't expecting quite so much help. I was trying it myself and I was still getting a bit stuck on it (my typo when I wrote $\displaystyle (-1)^{n+1}$ was really throwing me).

    Anyway, thanks a bundle. I'm going to attempt this question and solve it like there's no tomorrow!!!

    After trying and SUCESSFULLY solved the problem: I used a method similar to Soroban's except I did it a little differently:

    $\displaystyle (-1)^k \frac{(k+1)(k+2)}{2}+(-1)^k(k+1)^2-(-1)^k (k+1)^2 $

    After a lot of working you end up with the required result.

    I like your method bkarpuz. Direct computation is a method I haven't heard of before. It took me a few read-throughs but I finally got it. =D
    Direct computation is not a method, its just calculating the desired identity directly by using well-known identities.
    However, you may not always come across with a known one and you may need to provide your own (new) identities.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Oct 11th 2011, 07:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 12:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Oct 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum