这个说法是否正确：`2^{n}−1=Θ(Fibonacci(n+1) - 1)`？
Is this claim correct: `2^{n}−1=Θ(Fibonacci(n+1) - 1)`?
作为简化我之前问题的一种方式：Number of nodes in AVL?我想证明/找到一个矛盾的例子来证明：
2^{n}−1=Θ(Fibonacci(n+1) - 1)
注： Θ (big theta) 表示大 omega 和大 O。
不是！因为 Fib(n+1) = (((sqrt(5)+1)/2)^{n+1} - ((1-sqrt(5))/2)^{n+1})/sqrt(5)。因此，Fib(n+1) = Theta((1+sqrt(5)/2)^{n+1}。由于(1+sqrt(5))/2 < 2，我们可以得出((1+sqrt(5))/2)^n \in o(2^n)（小哦）。因此，说法不正确。
作为简化我之前问题的一种方式：Number of nodes in AVL?我想证明/找到一个矛盾的例子来证明：
2^{n}−1=Θ(Fibonacci(n+1) - 1)
注： Θ (big theta) 表示大 omega 和大 O。
不是！因为 Fib(n+1) = (((sqrt(5)+1)/2)^{n+1} - ((1-sqrt(5))/2)^{n+1})/sqrt(5)。因此，Fib(n+1) = Theta((1+sqrt(5)/2)^{n+1}。由于(1+sqrt(5))/2 < 2，我们可以得出((1+sqrt(5))/2)^n \in o(2^n)（小哦）。因此，说法不正确。