, 2020

Solution:

Note that $a_{2^{n}-1}=1$ for all $n$ by repeatedly applying $a_{2i+1}=a_{i}$. Now let $b_{n}=a_{0}+a_{1}+a_{2}+\cdots+a_{2^{n}-1}$. Applying the given recursion to every term of $b_{n}$ except $a_{0}$ gives
$$\begin{aligned} b_{n}= & a_{0}+a_{1}+a_{2}+a_{3}+\cdots+a_{2^{n}-1} \\ = & a_{0}+a_{2}+a_{4}+\cdots+a_{2^{n}-2}+a_{1}+a_{3}+\cdots+a_{2^{n}-1} \\ = & a_{0}+\left(a_{0}+a_{1}\right)+\left(a_{1}+a_{2}\right)+\left(a_{2}+a_{3}\right)+\cdots+\left(a_{2^{n-1}-2}+a_{2^{n-1}-1}\right) \\ & +a_{0}+a_{1}+a_{2}+\cdots+a_{2^{n-1}-1} \\ = & 3 a_{0}+3 a_{1}+3 a_{2}+\cdots+3 a_{2^{n-1}-2}+3 a_{2^{n-1}-1}-a_{2^{n-1}-1} \\ = & 3 b_{n-1}-1 . \end{aligned}$$
Now we easily obtain $b_{n}=\frac{3^{n}+1}{2}$ by induction.

Solution:

Define a binary string to be good if it is the null string or of the form $101010 \ldots 10$. Let $c_{n}$ be the number of good subsequences of $n$ when written in binary form. We see $c_{0}=1$ and $c_{2n+1}=c_{n}$ because the trailing $1$ in $2n+1$ cannot be part of a good subsequence. Furthermore, $c_{2n+2}-c_{n+1}$ equals the number of good subsequences of $2n+2$ that use the trailing $0$ in $2n+2$. We will show that this number is exactly $c_{n}$.

Let $s$ be a good subsequence of $2n+2$ that contains the trailing $0$. If $s$ uses the last $1$, remove both the last $1$ and the trailing $0$ from $s$; the result $s'$ will be a good subsequence of $n$. If $s$ does not use the last $1$, consider the sequence $s'$ where the trailing $0$ in $2n+2$ is replaced by the last $0$ in $n$ (which is at the same position as the last $1$ in $2n+2$.) The map $s \mapsto s'$ can be seen to be a bijection, and thus $c_{2n+2}=c_{n}+c_{n+1}$.

Now it is clear that $a_{n}=c_{n}$ for all $n$. Consider choosing each binary string between $0$ and $2^{n}-1$ with equal probability. The probability that a given subsequence of length $2k$ is good is $\frac{1}{2^{2k}}$. There are $\binom{n}{2k}$ subsequences of length $2k$, so by linearity of expectation, the total expected number of good subsequences is
$$\sum_{k=0}^{\lfloor n / 2\rfloor} \frac{\binom{n}{2k}}{2^{2k}}=\frac{(1+1/2)^{n}+(1-1/2)^{n}}{2}=\frac{3^{n}+1}{2^{n+1}}$$
This is equal to the average of $a_{0}, \ldots, a_{2^{n}-1}$, therefore the sum $a_{0}+\cdots+a_{2^{n}-1}$ is $\frac{3^{n}+1}{2}$.