I need to prove that for the given fibonacci sequence, with initial values:
f(1)=1
f(2)=2
f(n)=f(n-1)+f(n-2)
f(n) is belong to small o(2^n). I need to prove it without using the closed formula of fibonacci, or without proving it with generating functions etc.
I need a proof by induction/tree/iterations or something like that.
I proved that it's O(2^n), but can't prove for small o. I'll appreciated any help.