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.