Prove by induction that the height of a complete binary tree with n nodes is $⌈\log_2(n+1)⌉ - 1 $

Question

Proposition: $$ ⌈\log_2(n+1)⌉ - 1 = h, \quad \forall n \in \mathbb{N}$$

I am trying to prove this proposition via proof by induction; $h$ represents the height of any complete binary tree with $n$ nodes.

The definition of a complete binary tree that I am using:

A complete binary tree is a binary tree in which all the levels are completely filled except possibly the lowest one, which is filled from the left.

The bottom level of a complete binary tree must be filled in left-right order (second-to-bottom level nodes must have a left child if they have a right child, but not vice versa) and may not be completely filled.

What I have gotten so far:

1. Base case: let $ n = 1 $ \begin{align} ⌈\log_2(1+1)⌉ - 1 = 0 \\ 1 - 1 = 0 \\ 0 = 0 \end{align}
2. Inductive hypothesis: let $n = k \quad$ Essentially: $ n = k \implies n = k + 1$ \begin{align} ⌈\log_2(k+1)⌉ - 1 = h \implies ⌈\log_2(k+2)⌉ - 1 = h \end{align}
3. Proof by induction: I noticed that for any complete binary tree $$ 2^h \leq n \leq 2^{h+1} - 1$$ Substituting $n = k$: \begin{align} 2^h \leq k \leq 2^{h+1} - 1 \\ k = ⌈2^h⌉, \quad k = ⌊2^{h+1} - 1⌋ \end{align}
4. I think that the above values for $k$ represent two separate cases: a case where the number of nodes is a power of 2, and a case where the number of nodes is essentially a full binary tree to the $hth$ level. I am unsure how to include these in the inductive hypothesis and prove the proposition via induction

Any ideas/suggestions? Thanks!

Answer 1

Seeing that you have proved $$2^h \le n \le 2^{h+1}-1$$ then observe that $2^h + 1 \le n + 1 \le 2^{h+1}$ implies $$\log_2(2^h+1) \le \log_2(n+1) \le h+1$$

Since $2^h < 2^h + 1$ we get $h < \log_2(2^h+1) $ so that $h < \log_2(2^h+1) \le \log_2(n+1) \le h + 1$.

So $h < \log_2(n+1) \le h+1 $ implies that $$⌈\log_2(n+1)⌉ = h +1$$