Demostrar que $ \left \lfloor {\log n} \right \rfloor = \left \lfloor {\log \left \lceil \frac {n-1}{2}\right \rceil} \right \rfloor + 1$

Question

Hemos estado haciendo análisis de algoritmos en la universidad, y después de analizar el algoritmo de búsqueda binaria, resultó la siguiente ecuación. Lo que tenemos que hacer ahora es demostrar que $ \left \lfloor {\log n} \right \rfloor = \left \lfloor {\log \left \lceil \frac {n-1}{2}\right \rceil} \right \rfloor + 1$

Esto me ha estado causando algún dolor de cabeza hoy y desesperadamente decidí ponerlo en este foro con la esperanza de alguna pista que mi vista de túnel ahora puede haber pasado por alto.

Al principio, intenté obtener una prueba sólo mediante transformaciones matemáticas. Eso no fue muy bien, aunque conseguí esto $ \left \lfloor {\log n} \right \rfloor = \left \lfloor {\log (\left \lceil \frac {n}{2}\right \rceil*2-2)} \right \rfloor$ que intenté demostrar por separado para n par y no par, pero me quedé atascado.

Mi siguiente planteamiento fue considerar para n no par -> n-1 es par. Y entonces

$2^k$ $\leq$ n-1 < n < $2^{k+1}$ $\Rightarrow$ $ k \leq log (n-1) < log n < k+1 $

Aunque he progresado mejor de esta manera, no consigo relacionarme con la función techo dentro del logaritmo.

¿Puede alguien darme una pista al respecto? Gracias de antemano.

Answer 1

Su afirmación original no es cierta (por favor, lea toda la respuesta). Pero la siguiente afirmación es correcta:

$$\left \lfloor {\log_2 n} \right \rfloor = \left \lfloor {\log_2 \left \lceil \frac {n-1}{2}\right \rceil} \right \rfloor + 1\tag{1}$$

Prueba:

Cada número $n$ puede situarse entre dos potencias consecutivas de 2. En otras palabras, existe $k$ tal que:

$$2^k\le n\le2^{k+1}-1\tag{1}$$

Obviamente:

$$k\le\log_2n<k+1$$

$$k=\lfloor\log_2n\rfloor\tag{2}$$

Al otro lado de (1):

$$\frac{2^k-1}2 \le \frac{n-1}{2} \le \frac{2^{k+1}-2}2$$

$$2^{k-1}-\frac12 \le \frac{n-1}{2} \le 2^k-1$$

$$\lceil 2^{k-1}-\frac12\rceil \le \lceil\frac{n-1}{2}\rceil \le 2^k-1$$

$$2^{k-1} \le \lceil\frac{n-1}{2}\rceil \le 2^k-1$$

$${k-1} \le \log_2\lceil\frac{n-1}{2}\rceil \le \log_2 (2^k-1)<k$$

$${k-1} =\lfloor \log_2\lceil\frac{n-1}{2}\rceil \rfloor$$

$$k=\lfloor \log_2\lceil\frac{n-1}{2}\rceil \rfloor+1\tag{3}$$

Comparando (2) y (3) se obtiene:

$$\lfloor\log_2n\rfloor = \lfloor \log_2\lceil\frac{n-1}{2}\rceil \rfloor+1$$

...lo que completa la prueba.

Puedes demostrar fácilmente que la afirmación original no es cierta. Básicamente estás diciendo que la función:

$$f(n)=\left \lfloor {\log n} \right \rfloor - \left \lfloor {\log \left \lceil \frac {n-1}{2}\right \rceil} \right \rfloor - 1$$

...es igual a cero para todos los valores de $n$ .

Esto no es cierto si " $\log$ "significa logartihm en base 10:

Esto tampoco es cierto si " $\log$ " stans para logaritmo natural " $\ln$ ":

Si no te fías de estos gráficos, calcula el valor de $n=45$ y en ambos casos el resultado es -1, no 0.