Results 1 to 2 of 2

Thread: Fibonacci Sequence: Induction Proof

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    21

    Fibonacci Sequence: Induction Proof

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

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

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

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

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

    $\displaystyle 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
    $\displaystyle F_{k+1}=F_k+F_{k-1}<\alpha^k+\alpha^{k-1}=\alpha^{k-1}(\alpha+1)$

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

    $\displaystyle \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 $\displaystyle \alpha>\beta=\frac{1+\sqrt{5}}{2}$ so the inequality (1) is true.

    Then $\displaystyle 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: Jan 19th 2011, 03:41 PM
  2. Mathematical Induction for Fibonacci sequence
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Dec 2nd 2010, 01:01 AM
  3. [SOLVED] Fibonacci sequence induction proof
    Posted in the Calculus Forum
    Replies: 2
    Last Post: Oct 1st 2010, 10:22 AM
  4. Fibonacci sequence - prove by induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 23rd 2008, 05:19 PM
  5. Fibonacci, proof with induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Aug 27th 2008, 10:19 AM

Search Tags


/mathhelpforum @mathhelpforum