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

There is no error.

1. When we consider a node $x$ of height $n$, say, in the induction step, our induction hypothesis is that the result is true for all nodes having height less than $n$. Thus, every node considered after the base case of height $0$ does have positive height: saying that we’re considering a node $x$ that has positive height is merely saying that we’re considering a node that isn’t part of the base case. If $x$ has height $1$, we’re just assuming the result for nodes of height $0$, and we’ve already proved that the result holds for them. If $x$ has height $2$, we’re assuming the result for nodes of height $0$ and $1$, and so on. This is just an instance of what is sometimes called strong (or complete) induction.
2. First, there is no harm in failing to use information if that information is not needed for the argument. However, in this case all of the information is used. First, we note that each child of $x$ has height less than $x$, so the induction hypothesis says that if $y$ is a child of $x$, the result is true for the subtree rooted at $y$: it contains at least $2^{\operatorname{bh}(y)}-1$ internal nodes. If $y$ is red, $\operatorname{bh}(y)=\operatorname{bh}(x)$, and the subtree rooted at $y$ contains at least $2^{\operatorname{bh}(x)}-1$ internal nodes. If $y$ is black, $\operatorname{bh}(y)=\operatorname{bh}(x)-1$, and the subtree rooted at $y$ contains at least $2^{\operatorname{bh}(x)-1}-1$ internal nodes. In all cases, therefore, the subtree rooted at $y$ contains at least $$\min\left\{2^{\operatorname{bh}(x)}-1,2^{\operatorname{bh}(x)-1}-1\right\}=2^{\operatorname{bh}(x)-1}-1$$ internal nodes, but we needed the information about both possible colors of child in order to establish this bound. We can now conclude that the subtree rooted at $x$ has at least $$\left(2^{\operatorname{bh}(x)-1}-1\right)+\left(2^{\operatorname{bh}(x)-1}-1\right)=2\cdot 2^{\operatorname{bh}(x)-1}-2=2^{\operatorname{bh}(x)}-2$$ internal nodes that are the internal nodes of the two subtrees rooted at the children of node $x$. Finally, node $x$ itself is an internal node of the subtree rooted at $x$ and is not in the subtrees rooted at the children of node $x$, so the subtree rooted at $x$ must in fact have at least $2^{\operatorname{bh}(x)}-2+1=2^{\operatorname{bh}(x)}-1$ internal nodes. This completes the induction step.