# Why is a recurrence of $2N_{h-2}$ equal to $2^{h/2}$?

I was watching video 7. Binary Trees, Part 2: AVL, where professor Erik Demaine stated that $$2N_{h-2} = 2^{h/2\text{ (or maybe with floor or something... maybe it's ceiling)}}$$ where $$N$$ stands for the number of nodes in a subtree of height $$h-2$$. Can someone explain me in more detail why this recursion can be solved like this?

Let $$N_h$$ denote the minimum number of nodes in a height-balanced tree of height $$h$$. Given a height-balanced tree of height $$h$$, without loss of generality assume the left child of the root has height $$h-1$$. The right child must have height $$h-1$$ or $$h-2$$, and to get the smallest possible values (the worst-case), assume it has height $$h-2$$. Then, the number of nodes in the given tree is at least $$N_{h-1} + N_{h-2} + 1$$, because there are at least $$N_{h-1}$$ nodes in the left subtree of the root, at least $$N_{h-2}$$ nodes (in the worst case) in the right subtree of the root, and the root itself contributes 1 to the count of number of nodes.

Thus, we get that $$N_h \ge N_{h-1} + N_{h-2} + 1$$. One can pay attention to constants and show the terms $$N_1, N_2, \ldots$$ grow at least as fast as the Fibonacci sequence. The $$h$$th term of the Fibonacci sequence is at least $$c \psi^h$$ for some constant $$c$$ and the golden ratio $$\psi$$. Hence, the terms of the sequence grow exponentially fast. This can be shown to imply that $$h$$ is at most $$1.44 \log n$$, and so we get that $$h=O(\log n)$$ for a height-balanced tree with height $$h$$ and $$n$$ nodes.

But, in asymptotic analysis, you can be "sloppy" and ignore constants, and it suffices to use the fact that $$N_{h-1}+1 > N_{h-2}$$ to get that $$N_h \ge N_{h-1}+N_{h-2}+1 > N_{h-2}+N_{h-2}$$. Thus, we have $$N_h > 2N_{h-2}$$. This means the terms of the sequence $$N_1, N_2,\ldots$$ grow fast enough that they at least double every two terms: $$N_3 > 2N_1$$, $$N_5 > 2N_3 > 4N_1$$, and in general, $$N_h > N_1 2^{h/2} = N_1 (\sqrt{2})^h$$. This implies that $$h < 2 \log n$$, and so $$h = O(\log n)$$.

In general, to show $$h=O(\log n)$$ for a height-balanced tree, it suffices to show that the number of nodes $$n$$ grows exponentially with $$h$$. The crude analysis given above is good enough to obtain this result.

In the lecture it was shown that $$N_h \geq 2N_{h-2}$$. You can obtain the bound of $$2^{h/2}$$ for this recurrence by continued expansion of the r.h.s., also called unrolling the recurrence. E.g. :

$$N_h \geq 2N_{h-2} = 2 * (2N_{h-4}) = 2*(2*(2N_{h-6})) = 2(2(2(...(2N_0)...)))$$.

This expansion will continue until you reach $$N_0$$, which is 1, I think since the tree with height 0 has only the root. The number of times you can subtract 2 from $$h$$ is at most $$\lceil h/2\rceil$$, which is also the number of 2's in the expansion. Thus you have $$N_h \geq 2^{\lceil h/2\rceil}$$.