Corrección de la prueba de la división en el techo de la función

Question

Mi profesor me ha pedido que presente un comprobante de mis compañeros que mañana

$$\left\lceil\frac{n}{2^k}\right\rceil = \left\lceil\frac{\left\lceil\frac{n}{2^{k-1}}\right\rceil}{2}\right\rceil$$

Traté de demostrar de la siguiente manera, pero no estoy seguro de si mi prueba es correcta.

Prueba

La anterior es equivalente a $$\left\lceil\frac{n}{2^{k+1}}\right\rceil = \left\lceil\frac{\left\lceil\frac{n}{2^k}\right\rceil}{2}\right\rceil$$

Digamos que $x = \left\lceil\frac{n}{2^{k+1}}\right\rceil$ para la facilidad de la notación.

Es entonces claro que $$x-1 \lt \frac{n}{2^{k+1}} \le x$$

Ahora vamos a demostrar que lo que se pide el uso de la contradicción. Suponga que $$\left\lceil\frac{n}{2^{k+1}}\right\rceil \lt \left\lceil\frac{\left\lceil\frac{n}{2^k}\right\rceil}{2}\right\rceil$$ Entonces existe un número entero $a$ tal que $$\left\lceil\frac{n}{2^{k+1}}\right\rceil \le a \lt \left\lceil\frac{\left\lceil\frac{n}{2^k}\right\rceil}{2}\right\rceil$$

Esto es equivalente a $$\left\lceil\frac{n}{2^k}\right\rceil \le 2*a \lt \frac{n}{2^k}$$, que, obviamente, puede no ser cierto.

QED

¿Ves algún error en mi prueba? Es claro? Estoy un poco dudoso sobre el último paso, donde me multiplicar $a$ 2.

Answer 1

Su razonamiento es un poco inestable en algunos lugares. Déjame ver si te puedo ayudar un poco con el rigor.

Para simplificar, vamos a decir $x=\left\lceil\frac{n}{2^{k+1}}\right\rceil$$y=\left\lceil\frac{n}{2^k}\right\rceil,$, por lo que debemos probar que $x=\left\lceil\frac{y}2\right\rceil$. Desde $\frac{n}{2^k}\le y,$$\frac{n}{2^{k+1}}\le\frac{y}2,$$x\le\left\lceil\frac{y}2\right\rceil$. Ahora podemos asumir que $x\ne\left\lceil\frac{y}2\right\rceil,$, del que se desprende que el$x<\left\lceil\frac{y}2\right\rceil.$, a Continuación, en realidad, no es un número entero $a$ tal que $x\le a<\left\lceil\frac{y}2\right\rceil.$, De hecho, $x$ es un número entero! Más relevante, sin embargo, es el hecho de que $$\frac{n}{2^{k+1}}\le x<\left\lceil\frac{y}2\right\rceil.$$ Since $x$ is an integer less than $\left\lceil\frac{y}2\right\rceil$, then we have $x<\frac{y}2,$ and so $$2x<y.\tag{$\spadesuit$}$$ On the other hand, $$\frac{n}{2^{k+1}}\le x,$$ so $$\frac{n}{2^k}\le 2x,$$ and since $2x$ is an integer, then $$y=\left\lceil\frac{n}{2^k}\right\rceil\le 2x.\tag{$\clubsuit$}$$ By $(\spadesuit)$ and $(\clubsuit),$ tenemos nuestra contradicción.