# Sequence, Irrational limit

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.

• $a_6>2$, isn't it? – Pp.. Feb 7 '15 at 15:57
• @Pp.. Yes I agree with this. – Rene Schipperus Feb 7 '15 at 15:58
• I get a limit of about 2.17266875085, so something is awry. – Jon Feb 7 '15 at 16:24
• 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? – prometheus21 Feb 7 '15 at 16:28
• 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}$$ – Jack D'Aurizio Feb 7 '15 at 16:33

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.