Results 1 to 2 of 2

Thread: 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) $\displaystyle \sum_{j=1}^nj2^j=(n-1)2^{n+1}+2$ for every positive integer $\displaystyle n$

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

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

    d) $\displaystyle 3$ divides $\displaystyle n^3+2n$ for all positive integers $\displaystyle 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) $\displaystyle \sum_{j=1}^nj2^j=(n-1)2^{n+1}+2$ for every positive integer $\displaystyle n$

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

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

    d) $\displaystyle 3$ divides $\displaystyle n^3+2n$ for all positive integers $\displaystyle 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 $\displaystyle P(n) \Rightarrow P(n+1)$.

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

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

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

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

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

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

    Expand and simplify $\displaystyle (n+1)^3 + 2(n+1)$. Then express the resulting expression in the form $\displaystyle n^3 + 2n + f(n)$, and you'll find that $\displaystyle f(n)$ is divisible by $\displaystyle 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: Jun 29th 2010, 12:10 PM
  2. Prove by induction?
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: Mar 1st 2010, 09:59 AM
  3. prove by induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 6th 2009, 09:16 PM
  4. prove by induction
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Jun 19th 2008, 08:09 AM
  5. Prove by induction....
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Apr 9th 2008, 11:37 AM

Search Tags


/mathhelpforum @mathhelpforum