Results 1 to 4 of 4

Math Help - Induction

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    Induction

    f:\mathbb{N}\rightarrow\mathbb{N}
    f(1)=1 \ f(2)=2 \ f(3)=3 \ f(n)=f(n-1)+f(n-2)+f(n-3)
    \forall n\geq 4 Prove f(n)\leq 2^n \ \ \forall n\in\mathbb{N}
    P(1), P(2), P(3), P(4) are all true.
    Assume p(k) is true for a fixed but arbitrary k\geq 4 \ \ k\in\mathbb{Z}
    Prove P(K+1): \ f(k)+f(k-1)+f(k-2)\leq 2^{k+1}

    I am sort of stuck.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member girdav's Avatar
    Joined
    Jul 2009
    From
    Rouen, France
    Posts
    678
    Thanks
    32
    Since P(k-2) is true we have f(k-2)\leq 2^{k-2}, since P(k-1) is true we have f(k-1)\leq 2^{k-1} and since P(k) is true we have f(k)\leq 2^{k}. Now sum these inequalities.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by girdav View Post
    Since P(k-2) is true we have f(k-2)\leq 2^{k-2}, since P(k-1) is true we have f(k-1)\leq 2^{k-1} and since P(k) is true we have f(k)\leq 2^{k}. Now sum these inequalities.
    f(k+1)\leq 2^{k-2}+2^{k-1}+2^k=\frac{7}{4}2^k<2^{k+1}

    \Rightarrow f(k+1)\leq \frac{7}{4}2^k<2^{k+1}\Rightarrow f(k+1)\leq 2^{k+1}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member girdav's Avatar
    Joined
    Jul 2009
    From
    Rouen, France
    Posts
    678
    Thanks
    32
    It's ok.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 01:36 AM
  2. Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 11th 2010, 03:08 AM
  3. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  5. induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 19th 2008, 06:12 PM

Search Tags


/mathhelpforum @mathhelpforum