Results 1 to 2 of 2

Math Help - Prove each of the following by induction

  1. #1
    Member
    Joined
    Jan 2010
    Posts
    232

    Prove each of the following by induction

    As the title says, prove each of the following by induction:

    a) \sum_{j=1}^nj2^j=(n-1)2^{n+1}+2 for every positive integer n

    b) 4^n<n! for all integers n>8

    c) n^2-10n+8 is positive for all n\geq10

    d) 3 divides n^3+2n for all positive integers n

    Show your work, of course.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Hello Runty
    Quote Originally Posted by Runty View Post
    As the title says, prove each of the following by induction:

    a) \sum_{j=1}^nj2^j=(n-1)2^{n+1}+2 for every positive integer n

    b) 4^n<n! for all integers n>8

    c) n^2-10n+8 is positive for all n\geq10

    d) 3 divides n^3+2n for all positive integers n

    Show your work, of course.
    I'll leave all the peripheral bits of the proofs to you. But here are the algebraic proofs that P(n) \Rightarrow P(n+1).

    a) P(n) is the propositional function: \sum_{j=1}^nj2^j=(n-1)2^{n+1}+2

    Then P(n)
    \Rightarrow \sum_{j=1}^{n+1}j2^j=(n-1)2^{n+1}+2+(n+1)2^{n+1}
    =2n.2^{n+1}+2

    =([n+1]-1)2^{[n+1]+1}+2
    \Rightarrow P(n+1)
    b) P(n) is the propositional function: 4^n<n!

    Then P(n)
    \Rightarrow 4^{n+1}<4.n!
    <(n+1).n! for n>8

    <(n+1)!
    \Rightarrow P(n+1)
    c) P(n) is the propositional function: n^2-10n+8 > 0

    Now (n+1)^2 -10(n+1) +8=n^2 -8n -1
    =n^2-10n+8 +2n -9
    > n^2-10n+8 since 2n-9>0 when n \ge 10
    Hence P(n) \Rightarrow (n+1)^2 -10(n+1) +8>0
    \Rightarrow P(n+1)
    d) I'll leave this to you. It's rather similar to (c).

    Expand and simplify (n+1)^3 + 2(n+1). Then express the resulting expression in the form n^3 + 2n + f(n), and you'll find that f(n) is divisible by 3.

    Can you fill in all the gaps?

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  2. Prove by induction?
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: March 1st 2010, 09:59 AM
  3. prove by induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 6th 2009, 09:16 PM
  4. prove by induction
    Posted in the Algebra Forum
    Replies: 3
    Last Post: June 19th 2008, 08:09 AM
  5. Prove by induction....
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 9th 2008, 11:37 AM

Search Tags


/mathhelpforum @mathhelpforum