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}}.$$
 A: 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 } $,

A: Note that we have $\forall r\in [2,k]$
$$x_r=nx_{r-1}+x_1-1$$
With the condition that $x_k=\frac{2-x_1}{n}$. Note that we can actually solve this recursion for a general formula. Shift the indices up by $1$ to get that
$$x_{r+1}=nx_r+x_1-1$$
and subtract the two equations to get
$$x_{r+1}-(n+1)x_r+nx_{r-1}=0$$
Note that we dropped the constant $x_1-1$ term(s) and increased the degree of our recursion. We will need to "reimplement" that term(s) later.
This has characteristic polynomial $x^2-(n+1)x+n=(x-n)(x-1)$. Hence, $x_r=an^r+b$ for some constants $a,b$. We know that $x_1=an+b$, $x_2=an^2+b$ and $x_k=an^k+b$. From our given problem, we know
$$\begin{cases}(an^2+b)=(n+1)(an+b)-1\\n(an^k+b)=2-an-b\end{cases}$$
This first equation is where we "reimplement" the term(s) we dropped (we account for the dropping of the terms by increasing the degree and therefore requiring another initial condition, which can be created by using any specific value of $r$ in the initially found recurrence).
$$\begin{cases}an^2+b=an^2+bn+an+b-1\\an^{k+1}+bn=2-an-b\end{cases}$$
$$\begin{cases}1=bn+an\\an^{k+1}+bn=2-an-b\end{cases}$$
$$\begin{cases}a+b=\frac{1}{n}\\an^{k+1}+b=2-(an+bn)\end{cases}$$
$$\begin{cases}a+b=\frac{1}{n}\\an^{k+1}+b=1\end{cases}$$
$$\begin{cases}a+b=\frac{1}{n}\\a(n^{k+1}-1)=1-\frac{1}{n}\end{cases}$$
$$\begin{cases}a+b=\frac{1}{n}\\a=\frac{n-1}{n(n^{k+1}-1)}\end{cases}$$
$$\begin{cases}b=\frac{1}{n}-\frac{n-1}{n(n^{k+1}-1)}\\a=\frac{n-1}{n(n^{k+1}-1)}\end{cases}$$
$$\begin{cases}b=\frac{n^k-1}{n^{k+1}-1}\\a=\frac{n-1}{n(n^{k+1}-1)}\end{cases}$$
So we have that $x_r=an^r+b=\frac{(n-1)n^{r-1}}{n^{k+1}-1}+\frac{n^k-1}{n^{k+1}-1}$
A: "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.
