What to infer about maximum height of AVL tree from these three different formulae

I have came across following problem:


What is the maximum height of any AVL-tree with 7 nodes?

The recurrence giving number of nodes $n$ in the AVL tree for given height $h$ is as follows:


$n(h)=n(h-1)+n(h-2)+1$


$n(0)=1$


$n(1)=2$

So if we follow this recurrence, we get the height of the AVL tree with 7 nodes = 3 as follows

$n(2)=n(1)+n(0)+1=2+1+1=4$

$n(\color{red}{3})=n(2)+n(1)+1=4+2+1=7$

However I find two formulae, both listed on this page:

-
The first one is stricter one:


$h

-
The second one is rough estimate and it is taken from Goodrich's book:


$h

So with these different answers, I don't get what should I infer. Am I doing any miscalculations? Or should I just stick to what is yielded by recurrence and ignore formulae as they are mere estimates? Or should the first formula have ceil function to give perfect answer rather than the estimates as follows?

$h \color{red}{=} \color{red}{\lceil} 1.475 \times log_2(n(h)) - 1.475 \color{red}{\rceil}$

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 > 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) &= \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 \\ &=
\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 < n(h) < \frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h.
$$
This shows that
$$
\log_{(1+\sqrt{5}))/2} n(h) < h + \log_{(1+\sqrt{5}))/2} < \log_{(1+\sqrt{5}))/2} [n(h)+2],
$$
from which you can deduce whichever excellent bounds you want.

StackExchange Computer Science Q#55775, answer score: 2