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
    Thanks
    1
    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, 01:10 PM
  2. Prove by induction?
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: March 1st 2010, 10:59 AM
  3. prove by induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 6th 2009, 10:16 PM
  4. prove by induction
    Posted in the Algebra Forum
    Replies: 3
    Last Post: June 19th 2008, 09:09 AM
  5. Prove by induction....
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 9th 2008, 12:37 PM

Search Tags


/mathhelpforum @mathhelpforum