2.45

Let [math]n\ge1[/math] and put [math]k=\lfloor\lg n\rfloor[/math]. By the definition of the floor function [math]2^{k}\le n<2^{k+1}\tag{1}[/math]. Adding 1 gives [math]2^{k}+1\;\le\;n+1\;\le\;2^{k+1}\tag{2}[/math]. Because the binary logarithm [math]\lg[/math] is strictly increasing, taking [math]\lg[/math] of (2) yields [math]\lg\bigl(2^{k}+1\bigr)\;\le\;\lg(n+1)\;\le\;k+1.[/math] Since [math]2^{k}+1>2^{k}[/math], we also have [math]\lg\bigl(2^{k}+1\bigr)>k[/math]. Hence [math]k\; <\; \lg(n+1)\; \le\; k+1.[/math] The only integer lying in this half-open interval is [math]k+1[/math]; therefore [math]\lceil\lg(n+1)\rceil = k+1 = \lfloor\lg n\rfloor + 1.[/math] Thus [math]\lceil\lg(n+1)\rceil = \lfloor\lg n\rfloor + 1[/math] for every integer [math]n\ge1[/math].

Back to Chapter 2