What to infer about maximum height of AVL tree from these three different formulae
Perhaps the simplest way out is to solve the recurrence explicitly. Let $m(h) = n(h) + 1$. Then $m(h)$ satisfies the recurrence
$$
m(h) = n(h) + 1 = n(h-1) + n(h-2) + 2 = m(h-1) + m(h-2).
$$
The initial conditions are $m(0) = 2$ and $m(1) = 3$. Define $F(h) = m(h-3)$, so that $F(3) = 2$, $F(4) = 3$, and $F(h) = F(h-1) + F(h-2)$ for $h &gt; 4$. It is well-known that
$$
F(n) = \frac{1}{\sqrt{5}} \left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right].
$$
Since $m(h) = F(h+3)$ and $n(h) = m(h)-1$, we see that $n(h) = F(h+3)-1$ and so
$$
\begin{align*}
n(h) &amp;= \frac{1}{\sqrt{5}} \left[\left(\frac{1+\sqrt{5}}{2}\right)^{h+3} - \left(\frac{1-\sqrt{5}}{2}\right)^{h+3}\right] - 1 \\ &amp;=
\frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h -
\frac{2-\sqrt{5}}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^h - 1.
\end{align*}
$$
The second term is very small, and in particular
$$
\frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h - 2 &lt; n(h) &lt; \frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h.
$$
This shows that
$$
\log_{(1+\sqrt{5}))/2} n(h) &lt; h + \log_{(1+\sqrt{5}))/2} &lt; \log_{(1+\sqrt{5}))/2} [n(h)+2],
$$
from which you can deduce whichever excellent bounds you want.