Fibonacci Sequence: Induction Proof

**dlbsd** · August 14th 2009, 07:59 AM

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

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

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

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

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

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

**red_dog** · August 14th 2009, 08:38 AM

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

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

$\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 $\alpha>\beta=\frac{1+\sqrt{5}}{2}$ so the inequality (1) is true.

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

Thread: Fibonacci Sequence: Induction Proof

LinkBack

Thread Tools

Display

Fibonacci Sequence: Induction Proof

Similar Math Help Forum Discussions

Fibonacci Sequence - Induction Proof

Mathematical Induction for Fibonacci sequence

[SOLVED] Fibonacci sequence induction proof

Fibonacci sequence - prove by induction

Fibonacci, proof with induction

Search Tags