For a fixed $\beta \in \{2, 2^2, 2^3, ...\}$, I define the random Pell sequence to be: \begin{equation} P_n = \begin{cases} 0 & \quad \text{if } n=0\\ 1 & \quad \text{if } n=1 \\ \pm\beta P_{n-1}+P_{n-2} &\quad \text{otherwise.} \end{cases} \end{equation} Then, if I write all possible sequences in the form of a tree, taking the positive value of $P_2$ as its root, it seems like, the sum of the absolute value of all values on the $i$-th row of my tree (starting at depth $i=0$) is $2^i\beta^{i+1}$ (note that $2^i$ is the number of leaves on this row). For example, if I take $\beta=2$, on depth $0$, I have the root $2$ and the two leaves on depth 1 are $5$ and $-3$ and we have that, $|2|=2^02^1$ and $|5|+|-3|=8=2^12^2$. Induction doesn't seem to help, has anybody ever seen something like this (sees why it could be the case)? (This would also mean that the expected value of the absolute value of the $i$-th term of the sequence is $\beta^{i+1}$).
Thanks
I think that I have it, but it would be really nice if somebody could tell me if it looks right.
I think that at each leaf, if you take the absolute value of the leaf, what you do to its children is just reversing them (the one on the right comes on the left and the one the left on the right). So in what follows, we can assume that $P_i$ and $P_{i-1}$ are positive.
First I proved with induction that for $P_{i-1}$ parent of $P_i$, $|P_i| \geq |P_{i-1}|$. This implies that the absolute value of the children of $P_i=|P_i|$ are $|P_{i+1}|=\beta|P_i|+|P_{i-1}|$ and $|P_{i+1}|=\beta|P_i|-|P_{i-1}|$ (recall that $\beta \geq 2$).
With this fact and again with induction, I proved that the sum of the absolute value of all entries on the $i$-th row is $2^i\beta^{i+1}$ (since the sum of the absolute value of two children of a $P_i$ always gives you $2\beta|P_i|$, at the end you always have $2\beta$ times the sum of the absolute value of the last row).
In particular, we have that $\mathbf{E}(|P_n|)^\frac{1}{n}$ goes to $\beta$ as $n$ goes to $\infty$. This means that the sequence grows faster when $\beta$ is bigger.
My next step would be to see if allowing $\beta$ to be $2$ or $4$ in the sequence gives an expected value between the one when $\beta=2$ and the one when $\beta=4$ ..