<s>[INST] Solve a linear system of equation involving some recursion $$
\begin{align*}
x_{1} &= 1 + x_{2}\\
x_{2} &= 1 + \frac{1}{2} x_{3} + \frac{1}{2} x_{1}\\
&\vdots\\
x_{i} &= 1 + \frac{1}{2} x_{i+1} + \frac{1}{2} x_{1}\\
&\vdots\\
x_{n-2} &= 1 + \frac{1}{2} x_{n-1} + \frac{1}{2} x_{1}\\
x_{n-1} &= 1 + \frac{1}{2} x_{n} + \frac{1}{2} x_1 \\
x_{n} &= 0 \\
\end{align*}
$$
EDIT: I found one way to solve this. It's simply plugging successive $x_i$ into the first equation. When you reach $x_n$, since $x_n = 0$, you end up with an equation of just $x_1$ which you can solve (using geometric sum) to get $x_1 = 3\times 2^{n-2} - 2$. The rest then is easy. 
If you have a more elegant solution, please share.
 [/INST] I claim that $x_{n-k}=\left(1-\frac{1}{2^k}\right)\left(2+x_1\right)$.  To see this, compute the first few terms of the "backwards" sequence $x_{n},x_{n-1},x_{n-2},...$
\begin{align}
x_n&=0 \\
x_{n-1}&=1+\frac{1}{2}\left(1+\frac{1}{2}x_1\right)+\frac{1}{2}x_1 \\
&=\left(1+\frac{1}{2}\right)+\left(\frac{1}{2}+\frac{1}{4}\right)x_1 \\
x_{n-2}&=1+\frac{1}{2}\left(\left(1+\frac{1}{2}\right)+\left(\frac{1}{2}+\frac{1}{4}\right)x_1\right)+\frac{1}{2}x_1 \\
&=\left(1+\frac{1}{2}+\frac{1}{4}\right)+\left(\frac{1}{2}+\frac{1}{4}+\frac{1}{8}\right)x_1 \\
\end{align}
These are very clearly geometric sums in $r=\frac{1}{2}$.  Applying the formula $S(n)=\frac{1-r^n}{1-r}$, I get the formula $2\left(1-\frac{1}{2^n}\right)$.  To verify, it gives the sequence $0,1,\frac{1}{2},...$, which is what we want.
So, we can write:
\begin{align}
x_{n-k}&=2\left(1-\frac{1}{2^k}\right)+\left(1-\frac{1}{2^k}\right)x_1 \\
&=\left(1-\frac{1}{2^k}\right)(2+x_1)
\end{align}
Now that we have our general formula, we can calculate $x_1$:
\begin{align}
x_1&=x_{n-(n-1)}=\left(1-\frac{1}{2^{n-1}}\right)(2+x_1) \\
0&=2\left(1-\frac{1}{2^{n-1}}\right)+x_1\left(1-1-\frac{1}{2^{n-1}}\right)\\
\frac{x_1}{2^{n-1}}&=2\left(1-\frac{1}{2^{n-1}}\right)\implies x_1=2^n-2 \\
x_{n-k}&=\left(1-\frac{1}{2^k}\right)(2+2^n-2)=2^{n}-2^{n-k}
\end{align}
From this and from our formula for $x_1$ (and the fact that $x_n=0$), it seems clear that $x_i=2^n-2^i$, giving us our solution.
</s>