Results 1 to 4 of 4

Thread: Fibonacci number proof

  1. #1
    Newbie
    Joined
    Sep 2008
    Posts
    1

    Fibonacci number proof

    The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, 21, 34, .... In general, the Fibonacci numbers are defined by f sub(1) = 1, f sub(2) = 1, and for n>or= 3, f sub(n) = f sub(n-1) + f sub(n-2). Prove that the nth Fibonacci number f sub(n) satisfies f sub(n) < 2^n.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    Yes, I think induction is the best way to approach this.

    You need to think of a recursive way of writing a term of the series in terms of previous ones. Establish that the fact you are trying to prove holds for a couple terms (only one is needed but perhaps a couple will be helpful). The assume that this is true for all i<j. Then show that i -> j, that is i implies j and you have proved it by induction.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by momof2 View Post
    The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, 21, 34, .... In general, the Fibonacci numbers are defined by f sub(1) = 1, f sub(2) = 1, and for n>or= 3, f sub(n) = f sub(n-1) + f sub(n-2). Prove that the nth Fibonacci number f sub(n) satisfies f sub(n) < 2^n.
    Lemma 1: $\displaystyle
    \left( {\begin{array}{*{20}c}
    1 & 1 \\
    1 & 0 \\

    \end{array} } \right)^n = \left( {\begin{array}{*{20}c}
    {f_{n + 1} } & {f_n } \\
    {f_n } & {f_{n - 1} } \\

    \end{array} } \right)
    $ $\displaystyle
    \forall n \in \mathbb{N}
    $ (we define $\displaystyle
    f_{ - 1}
    =1$ )

    Proof:

    Note that the initial conditions hold and that: $\displaystyle
    \left( {\begin{array}{*{20}c}
    {f_{n + 1} } & {f_n } \\
    {f_n } & {f_{n - 1} } \\

    \end{array} } \right) \cdot \left( {\begin{array}{*{20}c}
    1 & 1 \\
    1 & 0 \\

    \end{array} } \right) = \left( {\begin{array}{*{20}c}
    {f_{n + 1} + f_n } & {f_{n + 1} } \\
    {f_n + f_{n - 1} } & {f_n } \\

    \end{array} } \right)
    $$\displaystyle
    = \left( {\begin{array}{*{20}c}
    {f_{n + 2} } & {f_{n + 1} } \\
    {f_{n + 1} } & {f_n } \\

    \end{array} } \right)\blacksquare
    $

    Given $\displaystyle
    A \in M_{n \times m} \left( \mathbb{R} \right)/A = \left[ {a_{i,j} } \right]
    $ we'll define: $\displaystyle
    \left\| A \right\| = \sqrt {\sum\nolimits_{i = 1}^n {\sum\nolimits_{j = 1}^m {a_{i,j} ^2 } } }
    $

    Lemma 2: Given: $\displaystyle
    A \in M_{n \times m} \left( \mathbb{R} \right),B \in M_{m \times p} \left( \mathbb{R} \right)/A = \left[ {a_{i,j} } \right],B = \left[ {b_{i,j} } \right]
    $ we have: $\displaystyle
    \left\| {A \cdot B} \right\| \leqslant \left\| A \right\| \cdot \left\| B \right\|
    $

    Proof:

    $\displaystyle
    \left\| {A \cdot B} \right\|^2 = \sum\nolimits_{i = 1}^n {\sum\nolimits_{j = 1}^p {\left( {\sum\limits_{k = 1}^m {a_{i,k} \cdot b_{k,j} } } \right)^2 } }
    $

    Apply Cauchy-Schwarz: $\displaystyle
    \left( {\sum\limits_{k = 1}^m {a_{i,k} \cdot b_{k,j} } } \right)^2 \leqslant \sum\limits_{k = 1}^m {\left( {a_{i,k} ^2 } \right)} \cdot \sum\limits_{k = 1}^m {\left( {b_{k,j} ^2 } \right)}
    $

    Thus: $\displaystyle
    \left\| {A \cdot B} \right\|^2 \leqslant \sum\nolimits_{i = 1}^n {\sum\nolimits_{j = 1}^p {\sum\limits_{k = 1}^m {\left( {a_{i,k} ^2 } \right)} \cdot \sum\limits_{k = 1}^m {\left( {b_{k,j} ^2 } \right)} } }
    $$\displaystyle
    = \sum\nolimits_{i = 1}^n {\sum\limits_{k = 1}^m {\left( {a_{i,k} ^2 } \right)} \cdot \overbrace {\sum\nolimits_{j = 1}^p {\sum\limits_{k = 1}^m {\left( {b_{k,j} ^2 } \right)} } }^{\left\| B \right\|^2 }} = \left\| A \right\|^2 \cdot \left\| B \right\|^2 \blacksquare
    $

    Claim: $\displaystyle
    f_{n+1} \leqslant \left( {\sqrt 3 } \right)^n
    $ $\displaystyle
    \forall n \in \mathbb{N}
    $

    Proof:

    By Lemma 2 : $\displaystyle
    \left\| {\left( {\begin{array}{*{20}c}
    1 & 1 \\
    1 & 0 \\

    \end{array} } \right)^n } \right\| \leqslant \left\| {\left( {\begin{array}{*{20}c}
    1 & 1 \\
    1 & 0 \\

    \end{array} } \right)} \right\|^n = \left( {\sqrt 3 } \right)^n
    $ but by Lemma 1 $\displaystyle
    \left( {\begin{array}{*{20}c}
    1 & 1 \\
    1 & 0 \\

    \end{array} } \right)^n = \left( {\begin{array}{*{20}c}
    {f_{n + 1} } & {f_n } \\
    {f_n } & {f_{n - 1} } \\

    \end{array} } \right)
    $

    Thus, by our definition in Lemma 2: $\displaystyle
    f_{n + 1} \leqslant \sqrt {f_{n + 1} ^2 + 2 \cdot f_n ^2 + f_{n - 1} ^2 } \leqslant \left( {\sqrt 3 } \right)^n
    \blacksquare


    $ (since the Fibonacci numbers are positive)
    Last edited by PaulRS; Sep 16th 2008 at 02:19 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    PaulRS's solution is a nice non-inductive proof. the proof by induction is much easier and, well, very boring! here's a realted problem for those who are interested:

    as usual we define Fibonacci sequence by $\displaystyle f_0=0,f_1=1, \ f_{n+1}=f_n+f_{n-1}, \ n \geq 1.$ for $\displaystyle n \geq 3$ find the value of: $\displaystyle \left \lfloor f_n^{\frac{2}{n-1}} \right \rfloor.$

    Edit: actually PaulRS's solution is not entirely non-inductive since induction is needed to prove Lemma 1. but his solution is creative and that is very important!
    Last edited by NonCommAlg; Sep 16th 2008 at 12:55 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Fibonacci Number Proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jun 7th 2011, 07:52 AM
  2. Fibonacci number
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 28th 2010, 12:05 AM
  3. Fibonacci number Induction Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 17th 2009, 03:09 PM
  4. Fibonacci Number
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 5th 2008, 02:04 PM
  5. Fibonacci number
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 6th 2008, 08:59 PM

Search Tags


/mathhelpforum @mathhelpforum