8
$\begingroup$

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?

  • 0
    The bound is ridiculously bad, why do you need that ?2012-06-15

1 Answers 1

43

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

  • 0
    @null - Exactly, you got the idea! We prove that: 1) The base case $k_0$ is true, and 2) if $k$ is true, then $k+1$ is true. Using both proofs, we conclude that $k_0+1$, $k_0+2$, ... are all true.2012-06-08