Prove that a red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$

Question

I cannot understand the first paragraph of the proof, which comes from the known book Introduction to Algorithms, third-edition, and I consider it has some errors, could anyone help me check about it?

Possible errors:

1. It first prove the case $\text{height(x)=0},$ then it says "For inductive steps, consider a node $x$ that has positive height".

   From my understanding of inductive proof, the base case should be able to trigger the inductive statement. I mean: the "first domino" should trigger the next one, so the statement should be something like non-negative height.

2. It says "each child has a black-height of either $\text{bh}(x)$ or $\text{bh}(x)-1$", but when applying, only the latter is used: $(2^{\text{bh}(x)-1}-1)+(2^{\text{bh}(x)-1}-1)+1=2^{\text{bh}(x)}-1$.

---

Paragraph from the book:

Answer 1

The proof seems correct to me.

1) The base case proves the claim when the height of the subtree rooted at $x$ is $0$. The inductive step proves the claim for every subtree rooted at $x$ of positive height $h$ assuming that the claim is true for all subtrees of heights from $0$ to $h-1$. So the inductive step for $h=1$ is able to prove the claim for all subtrees of height $1$ using the fact that the claim is true for the base case, i.e., for all subtrees of height $0$. This is a standard proof by structural induction.

2) Each subtree $T_u$ rooted in a child $u$ of $x$ has a black-height $bh(u)$ of either $bh(x)$ or $bh(x)-1$ but, in any case, the height of $T_u$ is smaller than the height of the subtree $T_x$ rooted in $x$. This means that the induction hypothesis can be applied, showing that the number of internal nodes is at least:

• $2^{bh(x)}-1$ if $bh(u)=bh(x)$; or
• $2^{bh(x)-1}-1$ if $bh(u)=bh(x)-1$.

In any case the number of internal nodes of $T_u$ is at least the smaller of the above two quantities, i.e., $\min\{ 2^{bh(x)}-1, 2^{bh(x)-1}-1 \} = 2^{bh(x)-1}-1$. This means that the number of internal nodes in $T_x$ is at least:

$$ 2 \cdot ( 2^{bh(x)-1}-1 ) + 1 = 2^{bh(x)}-1. $$