At least one even number among $\{ \lfloor 2^{n}\sqrt{2} \rfloor, \lfloor 2^{n+1}\sqrt{2} \rfloor,..., \lfloor 2^{2n}\sqrt{2} \rfloor \}$

Question

For any positive integer $n$, prove that the set

$$\{ \lfloor 2^{n}\sqrt{2} \rfloor, \lfloor 2^{n+1}\sqrt{2} \rfloor,..., \lfloor 2^{2n}\sqrt{2} \rfloor \}$$

contains at least one even number.

I tried to prove this question by contradiction, assuming that each element is odd. There exist the positive integers $k_1, k_2, ..., k_{n+1}$ such that

$$2k_1-1<2^n\sqrt{2}<2k_1$$

$$2k_2-1<2^{n+1}\sqrt{2}<2k_2$$

$$...$$

$$2k_{n+1}-1<2^{2n}\sqrt{2}<2k_{n+1}$$

But i can't find a contradiction among these inequalities.

Answer 1

If $\lfloor x\rfloor$ and $\lfloor {2x}\rfloor$ are both odd, then $\lfloor {2x}\rfloor=2\lfloor x\rfloor+1$. Use this fact to prove that if all the floor functions are odd, then $\lfloor{2^n\sqrt2}\rfloor$ is one less than a multiple of $2^{n+1}$.

Then show that for $n\ge 1$, in fact $2^{n+1}>1+2^n\sqrt2$. Thereby the assumption that all the floor functions are odd will meet the same fate as most of my college basketball tournament brackets.

For further review: If we allow $n=0$ then we do have all the floor functions (one value) odd. Where does the above proof break down if we allow $n=0$?

Answer 2

Let me continue TonyK's comment. If $\sqrt{2}=1.b_1b_2\ldots b_{n-1}11\ldots11b_{2n+1}\ldots$, then $$ \sqrt{2}=\frac{k}{2^{n-1}}+\left(\frac{1}{2^n}+\ldots+\frac{1}{2^{2n}}\right)+r, $$ where $k=(\overline{1b_1b_2\ldots b_{n-1}})_2$ is a positive integer and $r\in(0,\frac{1}{2^{2n}})$ (since $\sqrt{2}$ is not rational number of the form $p/2^{q}$). Hence, $$ 2^{n+1}(k+1)-1<2^{2n}\sqrt{2}<2^{n+1}(k+1). $$ Denote $m=2^{n+1}(k+1)$, then the last inequality can be rewritten as follows $$ (m-1)^2<2^{4n+1}<m^2. $$ However, $m^2$ and $2^{4n+1}$ are divisible by $2^{2n+2}$, so $$ (m-1)^2\leq 2^{4n+1}\leq m^2-2^{2n+2}. $$ Thus, $2m-1\geq 2^{2n+2}$, so $m>2^{2n+1}$. Recall that $m=2^{n+1}(k+1)$, so the last inequality means that $k\geq 2^{n}$. But it's impossible because $k=(\overline{1b_1b_2\ldots b_{n-1}})_2<2^n$.

Answer 3

For the sake of contradiction assume that each element in the set is odd. Then, for some $m \geq 1$, we have:

$$2m-1 < 2^n\sqrt{2}<2m$$

and multiplying by $2$:

$$4m-2 < 2^{n+1}\sqrt{2}<4m$$

However, since $\lfloor 2^{n+1}\sqrt{2}\rfloor$ is odd, then

$$4m-1<2^{n+1}\sqrt{2}<4m$$

Repeating the process

$$2^{n+1}m-1<2^{2n}\sqrt{2}<2^{n+1}m\Rightarrow \frac{1}{2^{n+1}}>m-2^{n-1}\sqrt{2}=\frac{m^2-2^{2n-1}}{m+2^{n-1}\sqrt{2}}$$

Also, since $2m>2^n\sqrt{2}\Rightarrow m^2>2^{2n-1}\Rightarrow m^2\geq 2^{2n-1}-1$. Thus:

$$\frac{1}{2^{n+1}}>\frac{m^2-2^{2n-1}}{m+2^{n-1}\sqrt{2}}\geq \frac{1}{m+2^{n-1}\sqrt{2}}$$

Therefore:

$$2^{n+1}<m+2^{n-1}\sqrt{2}<\frac{2^{n}\sqrt{2}+1}{2}+2^{n-1}\sqrt{2}=2^n\sqrt{2}+\frac{1}{2}<2^n\sqrt{2}+\frac{2^n}{2}$$

and thus

$$2<\sqrt{2}+\frac{1}{2}$$

which is a contradiction.