How to prove that $\mathrm{Fibonacci}(n) \leq n!$, for $n\geq 0$

Question

I am trying to prove it by induction, but I'm stuck $$\mathrm{fib}(0) = 0 < 0! = 1;$$ $$\mathrm{fib}(1) = 1 = 1! = 1;$$

Base case n = 2,

$$\mathrm{fib}(2) = 1 < 2! = 2;$$

Inductive case assume that it is true for ~~(k+1)~~ $k$ Try to prove that $\mathrm{fib}(k+1) \leq(k+1)!$

$$\mathrm{fib}(k+1) = \mathrm{fib}(k) + \mathrm{fib}(k-1) \qquad(LHS)$$

$$(k+1)! = (k+1) \times k \times (k-1) \times \cdots \times 1 = (k+1) \times k! \qquad(RHS)$$

......

How to prove it?

By the way, you have to assume it is true for $k$, not for $k+1$. Otherwise, you are simply assuming what you want to prove — M Turgeon, Jun 6, 2012 at 17:16
Base case is $0$, $1$ (to allow use of the Fibonacci recursion) — John Engbers, Jun 6, 2012 at 17:18
Not that it matters for your problem, but as Ayman observed below, n! is a very loose upper bound. — Rick Decker, Jun 6, 2012 at 17:54

Ayman Hourieh · Accepted Answer · 2012-06-06 17:09:01Z

43

$$ F_{k+1} = F_k + F_{k-1} \le k! + (k - 1)! \le k! + k! \le 2 k! \le (k + 1) k! $$

answered Jun 6, 2012 at 17:09

Ayman Hourieh

38.6k5 gold badges98 silver badges154 bronze badges

1

$\begingroup$ Given that $F_k \sim \varphi^k$, it's easy to see that $k!$ grows much faster than $F_k$. $\endgroup$
– Ayman Hourieh
Jun 6, 2012 at 17:19
$\begingroup$ Aren't you supposed to prove by induction? $\endgroup$
– Gigili
Jun 6, 2012 at 17:31
2

$\begingroup$ @Gigili - This is exactly what I did. I only showed the inductive step as the OP seemed to know the rest. $\endgroup$
– Ayman Hourieh
Jun 6, 2012 at 17:33
8

$\begingroup$ Short and sweet. (Though you can make it even shorter: $k!+(k-1)!=(k+1)(k-1)!\le(k+1)!$.) $\endgroup$
– Brian M. Scott
Jun 6, 2012 at 22:11
$\begingroup$ @AymanHourieh That's elegant.But sorry I have two stupid question : 1) How can we prove something by the assumption like f(k) <= k!. 2) We only assume that f(k) <= k!, why we still can assume that f(k-1) <= (k-1)!. Is prove by induction logically correct? $\endgroup$
– Timeless
Jun 7, 2012 at 4:02

| Show 4 more comments

1 Answer 1