Show that the sequence $\{a_{n}\}_{n \ge 1}$ defined by $a_{n}=\lfloor n\sqrt{2}\rfloor$ contains an infinite number of integer powers of $2$.
Problem
Source:
Tags: floor function, More Sequences
19.10.2007 22:22
Suppose the sequence contains finitely many powers of $ 2$. Let $ 2^t$ the greatest power met in the sequence. Take $ n>t$. Then for some $ m$, $ m\sqrt2<2^n<2^n+1<(m+1)\sqrt2$, implying $ 2^n>m\sqrt2\ge2^n-(\sqrt2-1)>2^n-\dfrac12$. Let $ m\sqrt2=2^n-\epsilon$. Then $ \epsilon<\dfrac12$. Let $ k$ be a positive integer such that $ 2^k\epsilon<1<2^{k+1}\epsilon$. Clearly $ k\ge1$ and $ \dfrac12<2^k\epsilon$. This means $ 2^{n+k}>2^km\sqrt2=2^{n+k}-2^k\epsilon>2^{n+k}-1$. We must also have $ 2^km\sqrt2=2^{n+k}-2^k\epsilon>2^{n+k}-(\sqrt2-1)>2^{n+k}-\dfrac12$, which is $ 2^k\epsilon<\dfrac12$, contradiction.
28.03.2008 05:29
freemind wrote: . We must also have $ 2^km\sqrt2 = 2^{n + k} - 2^k\epsilon > 2^{n + k} - (\sqrt2 - 1) > 2^{n + k} - \dfrac12$, which is $ 2^k\epsilon < \dfrac12$, contradiction. Why is it true? Can you explain please?
28.05.2008 08:34
Another solution: Let us represent $ \sqrt{2}$ in binary expression,$ \sqrt{2}=a_{0}.a_{1}a_{2}\dots$,since $ \sqrt{2}$ is irrational,we know that there are infinitely many $ k$,such that $ a_{k}=1$.So $ 2^{k-1}\sqrt{2}=a_{0}a_{1}\dots a_{k-1}.a_{k}\dots$. Let $ m=[2^{k-1}\sqrt{2}]$,where $ [n]$-means integer part of $ n$.Since $ a_{k}=1$,it follows $ 2^{k-1}\sqrt{2}-1<m<2^{k-1}\sqrt{2}-\frac{1}{2}$,hence $ 2^{k}<(m+1)\sqrt{2}<2^{k}+\frac{1}{\sqrt{2}}$,and thus $ \boxed{[(m+1)\sqrt{2}]=2^{k}}$,so we are done.