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

Question

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!

Answer 1

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). $$