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.

2. 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.

3. Originally Posted by momof2
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)

4. 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!