We claim there are $2^n$ such sequences. Define the $k$-interval as $\{a_k, a_{k+1}, \dots, 2k\}$. Then the condition requires that $k, \left\lfloor \frac{k}{2} \right\rfloor, \dots$ are in the $k$-interval. Call these the lamps for $k$. Claim: We induct on the following claims: Each $k$-interval consists of all integers $\{0, 1, \dots, k\}$. $\{a_{2k-1}, a_{2k}\} = \{a_{k-1}, k\}$ $a_{k-1}$ is a lamp for $k$. Proof. We prove this inductively. The base case of $k = 0, 1$ works. Now, we show that $a_{k-1}$ is a lamp for $a_k$. Suppose that $k$ is even. Then we get that $\{a_{k-1}, a_{k}\} = \{a_{\frac{k}{2}-1}, \frac{k}{2}\}$, and note that $a_{\frac{k}{2}-1}$ is a lamp for $\frac{k}{2}$ which is a lamp for $\frac{k}{2}$ which implies the result. Likewise, if $k$ is odd, we consider $\{a_{k-1}, a_{k-2}\} = \{\frac{k-1}{2}, a_{\frac{k-1}{2}-1}\}$ which are both lamps for $k$. As such, since the $a_{k-1}, \dots, a_{2k-2}$ contains $a_k$ exactly once, we get that $a_k, \dots, a_{2k-2}$ doesn't contain $a_k$. It also can't contain $k$. Since $a_k$ and $k$ are lamps for $k$, $a_k, \dots, a_{2k}$ must contain them, which implies that $a_{2k-1, a_{2k}} = \{a_{k-1}, k\}$. Then we get that $\{a_k, \dots, a_{2k}\} = \{a_{k-1}, \dots, a_{2k-2}, k\} = \{0, \dots, k\}$ for the third claim. $\blacksquare$ Notably, we also have that if $\{a_{2k-1}, a_{2k}\} = \{a_{k-1}, k\}$ and $a_0, \dots, a_{2k-2}$ is a valid sequence, then $a_0, \dots, a_{2k}$ is a valid sequence. This constraint gives us $2^n$ total options for building up $a_0, \dots, a_{2k}$ by first choosing $\{a_1, a_2\}$ and so forth.

See https://artofproblemsolving.com/community/c6h44479p281572 for something similar. I feel like this problem is like a more accessible version of the 2005 IMO problem.

Answer: $2^n$. The key claim is the following: Claim: $a_k, \dots, a_{2k}$ is a permutation of $(0,1, \dots, k)$ for all $k\leq n$. Proof. We strong induct on $n$. The base cases of $k=1$ and $k=2$ can be checked. Now, we know that $a_{k-1}, \dots, a_{2k-2}$ is a permutation of $(0,\dots, k-1)$. Thus $a_k, \dots, a_{2k-2}$ are not $k=\lfloor k/2^0\rfloor$, so $a_{2k-1}$ or $a_{2k}$ is $k$. It suffices to show that $a_{k-1}$ appears in $a_k, \dots, a_{2k}$ or $a_{k-1}=a_{2k-1},a_{2k}$. By our inductive hypothesis and the reasoning above, $\{a_{2l-1}, a_{2l}\} = \{a_{l-1},l\}$ for $l<k$. Let $j=\lfloor k/2\rfloor$. Thus $\{a_{2j-1},a_{2j}\}=\{a_{j-1},j\}$. Also, $k-1=2j-1$ or $2j$ by the floor definition of $k$. Thus $a_{k-1}=a_{j-1}$ or $k$. If $a_{k-1}=j$, then since $\lfloor k/2\rfloor = a_j$ must appear in $a_k, \dots, a_{2k}$ we conclude. Else, $a_{k-1}=a_{j-1}$. We can repeat the same argument to find $a_{j-1}=\lfloor j/2\rfloor$ or $a_{\lfloor j/2\rfloor -1}$. Repeat this inductively to get $a_{k-1}=\lfloor k/2^m\rfloor$ for some $m$. Thus $a_{k-1}$ is in $a_k, \dots, a_{2k}$ and the claim is proven. $\blacksquare$ To finish, repeatedly applying the claim gives $a_0=0$ and $i \in \{a_{2i-1}, a_{2i}\}$. Now, I claim the answer is $2^n$. This is from choosing which of $a_{2i-1}, a_{2i}$ is $i$. It suffices to show each choice gives a unique sequence. This is true by applying the claim on $1$ through $n$ to get the other number in each pair.

