<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] The determinant can also be verified using block determinants.
Define $A^{(k)}$ to be the $k\times k$ matrix of the form$$A^{(k)}:=
        \begin{bmatrix}
        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& & 0& 2 &5& 2\\
        0 & \cdots & & \cdots&\cdots& 2 &5
        \end{bmatrix}.
$$
This can be expressed as
$$A^{(k)}=\begin{bmatrix}A^{(k-1)}&u\\u^T&5\end{bmatrix},$$
where $u=[0,0,0,\ldots,2]^T$ is a $k\times1$ vector.
It follows form the block determinant form that
$$
\det\left(A^{(k)}\right)=\det\left(A^{(k-1)}\right)\det\left(5-u^T{\left(A^{(k-1)}\right)}^{-1}u\right),
$$
which can be simplified dramatically by the structure of $u$ as
$$
\det\left(A^{(k)}\right)=\det\left(A^{(k-1)}\right)\left(5-4{\left(A^{(k-1)}\right)}^{-1}_{n,n}\right).
$$
Furthermore,
$$\left(A^{(k-1)}\right)^{-1}_{n,n}=\frac{(-1)^{n+n}\det\left(A^{(k-2)}\right)}{\det\left(A^{(k-1)}\right)}=\frac{\det\left(A^{(k-2)}\right)}{\det\left(A^{(k-1)}\right)}.$$
The recurrence relation for the determinant can then be written as, upon simplifying,
$$\det\left(A^{(k)}\right)=5\det\left(A^{(k-1)}\right)-4\det\left(A^{(k-2)}\right),$$
from which the required form of the determinant can be verified similarly to the previous answers.
</s>