Prove $ \lg (n + 1) - 1\le h \le \lg n\implies h=\lfloor\lg n\rfloor$

Question

For integer $n>0$ and integer $h$ prove ($lg$ means $log_2$) $$ \lg (n + 1) - 1\le h \le \lg n\implies h=\lfloor\lg n\rfloor $$

I'm thinking I may use $x-1<\lfloor x \rfloor \le x \le \lceil x \rceil<x+1$, but it seems like I cannot because we have $\lg (n + 1) - 1$ instead of $\lg n - 1$.

I tried some values and this seems true, the only integral solution in $[\lg (n + 1) - 1,\lg n]$ indeed seems to be $\lfloor\lg n\rfloor$

n =1 [0,0]
n =2 [0.584963,1]
n =3 [1,1.58496]
n =4 [1.32193,2]
n =5 [1.58496,2.32193]
n =6 [1.80735,2.58496]

---

The background (which I think is irrelevant to this question) is that I'm trying to answer

Show that an n-element heap has height $\lfloor\lg n\rfloor$ [1]

because for heap (similar to a complete binary tree in terms of tree shape), every level (from $0,...,h-1$) except the last one (level $h$) must be full. Heap of height $h$ must contain a min of $2^h$ and a max of $2^{h+1}-1$ elements. This gives $2^h\le n \le 2^{h+1}-1$ and upon solving I obtained the above inequality.

[1] Introduction to Algorithms, Fourth Edition. MIT press.

Answer 1

This has nothing to do with logarithms (except that the $\lg$ function is increasing).

If $a$ and $b$ are any two real numbers with $a>b$, and if $h$ is an integer such that $a-1\le h\le b$, then $h=\lfloor b\rfloor$. This is because $a-1\le h\implies b-1<h$, so $b-1<h\le b$, which is simply the definition of the floor function.

Now just put $a=\lg(n+1)$ and $b=\lg n$.

Answer 2

$h\leq\lg n$ implies $h\leq\lfloor\lg n\rfloor$; if $h<\lfloor\lg n\rfloor$, then $h\leq\lfloor\lg n\rfloor-1\leq\lg n-1<\lg(n+1)-1$.

Answer 3

$$ \lg (n + 1) > \lg (n) \geq \lfloor\lg n\rfloor, \quad \lg n < \lfloor\lg n\rfloor + 1 \\ \implies \lfloor\lg n\rfloor - 1 < h < \lfloor\lg n\rfloor + 1 \\ \implies h = \lfloor\lg n\rfloor $$

Answer 4

$$ h\geq \log_2(n+1) - 1 > \log_2 n -1,\ \implies h+1 > \log_2 n.$$

Also, $$ h \leq \log_2 n.$$

Therefore,

$$ h\leq \log_2 n < h+1,\ \text{ and }\ h\in\mathbb{Z},\ \implies \left\lfloor \log_2 n \right\rfloor = h.$$