Results 1 to 2 of 2

Math Help - Fibonacci Sequence: Induction Proof

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    21

    Fibonacci Sequence: Induction Proof

    Q: Let \alpha be any real number larger than \beta = (1/2)*(1 + \sqrt{5}) = 1.61 . . . .

    Prove by induction or otherwise that for n \geq 1, F_n < \alpha^2

    (Note that \beta is a solution of the equation x^2 = x+1)

    What I have so far:
    Base Case:
    n = 1
    \alpha > \beta > F_1 = 1
    \Rightarrow F_1 <  \alpha

    Inductive Step
    Assume F_k < \alpha^k for n = k

    F_{k+1} = F_k + F_{k-1} < F_k + F_k = 2*\alpha^k < \beta^2*\alpha^k = (\beta + 1)*\alpha^k < \alpha^2*\alpha^k = \alpha^{k+2}

    I've had other attempts but this is the closest I could come up with.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor red_dog's Avatar
    Joined
    Jun 2007
    From
    Medgidia, Romania
    Posts
    1,252
    Thanks
    5
    F_{k+1}=F_k+F_{k-1}<\alpha^k+\alpha^{k-1}=\alpha^{k-1}(\alpha+1)

    Now we have to prove that \alpha+1<\alpha^2 (1)

    \alpha+1<\alpha^2\Leftrightarrow\alpha^2-\alpha-1>0\Leftrightarrow\alpha\in\left(-\infty,\frac{1-\sqrt{5}}{2}\right)\cup\left(\frac{1+\sqrt{5}}{2},  \infty\right)

    But \alpha>\beta=\frac{1+\sqrt{5}}{2} so the inequality (1) is true.

    Then F_{k+1}<\alpha^{k-1}(\alpha+1)<\alpha^{k-1}\cdot\alpha^2=\alpha^{k+1}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci Sequence - Induction Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 19th 2011, 03:41 PM
  2. Mathematical Induction for Fibonacci sequence
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 2nd 2010, 01:01 AM
  3. [SOLVED] Fibonacci sequence induction proof
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 1st 2010, 10:22 AM
  4. Fibonacci sequence - prove by induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 23rd 2008, 05:19 PM
  5. Fibonacci, proof with induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 27th 2008, 10:19 AM

Search Tags


/mathhelpforum @mathhelpforum