As a way of simplifying my previous question: Number of nodes in AVL? I want to prove / find a contradiction example to the claim that:

2^{n}−1=Θ(Fibonacci(n 1) - 1)

Note: Θ (big theta) means both big omega and big O.

CodePudding user response：

It is not! Beacuse Fib(n 1) = (((sqrt(5) 1)/2)^{n 1} - ((1-sqrt(5))/2)^{n 1})/sqrt(5). Hence, Fib(n 1) = Theta((1 sqrt(5)/2)^{n 1}. As (1 sqrt(5))/2 < 2, we can conclude that ((1 sqrt(5))/2)^n \in o(2^n) (little-oh). Therefore, the claim is not correct.