I am interested in the distributedness or "mixing" behavior of certain linear recurrences modulo powers of $2$. In particular, consider the Pell sequence (https://oeis.org/A000129), modulo $2^k$ for a sufficiently large integer $k$, defined as \begin{align*} a_0 &\equiv 0,\\ a_1 &\equiv 1,\\ a_{n} &\equiv 2 a_{n-1} + a_{n-2} \pmod{2^k}. \end{align*} I want to know how well-distributed this sequence is in a coarse sense: the sequence should be $< 2^{k-1}$ half the time and $\ge 2^{k-1}$ half the time. In other words, the most significant bit of the sequence should be equally likely to be $0$ or $1$.
I can show that this is true on a long time scale, on the order of $2^k$:
- The period of the Pell sequence mod $2^k$ is exactly $2^k$, which can be shown using the sequence's binomial identity and arguing about the factors of each term.
- Then with the same techniques, we can show $a_{n} \equiv a_{2^{k-1}+n} + 2^{k-1}$.
Thus, the second half of a period of the sequence is equal to the first half but with the most significant bit toggled, and hence exactly half of the period is $<2^{k-1}$.
However, I want to show that this mixing happens on short time scales as well. We know that there is an explicit Binet formula for this sequence (e.g. on OEIS) which shows that the $n$th element of the sequence grows exponentially in $n$, and so we expect the first $\Theta(k)$ elements of the sequence to stay below $2^{k-1}$. However, from computer-generated examples I've observed that if we ignore the first $\Theta(k)$ elements to allow the sequence to "mix", then the cumulative fraction of subsequent large sequence elements always stays above an absolute constant (say, $0.1$), and rapidly converges to $1/2$. Is this true for all sufficiently large $k$? That is, is there some absolute constant $C$ such that for all $N > Ck$ the following holds? $$\frac{\#\{Ck< n\le N : a_n\in [0,2^{k-2}) \}}{N-Ck}< 0.9.$$ (Here, I would be happy with $2^{k-2}$ or any $\Omega(2^k)$ as the threshold for "large" instead of $2^{k-1}$; since $a_n$ grows like $2.414^n$, choosing a smaller cutoff eliminates the possibility that for some choices of $k$ the sequence wraps back around modulo $2^k$ before it becomes large.)
