A common term for $a_n=\begin{cases} 2a_{n-1} & \text{if } n\ \text{ is even, }\\ 2a_{n-1}+1 & \text{if } n\ \text{ is odd. } \end{cases}$ When I was answering a question here, I found a sequence as a recursive one as given below. 
$a_1=1$, and for $n>1$, 
$$a_n=\begin{cases}
2a_{n-1} & \text{if } n\ \text{ is even, }\\
2a_{n-1}+1 & \text{if } n\ \text{ is odd. }
\end{cases}$$
I need to find a common term for this sequence. For example, for the sequence $a_1=2$ and $a_n=2a_{n-1}$, for $n>1$, the common term is $a_n=2^n$.
I appreciate any answer or hint in advance.
 A: Note that in binary we have 
$$\begin{align*}
a_1&=1\\
a_2&=10\\
a_3&=101\\
a_4&=1010\\
a_5&=10101\;,
\end{align*}$$
displaying a pattern easily shown by induction to be real. Now note that the binary expansion of $\frac23$ is $\frac23=0.\overline{10}_{\text{two}}$, so that 
$$\begin{align*}
2\cdot\frac23&=1.\overline{01}_{\text{two}}\\
2^2\cdot\frac23&=10.\overline{10}_{\text{two}}\\
2^3\cdot\frac23&=101.\overline{01}_{\text{two}}\\
2^4\cdot\frac23&=1010.\overline{10}_{\text{two}}\\
2^5\cdot\frac23&=10101.\overline{01}_{\text{two}}\;,
\end{align*}$$
and therefore
$$a_n=\left\lfloor 2^n\cdot\frac23\right\rfloor=\left\lfloor\frac{2^{n+1}}3\right\rfloor\;.$$
If you really want to get rid of the floor function, observe that $2^{n+1}\equiv 1\pmod3$ when $n$ is odd, and $2^{n+1}\equiv2\pmod3$ when $n$ is even, so
$$\left\lfloor\frac{2^{n+1}}3\right\rfloor=\begin{cases}
\dfrac{2^{n+1}-1}3,&\text{if }n\text{ is odd}\\
\dfrac{2^{n+1}-2}3,&\text{if }n\text{ is even}\;.
\end{cases}$$
Now
$$\frac12\big(1+(-1)^n\big)=\begin{cases}
0,&\text{if }n\text{ is odd}\\
1,&\text{if }n\text{ is even}\;,
\end{cases}$$
so
$$\begin{align*}
\left\lfloor\frac{2^{n+1}}3\right\rfloor&=\frac13\left(2^{n+1}-1-\frac12\big(1+(-1)^n\big)\right)\\
&=\frac13\left(2^{n+1}-\frac12\left(3+(-1)^n\right)\right)\\
&=\frac16\left(2^{n+2}-3-(-1)^n\right)\;.
\end{align*}$$
A: This answer deals with how one can solve the recursion using the standard (textbook) method. We can write your recursion on the form
$$a_n - 2a_{n-1} = f(n)$$
where $f(n) = 1$ when $n$ is odd and zero otherwise. In this form it's easy to see that the homogenous solution is $a_n^{\rm h} = c\cdot2^n$ as the characteristic equation is simply $\lambda-2 = 0$. To find a particular solution note that we can write $f(n)$ as  
$$f(n) = \frac{1 - (-1)^n}{2}$$
which motivates the ansatz $a_n^{\rm p} = A + B(-1)^n$ (always try a test-solution on a similar form as the right hand side). Inserting this into the recursion and solving for $A,B$ gives us the particular solution $a_n^{\rm p} = -\frac{1}{2} - \frac{(-1)^n}{6}$. Finally imposing $a_1=1$ determines $c = \frac{2}{3}$ and gives us the final solution $a_n = a_n^{\rm h} + a_n^{\rm p} = \frac{2^{n+2} - (-1)^{n} - 3}{6}$.
A: It can often be helpful to just write out the first couple of terms:
$$\begin{align}
a_1 &= 1 \\
a_2 &= 2 \\
a_3 &= 5 = 2^2 + 1\\
a_4 &= 10 = 2^3 + 2 \\
a_5 &= 21 = 2^4 + 5 = 2^4 + 2^2 + 1\\
a_6 &= 42 = 2^5 + 10 = 2^5 + 2^3 + 2\\
a_7 &= 85 = 2^6 + 21 = 2^6 + 2^4 + 5 = 2^6 + 2^4 + 2^2 + 1\\
a_8 &= 170 = 2^7 + 42 = 2^7 + 2^5 + 10 = 2^7 + 42 = 2^7 + 2^5 + 2^3 + 2
\end{align}
$$
Do you see a pattern? You basically just need to find an expression changing between $1$ and $2$.
