Question

证明 >= fib(n) 当n>=0 fib :1 1 2 3 .fib(n) = fib(n-1)+fib(n-2)

Answer 1

n=1,2时,显然成立

假设n=k>=2时成立,即

k!>fib(k)

则n=k+1>=2时,注意到fib(n)是单增的

(k+1)!=k!(k+1)>2k!>fib(n)+fib(n)>fib(n-1)+fib(n)=fib(n+1)

也成立

所以对任意的n都成立