Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

1 Answer 1

up vote 38 down vote accepted

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

share|improve this answer
    
+1 for Elegance –  rckrd Jun 6 '12 at 17:10
1  
Given that $F_k \sim \varphi^k$, it's easy to see that $k!$ grows much faster than $F_k$. –  Ayman Hourieh Jun 6 '12 at 17:19
    
Aren't you supposed to prove by induction? –  Gigili Jun 6 '12 at 17:31
2  
@Gigili - This is exactly what I did. I only showed the inductive step as the OP seemed to know the rest. –  Ayman Hourieh Jun 6 '12 at 17:33
5  
Short and sweet. (Though you can make it even shorter: $k!+(k-1)!=(k+1)(k-1)!\le(k+1)!$.) –  Brian M. Scott Jun 6 '12 at 22:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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