Let $(a_n)$ be a sequence such that $a_0=0,a_1=1$ and $a_{n+2}=a_{n+1}+\frac{a_n}{2^n}$

Prove that the sequence is convergent and that the limit is irrational.

My attempt: Proving the first bit is quite easy.

Using induction we see that $a_n>0,\forall n>0$, hence the sequence is increasing. After some tricks we find an upper bound to be 2. So I proved convergence.

EDIT: Proving the upper bound is 2: $$ln(a_{n+2})<ln(a_{n+1})(1+\frac{1}{2^n})<ln(a_{n+1}+\frac{1}{2^n})<ln(a_n)+\frac{1}{2^{n-1}}+\frac{1}{2^n}<...<\sum_{k=0}^n\frac{1}{2^k}<2$$

EDIT_2: The upper bound appears to be $e$, result proved by @Jack D'Aurizio in the comment section

For the irrational bit. I found that $a_{n+2}=1+\sum_{k=1}^n\frac{a_k}{2^k}$

Letting $L=\lim\limits_{n \to \infty}a_n$ we have $L=1+ \sum_{n=1}^\infty\frac{a_n}{2^n}$

I haven't been able to go beyond this.

  • 2
    $\begingroup$ $a_6>2$, isn't it? $\endgroup$ – Pp.. Feb 7 '15 at 15:57
  • $\begingroup$ @Pp.. Yes I agree with this. $\endgroup$ – Rene Schipperus Feb 7 '15 at 15:58
  • $\begingroup$ I get a limit of about 2.17266875085, so something is awry. $\endgroup$ – Jon Feb 7 '15 at 16:24
  • $\begingroup$ If you found my proof of the upper bound wrong feel free to find an alternative upper bound and please prove the answer as well. Any ideas about the irrationality of the limit? $\endgroup$ – prometheus21 Feb 7 '15 at 16:28
  • 2
    $\begingroup$ The sequence is convergent since it is increasing and: $$ a_{n+2} \leq a_{n+1}\left(1+\frac{1}{2^n}\right) \leq \prod_{k=1}^{n}\left(1+\frac{1}{2^k}\right)\tag{1}$$ where the RHS is converging since $\sum_{k\geq 1}\frac{1}{2^k}$ is converging. In particular: $$ a_{n+2} \leq \exp\sum_{k=1}^{n}\frac{1}{2^k} \leq e.\tag{2} $$ $\endgroup$ – Jack D'Aurizio Feb 7 '15 at 16:33

Isn't the binary representation of the limit infinite and non periodic and hence it is irrational?

Represent $a_n$ as a binary number, and prove that $a_{n+1}$ has more binary digits than $a_n$. This shows infinite.

If period were $p$ (after the first $d$ digits), I guess we can consider large enough $N$, and $a_N$. This is incomplete and perhaps the more difficult part of this problem.


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.