AVL tree worst case height proof
We want to show that the number of nodes $n$ in a height-balanced binary tree with height $h$ grows exponentially with $h$ and at least as fast as the Fibonacci sequence.  

Let $N_h$ denote the minimum number of nodes in a height-balanced binary tree having height $h$.  Recall that in a height-balanced binary tree of height $h$, the subtree rooted at one of the children of the root has height $h-1$, and the subtree rooted at the other child of the root has height $h-1$ or $h-2$.  Thus, $N_h &gt; N_{h-1} + N_{h-2}$.  Thus, $N_h$ is at least $f_h$, the $h$th term of the Fibonacci sequence, where $f_h \approx \phi^h / \sqrt{5}$ and $\phi$ is the golden ratio $\frac{1+\sqrt{5}}{2}$. 

So, if $n$ is the number of nodes in an AVL tree of height $h$, we have $n \ge \phi^h / \sqrt{5}$. Taking $\log_2$ of both sides, we get $h \le \frac{\log_2 n}{\log_2 \phi} + c = 1.4404 \log_2 n + c$, for some constant $c$. Thus, an AVL tree has height $h = O(\log n)$

An easier proof, if you don't care about the constants as much, is to observe that $N_h &gt; N_{h-1}+N_{h-2} &gt; 2N_{h-2}$.  Hence, $N_h$ grows at least as fast as $\sqrt{2}^h$.  So the number of nodes $n$ in a height-balanced binary tree of height $h$ satisfies $n &gt; \sqrt{2}^h$.  So $h \log_2 \sqrt{2} &lt; \log n$, which implies $h &lt; 2 \log n$.