Results 1 to 5 of 5

Math Help - Math Induction

  1. #1
    Member
    Joined
    Sep 2006
    Posts
    221

    Math Induction

    Given a sequence of #'s a_1, a_2, a_3, a_4, \ldots which is defined by:

    a_1 = 1
    a_2 = 2
    a_n = a_{n-1} + a_{n-2}\ \ n \geq 3

    Prove, using math induction:

    a_n < \left(\frac{7}{4}\right)^{n} \ \forall integers n \geq 1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    Notice that this is the Fibonacci sequence.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    I will go ahead and use f_{n} instead of a_{n} because we are dealing with a Fibonacci sequence. Okey-doke.

    Prove f_{n}\leq{(\frac{7}{4})^{n}}

    Show for n=1:

    f_{1}\leq{\frac{7}{4}}\Rightarrow{1\leq{\frac{7}{4  }}}, TRUE.

    Assume f_{n-1}\leq{(\frac{7}{4})^{n-1}}; \;\ f_{2-1}\leq{(\frac{7}{4})^{2}}=1\leq{\frac{49}{16}}....TRUE

    Since f_{n}+f_{n-1}=f_{n+1}, we have:

    f_{n+1}\leq{(\frac{7}{4})^{n}}+(\frac{7}{4})^{n-1}=\frac{11}{4}(\frac{7}{4})^{n-1}

    f_{n+1}\leq{\frac{11}{4}(\frac{7}{4})^{n-1}}

    f_{n+1}\leq{(\frac{49}{44})(\frac{11}{4})(\frac{7}  {4})^{n-1}}=(\frac{7}{4})^{2}(\frac{7}{4})^{n-1}=(\frac{7}{4})^{n+1}

    f_{n+1}\leq{(\frac{7}{4})^{n+1}}

    f_{n+1}\leq{\frac{11}{4}(\frac{7}{4})^{n-1}}<(\frac{7}{4})^{n+1}

    \therefore, \;\ f_{n}\leq{(\frac{7}{4})^{n}}

    And the induction is complete.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2006
    Posts
    221
    Where did 49/44 mysteriously come from?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    Sorry about that.

    it's rather redundant. Notice that (\frac{49}{\not{44}^{4}})(\frac{\not{11}^{1}}{4})
    =\frac{49}{16}=(\frac{7}{4})^{2}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Math Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 26th 2010, 03:24 PM
  2. Math Induction Help
    Posted in the Pre-Calculus Forum
    Replies: 12
    Last Post: December 6th 2009, 08:19 PM
  3. Math Induction
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: December 1st 2008, 10:24 AM
  4. Math Induction...PLEASE HELP!!!!!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 16th 2008, 02:01 AM
  5. Math Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 15th 2007, 03:28 PM

Search Tags


/mathhelpforum @mathhelpforum