What is the general term of this recursive sequence? This real sequence is defied by recursion but I could not find the general term of it. (Really, I have the general term, but I don't know how it's been found.)
Suppose $\{ x_n\}$ is a real sequence which $x_1=\frac{1}{3}$ and for any $n>1$ the terms defined recursively as below:
$$x_{2n}=\frac{1}{3}x_{2n-1}$$
$$x_{2n+1}=\frac{1}{3}+x_{2n}$$
What is the general term of this sequence?
 A: It never hurts to gather some data: the first few terms are
$$\frac13,\frac19,\frac49,\frac4{27},\frac{13}{27},\frac{13}{81},\frac{40}{81},\frac{40}{243},\frac{121}{243}\;.$$
Look at the terms with odd indices: $$\frac13,\frac49,\frac{13}{27},\frac{40}{81},\frac{121}{243}\;.$$ It's pretty apparent that in each case the denominator is one more than twice the numerator. The denominator of $x_{2n-1}$ is evidently $3^n$, and the numerator seems to be $\frac12(3^n-1)$, so we conjecture that
$$x_{2n-1}=\frac{3^n-1}{2\cdot3^n}=\frac12-\frac1{2\cdot3^n}$$
and hence $$x_{2n}=\frac13\left(\frac12-\frac1{2\cdot3^n}\right)=\frac16-\frac1{2\cdot3^{n+1}}\;.$$
Once you make this conjecture, proving it by induction on $n$ is straightforward.
Another approach is to observe that we can write $x_{2n-1}=\frac{a_n}{3^n}$ for some positive integer $a_n$, in which case $x_{2n}=\frac{a_n}{3^{n+1}}$. Now
$$\frac{a_{n+1}}{3^{n+1}}=x_{2n+1}=\frac13+x_{2n}=\frac13+\frac{a_n}{3^{n+1}}=\frac{a_n+3^n}{3^{n+1}}\;,$$
so $a_{n+1}=a_n+3^n$. It follows easily that $$a_n=\sum_{k=0}^{n-1}3^k=\frac{3^n-1}2\;,$$
which is exactly what we conjectured just from the numerical data.
