Results 1 to 9 of 9

Math Help - Mathematical induction

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    61

    Mathematical induction

    Use mathematical Induction to prove the formula for all integers n with the given values:

    11+15+19...+(4n+7)=2n^2+9n , n≥1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    737
    Thanks
    1
    Quote Originally Posted by flexus View Post
    Use mathematical Induction to prove the formula for all integers n with the given values:

    11+15+19...+(4n+7)=2n^2+9n , n≥1
    When n=1 the expression is true. That's the basis of the induction.

    Then you assume it's true for n=k, for some k \ge 1, and from that, you try and derive the truth of that expression for n = k+1.

    So by assuming that 11+15+19...+(4k+7)=2k^2+9k is true (this is your induction hypothesis), you want to prove that:

    11+15+19...+(4(k+1)+7)=2(k+1)^2+9(k+1).

    The way you would do that is to say that:

    11+15+19...+ (4k+7) + (4(k+1)+7) = 2k^2+9k + (4(k+1)+7)

    using the induction hypothesis.

    Now you want to show that the RHS is 2(k+1)^2+9(k+1).

    Match up what I've said above with what your text book says about proof by induction and try and work out the why of it rather than the what.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2009
    Posts
    61
    so im trying to show that the formula 2(k+1)^2+9(k+1) is true??
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    737
    Thanks
    1
    Do you actually understand how "mathematical induction" actually works?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2009
    Posts
    61
    Quote Originally Posted by Matt Westwood View Post
    Do you actually understand how "mathematical induction" actually works?
    im not gonna lie to you ...no im actually really trying to learn it because i caught the flu and missed class that day. there is an example in the book but it really does not help that's why i picked a question out of the book and trying to get anyone to work it out for me so i can see the pattern and use it as an example for my other problems. ....yea so these past couple post i must looked really dumb because i made no sense. im sorry.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    737
    Thanks
    1
    It works like this.

    You've got a proposition involving n that you're trying to trying to prove is true for all n. (The usual example is 1+2+3+...+n = \frac {n(n+1)}2).

    First you show it's true for n=1 (or n=0, or whatever, depends on the expression). In the above case, we have 1 = \frac {1(1+1)}2. This is called the "basis for the induction (or the "base case").

    Then you say: "Suppose this proposition is true for n=k, where k is any number \ge 1. Let's just, for a time being, assume that it's true." In the above example, we see that means 1+2+3+...+k = \frac {k(k+1)}2. This is called the "induction hypothesis".

    Now, if by assuming that it's true for k, we can prove it's true for k+1, we know that it will then be true for all n. This is called the "induction step".

    In the above, we want to show that 1+2+3+...+k+(k+1)= \frac {(k+1)((k+1)+1)}2 = \frac {(k+1)(k+2)}2.

    And we do that by saying:

    1+2+3+...+k+(k+1)

    = \frac {k(k+1)}2+(k+1) (we've used the induction hypothesis here, which we temporarily assumed true above)

    = \frac {(k+1)(k+2)}2 (by some fairly straightforward algebra)

    And so we have shown that:

    IF 1+2+3+...+k = \frac {k(k+1)}2 is true,

    THEN 1+2+3+...+k+(k+1)= \frac {(k+1)(k+2)}2 is true.

    And we already know that it's true when k=1.

    So, "by the principle of mathematical induction", or "by mathematical induction", or just "by induction", 1+2+3+...+n = \frac {n(n+1)}2 is true for ALL values of n.


    See how it works? Now see how I've applied the above to the question you asked.

    It's true for 1. And, if it's true for k, then it's true for k+1.

    Because it's true for 1, it's true for 1+1=2. And because it's true for 2, it's true for 2+1 = 3. And because it's true for 3, it's true for 3+1 = 4. And so on. Thus it's true for all numbers, by the fact that the numbers all go 1, 2, 3, 4, ... and so on "to infinity".

    There are several underlying philosophical questions underlying the validity of the above. So much so, that the "principle of induction" is taken as an axiom (that is, a "postulate", or "basic truth") of the system of natural numbers. So don't take it too much to heart if you're not sure it "makes sense" or feel that the reasoning seems a little flimsy - the logical justification is a deep question.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Sep 2009
    Posts
    61
    Quote Originally Posted by Matt Westwood View Post
    It works like this.

    You've got a proposition involving n that you're trying to trying to prove is true for all n. (The usual example is 1+2+3+...+n = \frac {n(n+1)}2).

    First you show it's true for n=1 (or n=0, or whatever, depends on the expression). In the above case, we have 1 = \frac {1(1+1)}2. This is called the "basis for the induction (or the "base case").

    Then you say: "Suppose this proposition is true for n=k, where k is any number \ge 1. Let's just, for a time being, assume that it's true." In the above example, we see that means 1+2+3+...+k = \frac {k(k+1)}2. This is called the "induction hypothesis".

    Now, if by assuming that it's true for k, we can prove it's true for k+1, we know that it will then be true for all n. This is called the "induction step".

    In the above, we want to show that 1+2+3+...+k+(k+1)= \frac {(k+1)((k+1)+1)}2 = \frac {(k+1)(k+2)}2.

    And we do that by saying:

    1+2+3+...+k+(k+1)

    = \frac {k(k+1)}2+(k+1) (we've used the induction hypothesis here, which we temporarily assumed true above)

    = \frac {(k+1)(k+2)}2 (by some fairly straightforward algebra)

    And so we have shown that:

    IF 1+2+3+...+k = \frac {k(k+1)}2 is true,

    THEN 1+2+3+...+k+(k+1)= \frac {(k+1)(k+2)}2 is true.

    And we already know that it's true when k=1.

    So, "by the principle of mathematical induction", or "by mathematical induction", or just "by induction", 1+2+3+...+n = \frac {n(n+1)}2 is true for ALL values of n.


    See how it works? Now see how I've applied the above to the question you asked.

    It's true for 1. And, if it's true for k, then it's true for k+1.

    Because it's true for 1, it's true for 1+1=2. And because it's true for 2, it's true for 2+1 = 3. And because it's true for 3, it's true for 3+1 = 4. And so on. Thus it's true for all numbers, by the fact that the numbers all go 1, 2, 3, 4, ... and so on "to infinity".

    There are several underlying philosophical questions underlying the validity of the above. So much so, that the "principle of induction" is taken as an axiom (that is, a "postulate", or "basic truth") of the system of natural numbers. So don't take it too much to heart if you're not sure it "makes sense" or feel that the reasoning seems a little flimsy - the logical justification is a deep question.
    thank you so much for the explanation. ok this is what i did. but now im stuck can you help me finish this.

    so from your example n=1 so (4)(1)+7=2(1)^2+9(1) which = 11=11 so true

    i assume that n=k , 11+15+19+...+(4K+7)=2K^2+9k is true

    now i must prove for (k+1) 11 +15 +19+...+(4(k+1)+7)=2(k+1)^2+9(k+1)
    11+15+19+...+(4(k+1)+7)=2(k^2+2k+1)+9k+1
    11+15+19+...+(4(k+1)+7)=2k^2+13K+11
    now i add the (4k+7) to both sides from the induction hypothesis
    11+15+19+...+(4k+7+4(k+1)+7=2k^2+9k+(4(k+1)+7)

    no this is where in stuck now.. what is next and how do i finish it. lol its like 3:18 am where in at. im dead tired.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Sep 2008
    From
    West Malaysia
    Posts
    1,261
    Quote Originally Posted by flexus View Post
    thank you so much for the explanation. ok this is what i did. but now im stuck can you help me finish this.

    so from your example n=1 so (4)(1)+7=2(1)^2+9(1) which = 11=11 so true

    i assume that n=k , 11+15+19+...+(4K+7)=2K^2+9k is true

    now i must prove for (k+1) 11 +15 +19+...+(4(k+1)+7)=2(k+1)^2+9(k+1)
    11+15+19+...+(4(k+1)+7)=2(k^2+2k+1)+9k+1
    11+15+19+...+(4(k+1)+7)=2k^2+13K+11
    now i add the (4k+7) to both sides from the induction hypothesis
    11+15+19+...+(4k+7+4(k+1)+7=2k^2+9k+(4(k+1)+7)

    no this is where in stuck now.. what is next and how do i finish it. lol its like 3:18 am where in at. im dead tired.

    HI

    When you need to prove that A = B , you must either start from A , then work it out to be B or vice versa .

     11 +15 +19+...+(4(k+1)+7)=2k^2+9k+(4(k+1)+7)


    11 +15 +19+...+(4k+7)+(4(k+1)+7)

    =2k^2+9k+4k+4+7

    =2k^2+4k+2+9k+9 and this will give you the desired result after simplifying


    4k+7 is the terms before that .
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Mar 2007
    Posts
    1,240

    Talking

    Quote Originally Posted by flexus View Post
    im not gonna lie to you ...no im actually really trying to learn [how to do induction proofs] because i caught the flu and missed class that day.
    To make up for the class(es) you missed, try here.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 31st 2010, 03:31 PM
  2. Mathematical induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 30th 2010, 05:54 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. mathematical induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 13th 2009, 05:29 PM
  5. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 18th 2009, 08:35 AM

Search Tags


/mathhelpforum @mathhelpforum