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?

  • 1
    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 prove2012-06-06
  • 0
    Base case is $0$, $1$ (to allow use of the Fibonacci recursion)2012-06-06
  • 0
    Not that it matters for your problem, but as Ayman observed below, n! is a very loose upper bound.2012-06-06
  • 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! $$

  • 1
    Given that $F_k \sim \varphi^k$, it's easy to see that $k!$ grows much faster than $F_k$.2012-06-06
  • 0
    Aren't you supposed to prove by induction?2012-06-06
  • 2
    @Gigili - This is exactly what I did. I only showed the inductive step as the OP seemed to know the rest.2012-06-06
  • 8
    Short and sweet. (Though you can make it even shorter: $k!+(k-1)!=(k+1)(k-1)!\le(k+1)!$.)2012-06-06
  • 0
    @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?2012-06-07
  • 0
    @null - 1) If want to know how induction works in general, I recommend checking out this question. It'll cover more details than I can in a comment: http://math.stackexchange.com/q/150166/45832012-06-07
  • 0
    @null - As for your second question, induction works just as well if you use 2 base cases. Have a look at the question I linked to, and see if it clears things up.2012-06-07
  • 0
    @AymanHourieh Can I say that when we assume that the formula is true for K, the K is actually a infinite loop from current base case to infinite, so when base case is true, we are trying to prove that (base case + 1) is also true, if (base case + 1) is true, then try to prove (base case + 2) is also true. Is it the way to understand it? Please correct me if I'm wrong2012-06-08
  • 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