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?