<s>[INST] How to compute the determinant of a tridiagonal matrix with constant diagonals? How to show that the determinant of the following $(n\times n)$ matrix
$$\begin{pmatrix}
5 & 2 & 0 & 0 & 0 & \cdots & 0 \\
2 & 5 & 2 & 0 & 0 & \cdots & 0 \\
0 & 2 & 5 & 2 & 0 & \cdots & 0 \\
\vdots & \vdots& \vdots& \vdots & \vdots & \vdots & \vdots \\
0 & \cdots & \cdots & 0 & 2 & 5 & 2 \\
0 & \cdots & \cdots & \cdots & \cdots & 2 & 5
\end{pmatrix}$$
is equal to $\frac13(4^{n+1}-1)$?

More generally:

How does one compute the determinant of the following tridiagonal matrix (where the three diagonals are constant)?
$$M_n(a,b,c) = \begin{pmatrix}
a & b & 0 & 0 & 0 & \cdots & 0 \\
c & a & b & 0 & 0 & \cdots & 0 \\
0 & c & a & b & 0 & \cdots & 0 \\
\vdots & \vdots& \vdots& \vdots & \vdots& \vdots & \vdots \\
0 & \cdots & \cdots & 0 & c & a & b \\
0 & \cdots & \cdots & \cdots & \cdots & c & a
\end{pmatrix}$$
Here $a,b,c$ can be taken to be real numbers, or complex numbers.

In other words, the matrix $M_n(a,b,c) = (m_{ij})_{1 \le i,j \le n}$ is such that
$$m_{ij} = \begin{cases}
a & i = j, \\
b & i = j - 1, \\
c & i = j + 1, \\
0 & \text{otherwise.}
\end{cases}$$
There does not seem to be an easy pattern to use induction: the matrix is not a diagonal block matrix of the type $M = \bigl(\begin{smallmatrix} A & C \\ 0 & B \end{smallmatrix}\bigr)$ (where we could use $\det(M) = \det(A) \det(B)$ for the induction step), and there are no lines or columns with only one nonzero entry, so Laplace expansion gets complicated quickly.
Is there a general pattern that one could use? Or is the answer only known on a case-by-case basis? It's possible to compute the determinant by hand for small $n$:
$$\begin{align}
\det(M_1(a,b,c)) & = \begin{vmatrix} a \end{vmatrix} = a  \\
\det(M_2(a,b,c)) & = \begin{vmatrix} a & b \\ c & a \end{vmatrix} = a^2 - bc \\
\det(M_3(a,b,c)) & = \begin{vmatrix} a & b & 0 \\ c & a & b \\ 0 & c & a \end{vmatrix} = a^3 - 2abc
\end{align}$$
But there is no readily apparent pattern and the computation becomes very difficult when $n$ gets large.
 [/INST] Let $M_n$ be the $n \times n$ matrix. Calculate the determinant by expanding along the first row and then by the second column, we get $ Det(M_n) = 5 Det(M_{n-1} ) - 4 Det(M_{n-2})$.
Let $Det(M_n) = D_n$, so $D_n$ satisfies the recurrence relation $D_n - 5 D_{n-1} + 4 D_{n-2} = 0$, with initial values $D_0 = 1, D_1 = 5$. The characteristic equation $x^2 - 5x + 4$ has roots $x= 4, 1$, so the solution has form $A4^n + B1^n$. Plugging in the initial values, we get $A= \frac {4}{3}, B= -\frac {1}{3}$, which yields the value $D_n = \frac {1}{3} (4^{n+1} - 1)$.

$D_0 = 1$ because it is the empty product, which by definition has the value 1. If you do not like to use $D_0 = 1$, you can just calculate $D_1 = 5$ and $D_2 = 5 \times 5 - 2 \times 2 = 21$ and then find the values of $A, B$.
</s>