# Prove that AVL tree has this kind of property with Fibonacci sequence

Q: Prove that for any AVL tree that has $$n$$ nodes ($$n\geq 1$$)
and has a height of $$h$$ this property is true:
$$n \geq F(h)$$ where $$F(h)$$ is the $$h$$-th element in the Fibonacci sequence:
$$F(0) =0, F(1)=1, F(n) = F(n-1) + F(n-2) ~~~~\forall n \geq 2$$

This is my go:

We know it is an AVL tree so $$h = \log_2{n}$$
Thus we need to prove that $$n \geq F( \log_2{n})$$

$$F(\log_2{n})= F(\log_2{n}-1)+F(\log_2{n}-2)$$
However I am stuck from here, I don't know what this helps me with and I am clueless on what to do next..
I would appreciate your help, thank you!

Let $$T$$ be an AVL tree of $$n > 0$$ nodes having height $$h \ge 0$$. You can prove that $$n > F(h)$$ by induction on $$h$$.

For $$h=0$$ the claim is true since $$n=1$$ and $$1 > 0 = F(0) = F(h)$$. For $$h=1$$ the claim is true since $$n \ge 2$$ and $$2 > 1 = F(1) = F(h)$$.

For $$h \ge 2$$, let $$r$$ be the root of the AVL tree. The subtree $$T_\ell$$ rooted in the left child of $$r$$ and the subtree $$T_r$$ rooted in the right child of $$r$$ exist are both AVL trees. Moreover, since $$T$$ is balanced, at least one tree $$T'$$ among $$T_\ell$$ and $$T_r$$ must have height $$h-1$$, while the other tree $$T''$$ must have height at least $$h-2$$.

By inductive hypothesis the number $$n'$$ of nodes of $$T'$$ is more than $$F(h-1)$$, while the number of nodes of $$T''$$ is more than $$F(h-2)$$. Therefore, the number of nodes $$n$$ is: $$n = 1 + n' + n'' \ge 3 + F(h-1) + F(h-2) = 3 + F(h) > F(h).$$