Results 1 to 4 of 4

Math Help - 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: <br />
\left( {\begin{array}{*{20}c}<br />
   1 & 1  \\<br />
   1 & 0  \\<br /> <br />
 \end{array} } \right)^n  = \left( {\begin{array}{*{20}c}<br />
   {f_{n + 1} } & {f_n }  \\<br />
   {f_n } & {f_{n - 1} }  \\<br /> <br />
 \end{array} } \right)<br />
<br />
\forall n \in \mathbb{N}<br />
(we define <br />
f_{ - 1} <br />
=1 )

    Proof:

    Note that the initial conditions hold and that: <br />
\left( {\begin{array}{*{20}c}<br />
   {f_{n + 1} } & {f_n }  \\<br />
   {f_n } & {f_{n - 1} }  \\<br /> <br />
 \end{array} } \right) \cdot \left( {\begin{array}{*{20}c}<br />
   1 & 1  \\<br />
   1 & 0  \\<br /> <br />
 \end{array} } \right) = \left( {\begin{array}{*{20}c}<br />
   {f_{n + 1}  + f_n } & {f_{n + 1} }  \\<br />
   {f_n  + f_{n - 1} } & {f_n }  \\<br /> <br />
 \end{array} } \right)<br />
<br />
 = \left( {\begin{array}{*{20}c}<br />
   {f_{n + 2} } & {f_{n + 1} }  \\<br />
   {f_{n + 1} } & {f_n }  \\<br /> <br />
 \end{array} } \right)\blacksquare <br />

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

    Lemma 2: Given: <br />
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]<br />
we have: <br />
\left\| {A \cdot B} \right\| \leqslant \left\| A \right\| \cdot \left\| B \right\|<br />

    Proof:

    <br />
\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 } }  <br />

    Apply Cauchy-Schwarz: <br />
\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)} <br />

    Thus: <br />
\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)} } } <br />
<br />
 = \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 <br />

    Claim: <br />
f_{n+1}  \leqslant \left( {\sqrt 3 } \right)^n <br />
<br />
\forall n \in \mathbb{N}<br />

    Proof:

    By Lemma 2 : <br />
\left\| {\left( {\begin{array}{*{20}c}<br />
   1 & 1  \\<br />
   1 & 0  \\<br /> <br />
 \end{array} } \right)^n } \right\| \leqslant \left\| {\left( {\begin{array}{*{20}c}<br />
   1 & 1  \\<br />
   1 & 0  \\<br /> <br />
 \end{array} } \right)} \right\|^n  = \left( {\sqrt 3 } \right)^n <br />
but by Lemma 1 <br />
\left( {\begin{array}{*{20}c}<br />
   1 & 1  \\<br />
   1 & 0  \\<br /> <br />
 \end{array} } \right)^n  = \left( {\begin{array}{*{20}c}<br />
   {f_{n + 1} } & {f_n }  \\<br />
   {f_n } & {f_{n - 1} }  \\<br /> <br />
 \end{array} } \right)<br />

    Thus, by our definition in Lemma 2: <br />
f_{n + 1}  \leqslant \sqrt {f_{n + 1} ^2  + 2 \cdot f_n ^2  + f_{n - 1} ^2 }  \leqslant \left( {\sqrt 3 } \right)^n <br />
\blacksquare <br /> <br /> <br />
(since the Fibonacci numbers are positive)
    Last edited by PaulRS; September 16th 2008 at 03: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 f_0=0,f_1=1, \ f_{n+1}=f_n+f_{n-1}, \ n \geq 1. for n \geq 3 find the value of: \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; September 16th 2008 at 01: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: June 7th 2011, 08:52 AM
  2. Fibonacci number
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 28th 2010, 01:05 AM
  3. Fibonacci number Induction Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 17th 2009, 04:09 PM
  4. Fibonacci Number
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 5th 2008, 03:04 PM
  5. Fibonacci number
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 6th 2008, 09:59 PM

Search Tags


/mathhelpforum @mathhelpforum