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: $
\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)
$
$
\forall n \in \mathbb{N}
$
(we define $
f_{ - 1}
=1$
)

Proof:

Note that the initial conditions hold and that: $
\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)
$
$
= \left( {\begin{array}{*{20}c}
{f_{n + 2} } & {f_{n + 1} } \\
{f_{n + 1} } & {f_n } \\

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

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

Lemma 2: Given: $
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: $
\left\| {A \cdot B} \right\| \leqslant \left\| A \right\| \cdot \left\| B \right\|
$

Proof:

$
\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: $
\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: $
\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)} } }
$
$
= \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: $
f_{n+1} \leqslant \left( {\sqrt 3 } \right)^n
$
$
\forall n \in \mathbb{N}
$

Proof:

By Lemma 2 : $
\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 $
\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: $
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 $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!