Height of AVL tree with balance condition of 2
Let $T_h$ denote the minimal number of nodes that a standard AVL tree of height $h$ could have.
If $h&gt;0$, then there's the root and two subtrees. One of the subtrees must have height $h-1$. The other must have height at least $h-2$, otherwise it's not a valid AVL tree. So we have the recurrence:
$$T_h = T_{h-1} + T_{h-2} + 1$$
And we can throw in $T_0 = 0$ and $T_1 = 1$ for obvious reasons.
The easy way to solve the recurrence is to denote $F_h = T_h + 1$. Then:
$$\begin{align*}F_0 &amp; = 1 \\ F_1 &amp; = 2 \\ F_h &amp; = F_{h-1} + F_{h-2}\end{align*}$$
That is, they're Fibonacci numbers with the sequence offset by 3.
Since:
$$F_h \approx \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^{h+3}$$
Inverting this, we get:
$$h \approx \frac{1}{\log \left( \frac{1 + \sqrt{5}}{2} \right)} \log \left( T_h \right) + 3$$
And that is where the 1.44 comes from.
So what you need is to solve the recurrence:
$$U_h = U_{h-1} + U_{h-3} + 1$$
with suitable initial conditions.
If you can't think of a clever way to do this, you can do it the not-clever-but-always-works way by observing that:
$$\begin{bmatrix} U_h \\ U_{h-1} \\ U_{h-2} \\ 1\end{bmatrix} = \begin{bmatrix} 1 &amp; 0 &amp; 1 &amp; 1 \\ 1 &amp; 0 &amp; 0 &amp; 0 \\ 0 &amp; 1 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; 0 &amp; 1\end{bmatrix} \begin{bmatrix} U_{h-1} \\ U_{h-2} \\ U_{h-3} \\ 1\end{bmatrix}$$
Therefore:
$$\begin{bmatrix} U_{h+2} \\ U_{h+1} \\ U_{h} \\ 1\end{bmatrix} = \begin{bmatrix} 1 &amp; 0 &amp; 1 &amp; 1 \\ 1 &amp; 0 &amp; 0 &amp; 0 \\ 0 &amp; 1 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; 0 &amp; 1\end{bmatrix}^{h} \begin{bmatrix} U_{2} \\ U_{1} \\ U_{0} \\ 1\end{bmatrix}$$
Next, perform eigendecomposition on the matrix. Let:
$$M = \begin{bmatrix} 1 &amp; 0 &amp; 1 &amp; 1 \\ 1 &amp; 0 &amp; 0 &amp; 0 \\ 0 &amp; 1 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; 0 &amp; 1\end{bmatrix}$$
Suppose you can find a matrix $Q$ and a diagonal matrix $\Lambda$ such that $M = Q \Lambda Q^{-1}$. Then:
$$M^h = Q \Lambda^h Q^{-1}$$
Taking the power of a diagonal matrix is trivial, and this should give you a closed form. You will then need to find an approximate inverse to solve your problem.