7
$\begingroup$

$\sqrt3=1.b_1b_2...$is the binary representation of $\sqrt3$.

i.e. $\sqrt3=1+\dfrac{b_1}{2^1}+\dfrac{b_2}{2^2}+...$

Prove that at least one of the digits $b_n,b_{n+1},...,b_{2n}$ is 1.

my attempt:

Square both sides: $$\left(1+\sum_{i=1}^\infty\frac{b_i}{2^i}\right)^2=3$$ Expand and subtract $1$ from both sides $$2\sum_{i=1}^\infty\frac{b_i}{2^i}+\sum_{i=1}^\infty\frac{b_i^2}{2^{2i}}=2$$ divide both side by 2 $$\sum_{i=1}^\infty\frac{b_i}{2^i}+\sum_{i=1}^\infty\frac{b_i^2}{2^{2i+1}}=1$$ Tidy up $$\sum_{i=1}^\infty\frac{1}{2^i}\left(b_i+\frac{b_i^2}{2^{i+1}}\right)=1$$ Lemma: $\displaystyle\sum_{i=m}^\infty\frac{1}{2^i}\left(1+\frac{1}{2^{i+1}}\right)<\frac{1}{2^{m-2}}$

Proof: multiply both side by $2^{m-1}$$$\sum_{i=1}^\infty\frac{1}{2^i}+\frac{1}{2^{m+1+i}}<2$$which is trivial for any positive integer m.

Proceed the proof by contradiction: suppose $b_n,b_{n+1},...b_{2n}$ are all equal to $0$. Then the sum $\sum_{i=1}^{n-1}\frac{1}{2^i}\left(b_i+\frac{b_i^2}{2^{i+1}}\right)$ is in the form of $1-\frac{x}{2^{2n-1}}$.

But $$\sum_{i=2n+1}^\infty\frac{1}{2^i}\left(b_i+\frac{b_i^2}{2^{i+1}}\right)<\frac{1}{2^{2n-1}}$$by lemma.

Q.E.D.

Is this proof correct? I am also happy for an alternative (and hopefully shorter) solution.

$\endgroup$
  • $\begingroup$ How do you go from $\left(1+\sum\limits_{j=1}^\infty 2^{-j}b_j\right)^2=3$ to $2\sum\limits_{j=1}^\infty 2^{-j}b_j+\sum\limits_{j=1}^\infty 2^{-2j}b_j^2=2$? Because I did the same thing and I have ended up with $$2\sum_{j=1}^\infty 2^{-j}b_j+\left(\sum_{j=1}^\infty 2^{-j}b_j\right)^2=2.$$ $\endgroup$ – Saucy O'Path Sep 9 '18 at 8:35
  • 2
    $\begingroup$ Note that $$\Big(1+\sum_{i=1}^\infty \frac{b_i}{2^i}\Big)^2 = 1+2\sum_{i=1}^\infty\frac{b_i}{2^i}+\color{red}{2\sum_{i,j=1}^\infty\frac{b_i b_j}{2^{i+j}}}+\sum_{i=1}^\infty \frac{b_i^2}{2^{2i}},$$ where the red term is missing in your computations. $\endgroup$ – M. Winter Sep 9 '18 at 8:39
  • $\begingroup$ Ooops... looks like I made a mistake. $\endgroup$ – abc... Sep 9 '18 at 8:47
  • $\begingroup$ @M. Winter, thanks for pointing out my mistake. If I cannot see properly OP on the screen of my smartphone, I should not edit answers :) $\endgroup$ – user376343 Sep 9 '18 at 8:52
  • $\begingroup$ (To the OP) Note that it is best to avoid use of MathJax in titles as that prevents the questions from appearing in the Hot Network and reduces their searchability on platforms like Google. See my edit. $\endgroup$ – The Long Night Sep 9 '18 at 9:16
4
$\begingroup$

The flaw in your proof was pointed out in the comments, so let me show you my approach


Assume $\sqrt 3$ has all digits $b_i=0$ for $i\in\{n,...,2n\}$ (these are $n+1$ digits). Write

$$\sqrt 3\cdot 2^{n-1}=N + \epsilon= b_1\cdots b_{n-1}.\underbrace{0\cdots0}_{n+1}b_{2n+1}\cdots$$

where $N=b_1\cdots b_{n-1}\in\Bbb N$ is the integer part, and $\epsilon=0.b_{n}b_{n+1}\cdots\in(0,1)$ is the fractional part (which is stricly positive because of the irrationality of $\sqrt{3}$). We have $N< 1.8\cdot 2^{n-1}$ (with $1.8$ being a rough upper bound for $\sqrt 3$). Further, $\epsilon$ must have zeros as the first $n+1$ digits $b_n,...,b_{2n}$. So the largest possible value is

$$\epsilon \le 0.\underbrace{0\dots0}_{n+1}\overline 1=0.\underbrace{0\cdots 0}_n1=\frac1{2^{n+1}}$$

Now observe that

$$\underbrace{3\cdot 2^{2n-2}}_{\text{integer}}=(\sqrt 3\cdot2^{n-1})^2=N^2+2N\epsilon+\epsilon^2.$$

The left side is an integer, and so is $N^2$. Note that $0<2N\epsilon< 0.9$. And finally, since $\epsilon^2<1/2^{2n+2}<0.1$, we cannot close the gap to make the right side a whole integer too.

$\endgroup$
  • $\begingroup$ For completeness, you should also show (or at least mention) that $\epsilon$ can't be zero. $\endgroup$ – TonyK Sep 9 '18 at 9:23
  • $\begingroup$ @TonyK Thanks, I included it! $\endgroup$ – M. Winter Sep 9 '18 at 9:26
  • $\begingroup$ Nice solution! Thank you very much @M.Winter $\endgroup$ – abc... Sep 9 '18 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.