Prove that AVL tree has this kind of property with Fibonacci sequence
Let $T$ be an AVL tree of $n &gt; 0$ nodes having height $h \ge 0$. You can prove that $n &gt; F(h)$ by induction on $h$.

For $h=0$ the claim is true since $n=1$ and $1 &gt; 0 = F(0) = F(h)$.
For $h=1$ the claim is true since $n \ge 2$ and $2 &gt; 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) &gt; F(h).
$$