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?

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – M Turgeon Jun 6 '12 at 17:16
  • $\begingroup$ Base case is $0$, $1$ (to allow use of the Fibonacci recursion) $\endgroup$ – John Engbers Jun 6 '12 at 17:18
  • $\begingroup$ Not that it matters for your problem, but as Ayman observed below, n! is a very loose upper bound. $\endgroup$ – Rick Decker Jun 6 '12 at 17:54
  • $\begingroup$ The bound is ridiculously bad, why do you need that ? $\endgroup$ – Lierre Jun 15 '12 at 17:38
43
$\begingroup$

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

$\endgroup$
  • 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 '12 at 17:19
  • $\begingroup$ Aren't you supposed to prove by induction? $\endgroup$ – Gigili Jun 6 '12 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 '12 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 '12 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 '12 at 4:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.