Lesson 4

One should be careful when applying the method of complete induction. To illustrate this, recall that the Fibonacci sequence \[F_{0}=0, F_{1}=1, F_{2}=1, F_{3}=2, F_{4}=3, F_{5}=5, F_{6}=8, F_{7}=13, F_{8}=21, F_{9}=34\] is defined as follows: \(F_{0}=0\), \(F_{1}=1\) and \(F_{n}=F_{n-1}+F_{n-2}\), for all \(n \ge 2\). Fibonacci numbers grow exponentially. For example, one can prove that \(F_{n} \ge 2^{\frac{n}{2}}\), for all \(n \ge 6\).

Problem. Is this a correct proof?

The base case \(n=6\) is easy to check: \(F_{6}=8 \ge 8=2^{6/2}\). Induction step \(n-1\to n\) is also not difficult to verify: \[F_{n} =F_{n-1}+F_{n-2}\ge 2^{\frac{n-1}{2}}+2^{\frac{n-2}{2}}=2^{\frac{n}{2} -1}(\sqrt{2}+1)>2^{\frac{n}{2}-1}\cdot 2 = 2^{\frac{n}{2}}.\]