0

I know the formula is: $n(h) = n(h-1) + n(h-2) + 1$

And I know it can be reduced as:

\begin{align} n(h) & = n(h-1) + n(h-2) + 1 \\[6pt] & \geq n(h-2) + n(h-2) + 1 \\[6pt] & \geq 2n(h-2) + 1 \\[6pt] & \geq 2n(h-2) \end{align}

After this step I don't understand the recurrence that would come after here. I was reading a proof online and they did this:

\begin{align} & \geq2n(h-2) \\[6pt] & \geq 2(2n(h-4)) \\[6pt] & \geq2(2(2n(h-6))) \end{align}

I'm not understanding that block. Why is each step multiplied by 2 and why is 2 more subtracted each time from the height? I'm having trouble visualizing it or something. Then the proof shows:

$$\geq2^in(h-2i)$$

I understand how they got that answer based on the pattern, and I can solve the rest of the proof, but I don't understand how that recursive pattern was chosen. I hope I'm making sense. If anyone can clarify this for me, I would appreciate it very much!

Michael Hardy
  • 1
David Velasquez
  • 251

1 Answers1

0

Let me try give a better visual explanation $$ \eqalign{ & Start \cr &N(h) > 2\cdot N(h-2) \ \ \ \ \ (1)\cr & Write\ for\ the\ first\ iteration \cr &> 2\cdot \bigl(\cdots\bigr) \cr &Use\ now\ for\ N(h-2)\ what\ you\ get\ from\ (1) when\ h=h-2 \cr &that\ is\ N(h-2) > 2 \cdot N(h-4) \ \ \ \ to\ get \cr &> 2\cdot \bigl(2 \cdot N(h-4)\bigr) \cr } $$ $\ldots$ and continue this way. In case this was not enough, we can see it with another way also. Consider : $$ \eqalign{ N(h) &> 2\cdot N(h-2) \cr N(h-2) &> 2\cdot N(h-4) \cr N(h-4) &> 2\cdot N(h-6) \cr &\cdots \cr N(h-2(i-1))& > 2\cdot N(h-2i) \cr } $$ and multiplying all of them we get $$ N(h) > 2^i\cdot N(h-2i) $$

nickchalkida
  • 1,495