Thread: Fibonacci Sequence: Induction Proof

Q: Let $\displaystyle \alpha$ be any real number larger than $\displaystyle \beta = (1/2)*(1 + \sqrt{5}) = 1.61 . . . .$

Prove by induction or otherwise that for $\displaystyle n \geq 1, F_n < \alpha^2$

(Note that $\displaystyle \beta$ is a solution of the equation $\displaystyle x^2 = x+1$)

What I have so far:
Base Case:
n = 1
$\displaystyle \alpha > \beta > F_1 = 1$
$\displaystyle \Rightarrow F_1 < \alpha$

Inductive Step
Assume $\displaystyle F_k < \alpha^k$ for n = k

$\displaystyle F_{k+1} = F_k + F_{k-1} < F_k + F_k = 2*\alpha^k < \beta^2*\alpha^k = (\beta + 1)*\alpha^k < \alpha^2*\alpha^k = \alpha^{k+2}$

I've had other attempts but this is the closest I could come up with.

$\displaystyle F_{k+1}=F_k+F_{k-1}<\alpha^k+\alpha^{k-1}=\alpha^{k-1}(\alpha+1)$

Now we have to prove that $\displaystyle \alpha+1<\alpha^2$ (1)

$\displaystyle \alpha+1<\alpha^2\Leftrightarrow\alpha^2-\alpha-1>0\Leftrightarrow\alpha\in\left(-\infty,\frac{1-\sqrt{5}}{2}\right)\cup\left(\frac{1+\sqrt{5}}{2}, \infty\right)$

But $\displaystyle \alpha>\beta=\frac{1+\sqrt{5}}{2}$ so the inequality (1) is true.

Then $\displaystyle F_{k+1}<\alpha^{k-1}(\alpha+1)<\alpha^{k-1}\cdot\alpha^2=\alpha^{k+1}$