Results 1 to 5 of 5

Thread: Math Induction

  1. #1
    Member
    Joined
    Sep 2006
    Posts
    221

    Math Induction

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

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

    Prove, using math induction:

    $\displaystyle a_n < \left(\frac{7}{4}\right)^{n} \ \forall$ integers $\displaystyle 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,002
    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,002
    Thanks
    1
    I will go ahead and use $\displaystyle f_{n}$ instead of $\displaystyle a_{n}$ because we are dealing with a Fibonacci sequence. Okey-doke.

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

    Show for n=1:

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

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

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

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

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

    $\displaystyle 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}$

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

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

    $\displaystyle \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,002
    Thanks
    1
    Sorry about that.

    it's rather redundant. Notice that $\displaystyle (\frac{49}{\not{44}^{4}})(\frac{\not{11}^{1}}{4})$
    $\displaystyle =\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: Mar 26th 2010, 02:24 PM
  2. Math Induction Help
    Posted in the Pre-Calculus Forum
    Replies: 12
    Last Post: Dec 6th 2009, 07:19 PM
  3. Math Induction
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: Dec 1st 2008, 09:24 AM
  4. Math Induction...PLEASE HELP!!!!!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Mar 16th 2008, 01:01 AM
  5. Math Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Apr 15th 2007, 02:28 PM

Search Tags


/mathhelpforum @mathhelpforum