How do I use induction to show that the $n$th term in the Fibonacci sequence is always less than or equal to $\left(\frac{1+\sqrt 5}{2}\right)^{n-1}$?

Question

I’m pulling this question from Invitation to Discrete Mathematics by Jiri Matousek and Jaroslav Nesetril. $\def\pgr{\left(\frac{1+\sqrt{5}}{2}\right)}$

They ask in an exercise to use induction to show that for the nth term in the Fibonacci sequence, $F_n \leq \pgr^{n-1}$.

This was my solution:

Base Case: $n=0$

$F_0 = 1 \leq \pgr^{-1}$ (True)

Inductive Hypothesis: $F_n \leq \pgr^{n-1}$

Inductive Step: Proving $F_{n+1} \leq \pgr^{n}$

$F_{n+1} = F_{n} + F_{n-1}$

$F_{n} + F_{n-1}\leq \pgr^{n-1} + \pgr^{n-2}$

$F_{n} + F_{n-1}\leq \left(1+\frac{1+\sqrt{5}}{2}\right) \pgr^{n-2}$

$1+\frac{1+\sqrt{5}}{2} = \pgr^2$ (This is the golden ratio)

$F_{n} + F_{n-1} \leq \pgr^{n-2+2}$

$F_{n} + F_{n-1} \leq \pgr^{n}$

$F_{n+1} \leq \pgr^{n}$

Obviously this uses strong induction, since I have to assume that if $F_n$ has a property, $F_{n-1}$ also holds that property.

I couldn’t figure out how to do it with basic induction. Is there such a way?

Answer 1

I don't think it is a worthwhile goal to blindly avoid strong induction in favour of weak induction. Theoretically is it known the two types of induction can prove exactly the same theorems, and in this case strong induction (or rather "two-level-deep" induction) fits the problem best, so that should be what you go for.

Writing down a mathematical proof is about communication, and the induction you have chosen is the one that communicates the ideas of your proof best. I think you should let it stay that way.

Answer 2

With $F_{-1},F_0,F_1=1,0,1$, the sequences $\{F_{n-1}\}_{n\ge 0}$ and $\{F_{n}\}_{n\ge 0}$ are a solution basis for the Fibonacci recursion $$a_{n+1}=a_n+a_{n-1}.$$ This means that the general solution is $$a_n=F_{n-1}a_0+F_na_1$$ (this is where an induction proof would be required). As $a_n=\phi^n$ is a solution, this gives $$ \phi^n=F_{n-1}+\phi F_n\implies \phi^{n-2}\le F_n\le \phi^{n-1}. $$