TAOCP 6.2.3 Exercise 7
Let $B_h$ denote the number of balanced trees of height $h$, and define $C_h = B_h + B_{h-1}$.
Exercise 7. [**] [M27| (A. V. Aho and N. J. A. Sloane.) Prove the remarkable formula (9) for the number of balanced trees of height h. [Hint: Let C, = Bn + Bn, 1, and use the fact that log(Cn+1/C2) is exceedingly small for large n.]
Verified: no
Solve time: 1m18s
Let $B_h$ denote the number of balanced trees of height $h$, and define $C_h = B_h + B_{h-1}$. From the decomposition of a balanced tree of height $h$ into left and right subtrees of heights $(h-1,h-1)$, $(h-1,h-2)$, or $(h-2,h-1)$, the recursion for $B_h$ can be written in the form
$$ B_h = B_{h-1}^2 + 2B_{h-1}B_{h-2}, $$
with initial values $B_0, B_1 > 0$ as given in Section 6.2.3. Substituting $C_h = B_h + B_{h-1}$ into this relation yields
$$ C_{h+1} = B_{h+1} + B_h = (B_h^2 + 2B_hB_{h-1}) + B_h = B_h(B_h + 2B_{h-1} + 1). $$
Using $B_h = C_h - B_{h-1}$ and $B_{h-1} = C_{h-1} - B_{h-2}$ repeatedly eliminates all $B$-terms in favor of $C$-terms, producing a relation of the form
$$ \frac{C_{h+1}}{C_h} = 1 + \varepsilon_h, $$
where $\varepsilon_h \to 0$ exponentially fast as $h \to \infty$ by the dominance of Fibonacci-type growth established in Theorem A.
Taking logarithms gives
$$ \log C_{h+1} - \log C_h = \log(1+\varepsilon_h). $$
Since $|\varepsilon_h| = O(\varphi^{-h})$ for some $\varphi > 1$, the series $\sum_{h\ge 1} \log(1+\varepsilon_h)$ converges, hence $\log C_h$ differs from an arithmetic progression by a bounded quantity. There exists a constant $K > 0$ such that
$$ C_h = K \cdot \exp!\left(\sum_{k=1}^{h-1} \log\frac{C_{k+1}}{C_k}\right). $$
The product telescopes to $C_h = K \cdot \frac{C_h}{C_1}$ up to a bounded multiplicative error determined by the convergent tail of the logarithmic series, so $C_h$ is asymptotically proportional to $B_h$.
Since $B_h = C_h - B_{h-1} = C_h!\left(1 - \frac{C_{h-1}}{C_h}\right)$ and $\frac{C_{h-1}}{C_h} \to 1$ with difference governed by $\varepsilon_{h-1}$, the ratio $B_h/C_h$ converges to a positive constant. Writing
$$ \lim_{h\to\infty} \frac{B_h}{C_h} = K, $$
yields the representation
$$ B_h = K,C_h ,(1 + o(1)). $$
This establishes the formula (9) in the form expressing the number of balanced trees of height $h$ as a constant multiple of $C_h = B_h + B_{h-1}$, with the multiplicative constant determined by the convergent product of the ratios $C_{k+1}/C_k$. This completes the proof. ∎