Solution from Twitch Solves ISL: The answer is $2^n$. We note $a_0=0$ and ignore it going forward, focusing only on $a_i$ for $i \ge 1$. In what follows, for each positive integer $t$ we let \[ D(t) \coloneqq \left\{ t, \left\lfloor t/2 \right\rfloor, \left\lfloor t/4 \right\rfloor, \dots \right\}. \]For example, $D(13) = \{13, 6, 3, 1, 0\}$. Then the problem condition is equivalent to saying that every element of $D(k)$ appears in $\{a_k, \dots, a_{2k}\}$. We prove the following structure claim about all the valid sequences. Claim: In any valid sequence, for each $0 \le k \le n$, $a_{2k-1}$ and $a_{2k}$ are elements of $D(k)$; and $a_k$, \dots, $a_{2k}$ consist of all the numbers from $0$ to $k$ each exactly once. Proof. We proceed by induction; suppose we know it's true for $k$ and want it true for $k+1$. By induction hypothesis: $\{a_k, \dots, a_{2k}\}$ contains each of $0$ to $k$ exactly once; $a_k$ is an element of $D(\left\lceil k/2 \right\rceil)$; We also know $\{a_{k+1}, \dots, a_{2k+2}\}$ contains all elements of $D(k+1)$ by problem condition. However, note that \[ D\left( \left\lceil k/2 \right\rceil \right) \subseteq D(k+1) \]so that means either \[ (a_{2k+1} = a_k \text{ and } a_{2k+2} = k+1) \quad\text{OR}\quad (a_{2k+1} = k+1 \text{ and } a_{2k+2} = a_k). \]$\blacksquare$ We return to the problem of counting the sequences. It suffices to show that if $(a_0, \dots, a_{2n})$ is a valid sequence, there are exactly two choices of ordered pairs $(x,y) \in \{0, \dots, n+1\}$ such that $(a_0, \dots, a_{2n}, x, y)$ is a valid sequence. However, the structure claim above implies that $\{x,y\} = \{a_n, n+1\}$, so there are at most two choices. Moreover, both of them work by the structure claim again (because $k=n=1$ is the only new assertion when augmenting the sequence, and it holds also by the structure claim). This completes the proof. Remark: Here are some examples to follow along with. When $n=4$ the $16$ possible values of $(a_4, a_5, a_6, a_7, a_8)$ are \[ \begin{array}{cc} (2,1,3,4,0) & (2,0,3,4,1) \\ (2,1,3,0,4) & (2,0,3,1,4) \\ (0,1,3,4,2) & (1,0,3,4,2) \\ (0,1,3,4,2) & (1,0,3,4,2) \\ (0,1,3,2,4) & (1,0,3,2,4) \\ (2,3,1,4,0) & (2,3,0,4,1) \\ (2,3,1,0,4) & (2,3,0,1,4) \\ (0,3,1,4,2) & (1,3,0,4,2) \\ (0,3,1,2,4) & (1,3,0,2,4) \\ \end{array} \]Now the point is that when moving to $n=5$, the element $a_4 \in \{0,1,2\} = D(2) \subseteq D(5)$ is chopped-off, and $a_9$ and $a_{10}$ must be $5$ and the chopped-off element in some order. So each of these sequences extends in exactly two ways, as claimed.

The answer is $2^n$. Clearly $a_0=0$, and $\{a_1,a_2\} = \{0,1\}$. The key structural claim is that $\{a_{2k-1},a_{2k}\} = \{a_{k-1},k\}$, call $P(k)$. It is clearly true for $k=1$. Note that one can show $P(1),P(2),\cdots,P(k)$ imply $(a_k,\cdots,a_{2k})$ is a permutation of $\{0,\cdots,k\}$ via induction. Furthermore, $P(1),\cdots,P(k-1)$ and $\{a_k,\cdots,a_{2k}\}$ being permutation of $\{0,\cdots,k\}$ imply that $\{a_{2k-1},a_{2k}\} = \{a_{k-1},k\}$, because I remove $a_{k-1}$, add $a_{2k},a_{2k-1}$, and end up just adding $k$ to the set. I will use $P(1),\cdots,P(k-1)$ to show $\{a_k,\cdots,a_{2k}\}\supset\{0,\cdots,k\}$, which suffices. Let $x \in \{0,\cdots,k\}$. If $x=k$ we are done, since the problem condition tells us that $$\{a_k,\cdots,a_{2k}\} \supset \left\{x,\lfloor \frac x2\rfloor, \cdots, \lfloor \frac{x}{2^m}\rfloor, \cdots, 1,0\right\}. (*)$$ Henceforth assume $x<k$. Then by $P(x)$, we have $x \subset \{a_{2x+1},a_{2x+2}\}$. By $P(2x+1),P(2x+2)$, if $2x+2 < k$ we have $\{a_{2x+1},a_{2x+2} \} \subset \{a_{4x+3},\cdots,a_{4x+6}\}$. (If $2x+1\ge k$ then we also have $\{a_{2x+1},a_{2x+2}\}\subset \{a_k,\cdots,a_{2k}\}$ since $x<k$. If $2x+2=k$ then we have $\{a_{2x+1},a_{2x+2} \} = \{a_k, a_{2k-1},a_{2k}\}$ by $P(k-1)$) We iterate the inductive step. Set a counter $e=2$. At each $e$ we have a set $\{a_{2^ex + (2^e-1)}, \cdots, a_{2^ex + 2^{e+1}-2}\}$ containing $x$, and we want to show it is contained in $\{a_k,\cdots,a_{2k}\}$. If $2^ex + 2^{e+1}-2 < k$ then by inductive hypothesis on $2^ex+(2^e-1)$ to $2^ex + (2^{e+1}-2)$ we have $$ \{a_{2^ex + (2^e-1)}, \cdots, a_{2^ex + 2^{e+1}-2}\} \subset \{ a_{2(2^ex + (2^e-1))+1}, a_{2(2^ex + (2^e-1))+2}, \cdots, a_{2(2^ex + (2^{e+1}-2))+1}, a_{2(2^ex + (2^{e+1}-2))+2} \} = \{a_{2^{e+1}x + (2^{e+1}-1)}, \cdots, a_{2^{e+1}x + 2^{e+2}-2}\} $$ Thus we set $e \leftarrow e+1$. Otherwise, $2^ex + 2^{e+1}-2\ge k$, so $ 2^ex + (2^e-1) > \frac 12 (2^ex + 2^{e+1}-2) \ge \frac k2$. For everything from $2^ex + 2^e-1$ to $k-1$ (possibly there is nothing there) I apply inductive hypothesis, so this ends up giving us a subset of $\{a_k,\cdots,a_{2k}\}$. This proves $P(k)$, as desired. Since the only restrictions we have are $\{a_{2k-1},a_{2k}\} = \{a_{k-1},k\}$, given any $a_0,\cdots,a_{2k-2}$ there are 2 choices for $(a_{2k-1},a_{2k})$. We make $n$ such choices so the answer is $2^n$.