How to solve system of linear equations that came up in looking at a probability problem, any tricks? The following system of $k$ equations came up in a probability problem I was looking at:
$$(n+1)x_1 - x_2 = 1, \quad x_1 + nx_2 - x_3 = 1 , \quad x_1 + nx_3 - x_4 = 1, \quad x_1 + nx_4 - x_5 = 1, \quad \ldots \quad x_1 + nx_{k-1} - x_{k} = 1, \quad x_1 + nx_{k} = 2,$$which involves solving$$\begin{pmatrix}
        n+1 & -1 & 0 & 0  & \cdots & 0 & 0 & 0\\
        1 & n & -1 & 0  & \cdots & 0 & 0 & 0 \\
       1 & 0 & n & - 1 & \cdots & 0 & 0 & 0\\ 
        \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
1 & 0 & 0 & 0 & \cdots & 0 & n & -1\\
1 & 0 & 0 & 0 & \cdots & 0 & 0 & n\\
        \end{pmatrix} \begin{pmatrix}
        x_1\\
        x_2 \\
       x_3 \\
\vdots \\
x_{k - 1}\\
x_k\\
        \end{pmatrix} = \begin{pmatrix}
        1\\
        1 \\
       1 \\
\vdots \\
1\\
2\\
        \end{pmatrix}$$Now, given that this matrix looks pretty "sparse", I'm wondering if there's any shortcuts that can get us the answer quickly without me having to painstakingly row reduce this augmented matrix by brute force. I've started in the direction of brute force but couldn't see any immediate pattern/simplification.
For the record, the answer in the back of my book is$$x_r = {{n^r - n^{r - 1} + n^{k} - 1}\over{n^{k+1} - 1}}.$$

"Smart" Brute force isn't that bad. We have the following pattern:
$S_1: (n+1) x_1 - x_2 = 1$
$S_2 + nS_1: (n^2+n+1) x_1 - x_3 = 1+n$
$S_3 + nS_2 + n^2 S_1: (n^3+n^2+n+1) x_1 - x_4 = 1+n+n^2$.
$\vdots$
$S_{k-1}+nS_{k-2} + \ldots + n^{k-2}S_1: \frac{n^k-1}{n-1} x_1 - x_k  = \frac{n^{k-1} - 1 } { n-1}$
$S_k: x_1 + nx_k = 2$.
From the last 2 equations, we can get $x_1 = \frac{n^k+n-2}{n^{k+1} - 1}, x_k = \frac{2n^k-n^{k-1} - 1 } {n^{k+1} - 1}$.
Then from the previous equations, we can get $x_i =\frac{ (n^i-1) x_1 - (n^{i-1} -1 ) } { n-1} = \frac{n^i - n^{i-1} + n^k -1}{n^{k+1} - 1 } $.
Observe it has the given form.
