<s>[INST] 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}}.$$
 [/INST] Another approach, by solving a linear 2-term recurrence relation.
Let $ y_i = x_i - \frac{ 1-x_1}{ n-1}$.
Then, the equations become
$ny_i - y_{i+1} = 0$ for $ i = 1$ to $k-1$ and $y_1 + ny_k = 2  - \frac{n+1}{n-1} ( 1 - x_1)$,
which then become
$ y_{i+1} = n^{i} y_1 $ for $ i = 1 $ to $k-1$ and  $y_1 (1+n^k) = 2 - \frac{n+1}{n-1} ( 1 - x_1)$.
Since $y_1 = x_1 - \frac{1-x_1} {n-1}$, the previous equation is only in terms of $x_1$, from which we get $x_1 = \frac{n^k + n - 2 } { n^{k+1} - 1 } $. So
$$x_i = y_i + \frac{1-x_1}{n-1} = n^{i-1} y_1 + \frac{1-x_1}{n-1} = \frac{n^i - n^{i-1} + n^k - 1 } { n^{k+1} - 1 }.$$
Notes

*

*Once $y_{i+1} = n^i y_1$, we can conclude that $x_i = n^{i-1} (x_1 - \frac{ 1-x_1}{ n-1})+ \frac{1-x_1}{n-1}$ which was Alan's $x_r = n^ra + b $form.

*If helpful to verify the calculations, we have $ \frac{1-x_1}{n-1} = \frac{n^k-1}{n^{k+1} - 1 } $, $y_1 = \frac{n-1}{n^{k+1} - 1 } $,

</s>