Showing limit of a sequence $0, \frac12, \frac14, \frac38, \frac5{16}, \frac{11}{32}, \frac{21}{64},...$ How do you show the convergence of the following 2 sequences?
$0, \dfrac12, \dfrac14, \dfrac38, \dfrac5{16}, \dfrac{11}{32}, \dfrac{21}{64},...$
and 
$1, \dfrac12, \dfrac34, \dfrac58, \dfrac{11}{16}, \dfrac{21}{32}, \dfrac{43}{64},...$
I know that for the first sequence $s_n=\dfrac{a_n}{2^n}$ converges to $\dfrac13$ and the second sequence $r_n=\dfrac{a_{n+1}}{2^n}$ converges to $\dfrac23$, 
where
$a_n=a_{n-1}+2a_{n-2}, a_0=0, a_1=1$
but how would we show this working out?
 A: Revised Answer. The $n$-th term of the first sequence is $\frac{a_n}{2^n}$, where the numerators satisfy the recurrence $a_{n+1}=2a_n+(-1)^n$ with $a_0=0$. We want a closed form for $a_n$. One way to approach the problem is to try to ‘unwind’ the recurrence. Imagine starting with some moderately large $n$:
$$\begin{align*}
a_n&=2a_{n-1}+(-1)^{n-1}\\
&=2\left(2a_{n-2}+(-1)^{n-2}\right)+(-1)^{n-1}\\
&=2^2a_{n-2}+2(-1)^{n-2}+(-1)^{n-1}\\
&=2^2\left(2a_{n-3}+(-1)^{n-3}\right)+2(-1)^{n-2}+(-1)^{n-1}\\
&=2^3a_{n-3}+2^2(-1)^{n-3}+2(-1)^{n-2}+(-1)^{n-1}\\
&\;\vdots\\
&=2^ka_{n-k}+2^{k-1}(-1)^{n-k}+2^{k-2}(-1)^{n-k+1}+\ldots+2(-1)^{n-2}+(-1)^{n-1}\\
&\;\vdots\\
&=2^na_0+\sum_{k=0}^n2^k(-1)^{n-1-k}\\
&=\sum_{k=0}^n2^k(-1)^{n-1-k}\\
&=(-1)^{n-1}\sum_{k=0}^{n-1}\left(\frac2{-1}\right)^k\\
&=(-1)^{n-1}\sum_{k=0}^{n-1}(-2)^k\\
&=(-1)^{n-1}\cdot\frac{(-2)^n-1}{-2-1}\\
&=\frac{(-1)^n\left((-2)^n-1\right)}3\\
&=\frac{2^n-(-1)^n}3\;.
\end{align*}$$
Of course we guessed the pattern to fill in after the first $\vdots$, so we really ought to prove by induction on $n$ that $a_n$ really is $\frac13\left(2^n-(-1)^n\right)$. Once that’s done, however, you know that the $n$-th term of your sequence is
$$\frac{\frac13\left(2^n-(-1)^n\right)}{2^n}\;,$$
and the limit is then obvious.
(There are other ways to solve the recurrence, but this one is probably the most elementary.)
A: Hint: For the first, subtract $\dfrac{1}{3}$ from each term and simplify.
A: From the given recurrence, derive
$$s_n=\frac{a_n}{2^n}=\frac{a_{n-1}+2a_{n-2}}{2^n}=\frac{a_{n-1}}{2\cdot2^{n-1}}+\frac{2a_{n-2}}{4\cdot2^{n-2}}=\frac{s_{n-1}+s_{n-2}}2.$$
From there,
$$s_n-s_{n-1}=-\frac12(s_{n-1}-s_{n-2}).$$
This shows that the first order difference follows a converging geometric progression (common ratio $-\frac12$), so that the corresponding series converges too.
A: The characteristic equation of the linear recurrence is
$$a^2=a+2,$$ which has roots $\color{blue}2$ and $\color{blue}{-1}$.
Hence the general solution is
$$a_n=c\ \color{blue}2^n+c'(\color{blue}{-1})^n,$$
so that $$s_n=\frac{a_n}{2^n}=c+c'(-\frac12)^n$$
converges to $c$, and $a_0+a_1=3c$.
