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!