Results 1 to 7 of 7

Math Help - Proofs by Mathematical Induction

  1. #1
    Newbie
    Joined
    Nov 2006
    Posts
    15

    Proofs by Mathematical Induction

    ll
    Last edited by chillerbros17; February 28th 2007 at 02:21 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,962
    Thanks
    349
    Awards
    1
    Quote Originally Posted by chillerbros17 View Post
    1) Prove by Mathematical Induction:

    1 * 3 + 2 * 4 + 3 * 5 + . . . + n(n + 2) = n(n + 1)(2n + 7)/6 for all integers > 1
    Try this for n = 1:
    1*3 =? 1(1 + 1)(2*1 +7)/6

    3 =? 1*2*9/6

    3 =? 3 (Check!)

    Now assume the statement is true for some integer k. That is
    1*3 + 2*4 + ... + k(k + 2) = k(k + 1)(2k + 7)/6

    We need to show that it also holds for k + 1:
    1*3 + 2*4 + ... + k(k + 2) + (k + 1)(k + 3) = (k + 1)(k + 2)(2k + 9)/6

    We know that 1*3 + ... + k(k + 2) = k(k + 1)(2k + 7)/6 so use that in the above equation. Thus
    k(k + 1)(2k + 7)/6 + (k + 1)(k + 3) = (k + 1)(k + 2)(2k + 9)/6
    should be an identity.

    Multiply both sides by 6, then simplify:
    k(k + 1)(2k + 7) + 6(k + 1)(k + 3) = (k + 1)(k + 2)(2k + 9)

    (k^2 + k)(2k + 7) + 6(k^2 + 4k + 3) = (k^2 + 3k + 2)(2k + 9)

    2k^3 + 9k^2 + 7k + 6k^2 + 24k + 18 = 2k^3 + 15k^2 + 31k + 18

    2k^2 + 15k^2 + 31k + 18 = 2k^3 + 15k^2 + 31k + 18

    0 = 0 (Check!)

    Thus the proposition is true for k = 1, so it is true for all integer k >= 1.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by chillerbros17 View Post
    2) Prove by Mathematical Induction: 57 divides 7^n+2 + 8^2n+1 for all integers n> 1
    Let P(n) be the proposition: 57 divides 7^(n+2) + 8^(2n+1).

    (a) P(1) is true as 7^3+8^3 = 855 = 15*57

    (b) Now suppose for some k>=1, P(k) is true. Then 7^(k+2) + 8^(2k+1) = a*57
    for some positive integer a, or 8^(2k+1) = a*57 - 7^(k+2).

    Now:

    7^((k+1)+2) + 8^(2(k+1)+1) = 7*7^(k+2) + 64*8^(2k+1)

    ........................................= 7*7^(k+2) + 64*[a*57 - 7^(k+2)]

    ........................................= [7 - 64]* 7^(k+2) + 64*a*57

    ........................................= 57*[ -7^(k+2) + 64*a]

    Hence 7^((k+1)+2) + 8^(2(k+1)+1) is divisible by 57, which proves P(k+1),
    therfore with (a) this proves P(n) is true for all n>=1 by mathematical
    induction.

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,748
    Thanks
    648
    Hello, chillerbros17!

    Another approach to #1 . . .


    1) Prove by Mathematical Induction:
    . . 1·3 + 2·4 + 3·5 + . . . + n(n + 2) .= .n(n + 1)(2n + 7)/6 .for all integers > 1

    Verify S(1): .1·3 .= .1(2)(9)/6 . . 3 = 3 . . . true!

    Assume S(k) is true: .1·3 + 2·4 + 3·5 + ... + k(k + 2) .= .k(k + 1)(2k + 7)/6

    We want to prove that S(k+1) is true:
    . . 1·3 + 2·4 + 3·5 + ... + (k + 1)(k + 3) .= .(k + 1)(k + 2)(2[k+1] + 7)/6 .[1]
    written out here for reference ... so we'll recognize it later.


    Begin with S(k): .1·2 + 2·4 + 3·5 + ... + k(k + 2) .= .k(k + 1)(2k + 7)/6

    Add (k + 1)(k + 3) to both sides:
    . . 1·3 + 2·4 + 3·5 + ... + (k + 1)(k + 3) .= .k(k + 1)(2k + 7)/6 + (k + 1)(k + 3)

    The left side is the left side of [1].
    We must show that the right side is the right side of [1].


    . . . . . . . . . . . . . k(k + 1)(2k + 7) . . . . . . . . . . . . . . . k(k + 1)(2k + 7) + 6(k + 1)(k + 3)
    The right side is: .-------------------- + (k + 1)(k + 3) .= . -----------------------------------------
    . . . . . . . . . . . . . . . . . . 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6


    . . . . . . .(k + 1) [k(2k + 7) + 6(k + 3)] . . . (k + 1)(2kČ + 13k + 18)
    Factor: . ------------------------------------ .= .-----------------------------
    . . . . . . . . . . . . . . . . . 6 . . . . . . . . . . . . . . . . . . . 6


    . . . . . (k + 1)(k + 2)(2k + 9) . . .(k + 1)(k + 2)(2[k+1] + 7)
    . . . = .-------------------------- .= .--------------------------------
    . . . . . . . . . . . . 6 . . . . . . . . . . . . . . . . . . 6


    This is the right side of [1] . . . The induction proof is complete.

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Priya
    Guest

    sum of 1^k+ 2^k+ 3^k+ 4^k+...n^k

    could anyone help me out for this question...
    i think we need to use the general terms for the sum of n terms, sum of 1^2+ 2^2+...n^2..etc
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,962
    Thanks
    349
    Awards
    1
    Quote Originally Posted by Priya View Post
    could anyone help me out for this question...
    i think we need to use the general terms for the sum of n terms, sum of 1^2+ 2^2+...n^2..etc
    If you have a new question, please start it in a new thread.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Priya View Post
    could anyone help me out for this question...
    i think we need to use the general terms for the sum of n terms, sum of 1^2+ 2^2+...n^2..etc
    A complicated topic see the Power Sum article on MathWorld for details.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: November 7th 2010, 06:12 PM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. Mathematical Induction Proofs
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: April 6th 2008, 06:27 AM
  4. Proofs and Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 18th 2008, 11:11 PM
  5. Mathematical proofs
    Posted in the Discrete Math Forum
    Replies: 27
    Last Post: April 8th 2007, 11:36 AM

Search Tags


/mathhelpforum @mathhelpforum