Results 1 to 6 of 6

Math Help - Basic Proof by Induction

  1. #1
    Newbie
    Joined
    Mar 2011
    Posts
    7

    Basic Proof by Induction

    Hi,

    im a bit stuck on an question,

    using proof by induction, prove that

    sum_(r=1)^n(2 r-1) = n^2

    same formula formatted:
    http://www.wolframalpha.com/input/?i=Sum[2+r+-+1%2C+{r%2C+1%2C+n}]

    my answers keep not making sense. please can someone help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1

    Re: Basic Proof by Induction

    Quote Originally Posted by nomanslan View Post
    using proof by induction, prove that
    sum_(r=1)^n(2 r-1) = n^2
    If n=1 then 2\cdot 1-1=1^2 so base case it true.

    Suppose that N>1 and \sum\limits_{r = 1}^N {\left( {2r - 1} \right)}  = N^2 is true.

    Then look at \sum\limits_{r = 1}^{N+1} {\left( {2r - 1} \right)}  =\sum\limits_{r = 1}^N {\left( {2r - 1} \right)}+[2(N+1)-1]

    Can you finish?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    106

    Re: Basic Proof by Induction

    Ok so we want to show that
    \sum_{r=1}^n (2r-1) = n^2

    to prove by induction we need to show for the base case (n=1) in this case we have
    \sum_{r=1}^1 (2r-1) = 1 = 1^2
    so it is true in that case,

    now for the inductive step we want to show that given that
    \sum_{r=1}^k (2r-1) = k^2

    then
    \sum_{r=1}^{k+1} (2r-1) = (k+1)^2

    so write it out and split the sum like so
    \sum_{r=1}^{k+1} (2r-1) = \sum_{r=1}^{k} (2r-1) + (2(k+1) - 1) = k^2 + 2k +1

    Give it a go from there
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2011
    Posts
    7

    Re: Basic Proof by Induction

    s(k+1) = s(k) +t(k) + 1
    = k^2+(2(k+1)-1)+1 = k^2+2k+1

    therefore
    2r=1 = n^2?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,444
    Thanks
    1863

    Re: Basic Proof by Induction

    Quote Originally Posted by nomanslan View Post
    s(k+1) = s(k) +t(k) + 1
    = k^2+(2(k+1)-1)+1 = k^2+2k+1

    therefore
    2r=1 = n^2?
    That makes no sense. There is no "r" or "n" in what you have above.

    The point was supposed to be that k^2+ 2k+ 1= (k+ 1)^2.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,831
    Thanks
    1602

    Re: Basic Proof by Induction

    Quote Originally Posted by nomanslan View Post
    Hi,

    im a bit stuck on an question,

    using proof by induction, prove that

    sum_(r=1)^n(2 r-1) = n^2

    same formula formatted:
    http://www.wolframalpha.com/input/?i=Sum[2+r+-+1%2C+{r%2C+1%2C+n}]

    my answers keep not making sense. please can someone help
    There's no need for induction...

    \displaystyle \begin{align*} \sum_{r = 1}^n{\left(2r - 1\right)} &= 2\sum_{r = 1}^n{r} - \sum_{r = 1}^n{1} \\ &= 2 \cdot \frac{n(n + 1)}{2} - n \\ &= n(n + 1) - n \\ &= n^2 + n - n \\ &= n^2 \end{align*}

    And in case you weren't sure that \displaystyle \begin{align*} \sum_{r = 1}^n{r} = \frac{n(n + 1)}{2} \end{align*} ...

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: November 24th 2011, 05:05 PM
  2. BASIC: How to Simpliy Powers for Induction
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: May 30th 2011, 11:59 PM
  3. Basic proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 17th 2009, 12:14 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum