Solve a linear system of equation involving some recursion

Question

$$ \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.

Answer 1

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}

Answer 2

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.