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:
- Base case: let $ n = 1 $
\begin{align}
⌈\log_2(1+1)⌉ – 1 = 0 \\
1 – 1 = 0 \\
0 = 0
\end{align} - 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} - 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} - 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!
Best Answer
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$$