For every $n \in \mathbb N$, let's define $a_0 = 0$, $$\begin{cases} a_{i+1} = 2a_i + 1 \pmod {2^n}, &\text{if it never appeared before} \\ a_{i+1} = 2a_i \pmod {2^n},& \text{otherwise}\end{cases}$$
if both $2a_i + 1 \pmod {2^n}$ and $2a_i \pmod {2^n}$ are already in the sequence, the algorithm stops
for example with $n=3$, we have $$0, 1, 3, 7, 6, 5, 2, 4$$ for $n=4$, we have $$0, 1, 3, 7, 15, 14, 13, 11, 6, 12, 9, 2, 5, 10, 4, 8$$
The goal is to show that, for every $n$, every number between $0$ and $2^n - 1$ will be generated.
(Of course every number generated will be distinct, but you have to show that the algorithm does not stop before)
I have a somewhat lengthy proof of this, but I would like to see other (more elegant) proofs.
Thank you for your time!
EDIT
I came up with the sequence trying to solve the following problem:
Show that for every $n$, there exist a string $A$ long $2^n + n - 1$ digits so that every binary sequence of $n$ digits can be extracted as subsequence of consecutives digits of $A$.
For example, with $n=3$, $A = 0001110100$ is long $2^3 + 3 - 1$ and we can find $000, 001, 010, 100, 101, 111, \text{etc}$ as subsequences of $A$.
One can see that the fact that the algorithm does not stop is equivalent to the existence of $A$
Such a string is guaranteed to exist by the De Bruijn sequence (setting $k=2$). The proof is rather elegant: construct a graph whose nodes are all the integer from $0$ to $2^{n-1} - 1$, add edges from $i$ to $j$ iff $i \mod 2^{n-2} = \lfloor j/4 \rfloor$ (that is, the last $(n-2)$ digits of the binary representation of $i$ is the same with the first $(n-2)$ digits of the binary representation fo $j$), and a Eulerian path in this graph constitutes to such a sequence. The existence of a Eulerian path in this graph is guaranteed by the properties of the graph -- if $n > 2$, then the graph is both connected and all nodes have even degree.