I have a question about a proof I found for the following claim in the context of the union by rank algorithm with respect to the disjoint-set data structure:
Claim: Prove that every node has rank at most $\lfloor \lg(n)\rfloor$
Proof: We’ll prove the claim by strong induction on the number of nodes. If $n = 1$, then that node has rank equal to $0 = \lfloor \lg(1) \rfloor$. Now suppose that the claim holds for $1, 2, . . . , n$ nodes. Given $n + 1$ nodes, suppose we perform a UNION operation on two disjoint sets with $a$ and $b$ nodes respectively, where $a,b \leq n$. Then the root of the first set has rank at most $\lfloor \lg(a)\rfloor$ and the root of the second set has rank at most $\lfloor \lg(b)\rfloor$. If the ranks are unequal, then the UNION operation preserves rank and we are done, so suppose the ranks are equal. Then the rank of the union increases by 1, and the resulting set has rank $\lfloor \lg(a)\rfloor + 1 \leq \lfloor \frac{\lg(n + 1)}{2} \rfloor + 1 = \lfloor \lg(n+1) \rfloor$.
How does the last set of inequalities follow? More specifically, why is it true that $\lfloor \lg(a)\rfloor + 1 \leq \lfloor \frac{\lg(n + 1)}{2} \rfloor + 1$ and is it true that $\lfloor \frac{\lg(n + 1)}{2} \rfloor + 1 = \lfloor \lg(n + 1) \rfloor$?
Edit:
Here's a link to the proof (problem 21.4-2): https://walkccc.me/CLRS/Chap21/21.4/
Information about union by rank: https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union_by_rank
The source skips over some commonly used techniques for these kinds of arguments. For example, they implicitly use that $n+1=a+b$ with WLOG $a\leq b$ in their inequalities. Also, they incorrectly write $\lg(n+1)/2$ (as written, not as a fraction) to mean $\lg((n+1)/2)$
With that in place it’s clear that $a\leq (a+b)/2=(n+1)/2$ and so $\lg(a) +1 \leq \lg((n+1)/2)+1=\lg(n+1)$