Solving randomized recurrence relation

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.

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.