Solving randomized recurrence relation I'm looking at the random sequence $x_n$ with $x_0=x_1=1$ and 
\begin{equation}
x_{n+1}=2x_n\pm x_{n-1}
\end{equation}
where we choose the $\pm$ sign independently with equal probability. Now considering the recurrence relations $x_{n+1}=2x_n+x_{n-1}$ and $x_{n+1}=2x_n-x_{n-1}$ separately, it is clear that $x_n\rightarrow\infty$ as $n\rightarrow\infty$. However, the sequence $x_n^{1/n}$ seems to tend to a limit near 1.91 (got this from numerical computation and some brute force by a Monte Carlo simulating the $\pm$ sign). Thus the sequence $x_n^{1/n}$ seems to convenge almost surely. I was wondering if anyone could show that the sequence was indeed almost surely converging and/or work out the limit. 
Thanks in advance. 
Update:
This comment shows that $\lim_{n\rightarrow\infty} |x_n|^{1/n}$ converges almost surely. Let $y_n=\frac{x_n}{2^n}$ then $2^{n+1}y_{n+1}=2^{n+1}y_n\pm 2^{n-1}y_{n-1}$. Hence
$y_{n+1}=y_n\pm \frac{1}{4}y_{n-1}$
Embree-Trefethen showed that $\lim_{n\rightarrow\infty} |y_n|^{1/n}$ converges almost surely. See Embree, M.; Trefethen, L. N. (1999), "Growth and decay of random Fibonacci sequences".
However, finding the almost sure limit accurately or analytically is proving difficult at the moment. 
 A: If you replace 2 with 1 in your recurrence, you get the random Fibonacci sequence. Viswanath has proven that the random Fibonacci sequence almost surely has exponential growth (and gives the growth constant).  I haven't carefully read the proof, though, so I can't comment on how it could be adapted to the case you're interested in.
Kesten and Furstenberg showed quite a while ago that the limit you say is around 1.91 at least exists, by restating the problem as one about multiplication of random matrices.
A: To start with: the sequence can be written as 
\begin{equation}
    x_{n+1} = 2 x_{n} + e_{n+1} x_{n-1}   \; [1]
\end{equation}
where $e_n$ is a sequence of iid Bernoully variables taking the values $(1,-1)$ with equal probabilities. 
Now, taking expectations, and because $e_{n+1}$ and $x_{n-1}$ are independent, it results that $E(x_n) = 2^{n-1}$
Hence, I'd say that, if the sequence $x_n^{1/n}$ converges, it should converge to 2. 
== continued ==
Let's see if we can compute the variance.
Multiplying by $x_{n+1}$ and taking expectations:
\begin{equation}
  E(x^2_{n+1})=2E(x_n x_{n+1}) + E(e_{n+1} x_{n+1} x_{n-1})  \; [2]
\end{equation}
To compute the first term we multiply [1]  by  $x_{n}$
\begin{equation}
  E(x_n x_{n+1})= 2 E(x_n^2) + E(e_{n+1} x_{n} x_{n-1}) = 2 E(x_n^2)  \; [3]
\end{equation}
To compute the second term we multiply [1] by  $e_{n+1} x_{m-1}$ and recall that $e_{n+1}^2 =1$
\begin{equation}
   E(e_{n+1} x_{n+1} x_{n-1}) =  2 E(e_{n+1} x_{n-1} x_{n}) + E(e_{n+1}^2) = E(e_{n+1}^2)  \; [4]
\end{equation}
Hence
\begin{equation}
   E(x_{n+1}^2) = 4 E(x^2_n) + E(x^2_{n-1}) \; [5]
\end{equation}
====
Updated: this doesnt lead where I expected to ... I thought that the linearly-normalized sequence (say, $x_n / 2^n$ ) would have an asymtotically vanishing variance, but this does not appear to be so.
