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.
 A: Disclaimer
I'm gonna write couple of terms and then general equation for both forward and backward substitution, so you'll need to use mathematical induction to actually prove them
First, substitute $x_1$ to the second equation
$$
2 x_2 = 2 + x_3 + x_1 = 2 + x_3 + 1 + x_2 = 3 + x_3 + x_2 \implies x_2 = 3\cdot 2^0 + x_3
$$
Now, substitute both $x_2$ and $x_1$ to the equation for $x_3$
$$
2x_3 = 2 + x_4 + x_1 = 2 + x_4 + 1 + x_2 = 3 + x_4 + 3 + x_3 = 3 \cdot 2^1 + x_4 + x_3 \implies x_3 = 3 \cdot 2^1 + x_4
$$
Now you can prove (using mathematical induction) that
$$
x_{n-1} = 3 \cdot 2^{n-3} + x_n
$$
Now, do backward substitution by using $x_n = 0$ 
$$
x_{n-1} = 3 \cdot 2^{n-3}
$$
and then
$$
x_{n-2} = 3 \cdot 2^{n-4} + x_{n-1} = 3 \cdot 2^{n-4} + 3 \cdot 2^{n-3} = 3 \cdot 2^{n-4} (2^0 + 2^1)
$$
and one more
$$
x_{n-3} = 3 \cdot 2^{n-5} + x_{n-2} = 3 \cdot 2^{n-5} + 3 \cdot 2^{n-4}(2^0 + 2^1) = 3 \cdot 2^{n-5} (2^0 + 2^1 + 2^2)
$$
Now, you can prove that
$$
x_{n - k} = 3 \cdot 2^{n-k-2} (2^0 + 2^1 + \ldots + 2^{k-1})
$$
In the parenthesis is nothing but simple geometric progression, so
$$
x_{n-k} = 3 \cdot 2^{n-k-2} (2^k - 1)
$$
You can do that all the way until $k = n - 2$ to find $x_2$
$$
x_2 = 3 \cdot 2^0 (2^{n-2} - 1) = 3(2^{n-2}-1)
$$
and finally
$$
x_1 = 1 + x_2 = 3 \cdot 2^{n-2} - 2
$$
Summary
\begin{align}
x_1 &= 3 \cdot 2^{n-1} - 2 \\
x_i &= 3 \cdot 2^{i-2} (2^{n-i} - 1)\quad \text{for}\ 2 \le i < n\\
x_n &= 0
\end{align}
A: 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.
