1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mathematical induction problem

  1. Jun 6, 2012 #1
    1. The problem statement, all variables and given/known data
    Hello! This is I want to prove using Mathematical Induction: [itex]1+3+5+...+(2n-1)=n^2[/itex]. The problem is: I don`t understand very much about Mathematical Induction :(


    2. Relevant equations



    3. The attempt at a solution
    Suppose n=1. Then 1=1. Now suppose [itex]1+3+5+...+(2n)=(n+1)^2[/itex]. Then [itex]1+3+5+...+2n=(1+3+5+...+(2n-1))+2n=n^2+2n=n(n+2)[/itex].
    Is this correct? If yes, how does this prove my hypothesis?
     
  2. jcsd
  3. Jun 6, 2012 #2
    You're only working with odd numbers, so the next term wouldn't be [itex]2n[/itex]..
     
  4. Jun 6, 2012 #3
    This is what I should do to solve the problem [itex]1+3+5+...+(2n-1+1)=1+3+5+...+2n[/itex]. Right? Because you always do [itex]n+1[/itex] in the Induction step.
     
  5. Jun 6, 2012 #4
    Mathematical induction attempts to show that if the equation holds for n, then it also holds for n+1. It's easier to keep straight if you use a substitution such as n=k+1
     
  6. Jun 6, 2012 #5
    @ DDarthVader: Yes, but you're not substituting [itex]n + 1[/itex] in for [itex]2n - 1[/itex] or anything, you're subbing it in for [itex]n[/itex]...
     
  7. Jun 6, 2012 #6
    Doing the substitution [itex]n=k+1[/itex] I've got this result:
    [itex] 1+3+5+...+2k+1=(1+3+5+...+(2n-1))+2k+1[/itex]
    Then
    [itex]n^2 +2k+1 = (k+1)^2+2k+1 = k^2+2k+2+2k+1 = k^2+4k+3[/itex]
    But since [itex]n=k+1[/itex] we got
    [itex](n-1)^2+4n-4+3 =n^2-2n+4n+1 =n^2+2n+1 = (n+1)^2[/itex]
    Is this correct?
     
    Last edited: Jun 6, 2012
  8. Jun 6, 2012 #7

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Your conjecture: [itex]1+3+5+...+(2n-1)=n^2[/itex]

    You've already done the base step, n = 1.

    For the induction step:

    Let k ≥ 1. Assume that your conjecture is true for n = k. From that, show (prove) that your conjecture is true for n = k+1 .

    So you need to show that [itex]1+3+5+\dots+(2k-1)+(2(k+1)-1)=(k+1)^2[/itex] is true,

    starting with [itex]1+3+5+\dots+(2k-1)=k^2\ .[/itex]
     
    Last edited: Jun 6, 2012
  9. Jun 6, 2012 #8
    As you see here, (n+1)th value is not equal to 2n
    It is equal to (2(n+1)-1)
     
  10. Jun 6, 2012 #9
    Substituting n=k+1 into 2n-1 gives 2(k+1)-1.
     
  11. Jun 6, 2012 #10
    Doing what you told me I've got this result:
    [itex]1+3+5+...+(2n-1)=n^2[/itex].
    We assume n=k. Then we try to prove if the conjecture is true for n=k+1 and we obtain: [itex]1+3+5+...+(2n-1)+(2n-1)=n^2[/itex]
    But n=k+1
    [itex]k^2+(2(k+1)-1)=(k+1)^2[/itex]
    [itex]k^2+(2(k+1)-1)=k^2+2k+1[/itex]
    [itex]2(k+1)-1=2k+1[/itex]
    [itex]2(k+1)=2k+2[/itex]
    [itex]2(k+1)=2(k+1)[/itex]
    So I proved that the conjecture is also true for n=k+1. Right?
     
  12. Jun 6, 2012 #11
    Isn't it bad practice to manipulate both sides of an equation in a problem such as this?
     
  13. Jun 6, 2012 #12

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Yes, somewhat indirectly.

    Rather you should do something like the following.

    Assume [itex]1+3+5+\dots+(2k-1)=k^2\ .[/itex]

    Now consider:

    [itex]1+3+5+\dots+(2k-1)+(2(k+1)-1)[/itex]
    [itex]=k^2+(2(k+1)-1)[/itex]   ... because of or assumption.

    [itex]=k^2+2k+1[/itex]

    [itex]=(k+1)^2[/itex]  Which is what we needed to show for the inductive step.​

    It's not that what you did is particularly wrong, it's just that it's not real clear that you're not somehow assuming the very thing you should be proving.
     
    Last edited: Jun 6, 2012
  14. Jun 6, 2012 #13
    It's generally frowned upon to work both sides at once, yeah. Usually, one would take [itex]k^2 + 2(k+1)-1[/itex] and manipulate it until it's clear the result is [itex](k+1)^2[/itex]. Working only in one direction ensures that no illegal operations or cancellations are done, even though it may be necessary to set both sides equal just to figure out how to do it.
     
  15. Jun 6, 2012 #14
    Well, I think I got it now! I have a list of mathematical induction to do. I'll try to solve the exercises using what you guys told me. I'll probably be back soon. Thanks guys!
     
  16. Jun 9, 2012 #15
    Prove by mathematical induction that n^3-n is divisible by 2 for all positive integral values of n.
    Please help me in solving this question!
     
  17. Jun 9, 2012 #16
    Please create a new thread for this.

    Also, show how you approached it so we can help you better!! :smile:

    As a start...try showing it is true for n=1..then assume it to be true for n=k......
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Mathematical induction problem
Loading...