Results 1 to 4 of 4

Math Help - Need Mathematical Induction help - 3 questions

  1. #1
    Newbie
    Joined
    Apr 2012
    From
    Singapore
    Posts
    3

    Need Mathematical Induction help - 3 questions

    Need help with the following questions.




    Thank you guys so much!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jan 2008
    From
    UK
    Posts
    484
    Thanks
    65

    Re: Need Mathematical Induction help - 3 questions

    What have you done so far? Where are you stuck?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2012
    From
    Singapore
    Posts
    3

    Re: Need Mathematical Induction help - 3 questions

    Well, I don't know where to begin for all three questions. In my worksheet these are the only 3 Mathematical Induction questions, and I was sick the day they went through this and didn't attend class. :/
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,280
    Thanks
    672

    Re: Need Mathematical Induction help - 3 questions

    let's work through number 3 in some detail, and perhaps you can try the other two on your own.

    first, this is how a proof by induction works:

    we prove that a formula works for some "starting number" (usually 0 or 1, but not always).

    then we prove that IF (and this is a big if) it works for "some number", then it will always work "for the next number".

    well, since we know it works for the starting number (let's call it "a"), then the "one to the next" part of the proof means it works for:

    a+1, (a+1)+1 = a+2, (a+2)+1 = a+3,.....,and so on (think of a string of dominoes, here).

    in short, it works for a, and every number after a.

    ok, now let's see a real-live induction proof in action. first, we state what we intend to prove:

    \sum_{r=1}^n r(r+4) = \frac{1}{6}n(n+1)(2n+13)

    ok, so "r" is just a dummy variable here (an INDEX), so that we don't have to write "....." in a really long sum. so we are going to use induction on "n" (that is, prove this is true for every integer n larger than or equal to 1).

    so, our starting number (or what is referred to as "the base case") will be in this instance, n = 1. so, we have to prove that our formula is correct when n = 1.

    \sum_{r=1}^1 r(r+4) = 1(1+4) = 5. that's the left-hand side (or LHS, as mathematicians are wont to write). now the RHS:

    for n = 1, this is: \frac{1}{6}(1)(1+1)(2(1)+13) = \frac{1}{6}(1)(2)(15) = \frac{30}{6} = 5.

    this shows that our formula works for n = 1. that's good

    now here is the point at which most people get confused. what we are about to do almost seems like cheating. we are going to ASSUME:

    \sum_{r=1}^n r(r+4) = \frac{1}{6}(n)(n+1)(2n+13) (even though the only "n" we know for sure works at this point is n = 1),

    and then we are going to PROVE that, given our assumption (or "induction hypothesis"):

    \sum_{r=1}^{n+1} = \frac{1}{6}(n+1)((n+1)+1)(2(n+1)+13). note all that has changed is we replaced "n" in our formula with "n+1".

    of course, if this works, then true for n = 1, will imply true for n = 2. and THEN, true for n = 2, will imply true for n = 3. and THEN....

    (this will save us the trouble of checking each case individually, which is GOOD, since there's an infinite number of positive integers, and i can't count that high).

    so, let's get to it: first note we can split the LHS side like so:

    \sum_{r=1}^{n+1} r(r+4) = \sum_{r=1}^n r(r+4) + (n+1)((n+1)+4)

    now the first term on the right side can be replaced (by our assumption), with:

    \frac{1}{6}n(n+1)(2n+13). so we have:

    \sum_{r=1}^{n+1} r(r+4) = \frac{1}{6}n(n+1)(2n+13) + (n+1)((n+1)+4).

    now, we need to do some, ugh, algebra, to see if we can clean this up a little:

    \frac{1}{6}n(n+1)(2n+13) + (n+1)((n+1)+4)

    = \frac{1}{6}(n(n+1)(2n+13) + 6(n+1)(n+5))

    =\frac{1}{6}((n^2+n)(2n+13) + 6(n^2 + 6n + 5))

    = \frac{1}{6}(2n^3 + 2n^2 + 13n^2 + 13n + 6n^2 + 36n + 30)

    = \frac{1}{6}(2n^3 + 21n^2 + 49n + 30)

    = \frac{1}{6}(2n^3 + 19n^2 + 30n + 2n^2 + 19n + 30)

    = \frac{1}{6}(n(2n^2 + 19n + 30) + (2n^2 + 19n + 30)) = \frac{1}{6}(n+1)(2n^2 + 19n + 30)

    (whew! i need to take a lil break after all that work!). ok, so let's march on:

     = \frac{1}{6}(n+1)(n+2)(2n+15) = \frac{1}{6}(n+1)((n+1) + 1)(2(n+1) + 13), which is the formula for "n+1".

    so we proved the formula true for "n" implies the formula is true for "n+1", in which case it holds for EVERY integer greater than or equal to 1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical induction
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: February 18th 2011, 01:25 PM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 8th 2010, 02:41 AM
  4. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 21st 2009, 03:28 PM
  5. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 18th 2009, 08:35 AM

Search Tags


/mathhelpforum @mathhelpforum