Cómo probar que $\mathrm{Fibonacci}(n) \leq n!$ $n\geq 0$

Question

Estoy tratando de demostrar por inducción, pero estoy atascado $$\mathrm{fib}(0) = 0 < 0! = 1;$$ $$\mathrm{fib}(1) = 1 = 1! = 1;$$

Caso Base n = 2,

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

Inductivo caso supongamos que es cierto para k(k+1)$k$ Intenta demostrar que $\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)$$

......

Cómo demostrarlo?

Answer 1

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