How does $2N_{h-2}$ become $2^{h/2}$?

Question

I'm reading the Lecture 6 notes from MIT OCW Introduction to Algorithms, which discusses AVL trees, and I'm confused about one of the relations below:

Balance:

Worst when every node differs by 1 -- let $N_h$ = min # nodes in height-h AVL tree.

$\Longrightarrow N_h = N_{h-1} + N_{h-2}+1$

<p>$N_h &gt; 2N_{h-2}$</p>

<p>$\Longrightarrow N_h &gt; 2^{h/2}$</p>

<p>$\Longrightarrow h &lt; 2 \lg N_h$</p>

I don't understand how to arrive at $N_h > 2^{h/2}$ from $N_h > 2N_{h-2}$. In the lecture video (at T27:25), the instructor simply hand-waves it with:

This looks like two to the something. What's that something? H over two.

Can someone explain the math for that? Thanks.

Answer 1

It is recursion. Since it is true that $N_h>2\cdot N_{h-2}$ then it is also true that $N_h>2\cdot N_{h-2}>2\cdot2\cdot N_{h-4}$.

Continue like this until you reach $N_h>\underbrace{2\cdot2\cdots2}_{\mathrm{k\, times}}\cdot N_{h-2k}$.

Now, we do this until $k=h/2$ to get $N_h>2^{h/2}N_{0}$.