I intuitively understand it but can't formulate a correct induction

Question

I have a matrix defined this way :
$m_{ij} = 0$ if $j < i - 1$ or if $j > i +1$
$m_{ij} = 1$ if $j = i - 1$
$m_{ij} = 3$ if $j = i$
$m_{ij} = 2$ if $j = i + 1$

Therefore for matrix size 1x1 I have : $$ \begin{bmatrix} 3 \end{bmatrix} $$

For size 2x2 I have : $$ \begin{bmatrix} 3 & 2\\ 1 & 3 \end{bmatrix} $$

3x3 :
$$ \begin{bmatrix} 3 & 2 & 0\\ 1 & 3 & 2\\ 0 & 1 & 3 \end{bmatrix} $$
For 4x4 :
$$ \begin{bmatrix} 3 & 2 & 0 & 0\\ 1 & 3 & 2 & 0\\ 0 &1 & 3 & 2\\ 0 &0 & 1 & 3 \end{bmatrix} $$

We note $d_n$ the determinant of matrix of size $n*n$ I am asked to prove (using induction) that $\forall n\ge 3, d_n = 3d_{n-1} - 2d_{n-2}$ , I do see why it works like that, but I have a hard time explaining it in concise mathematical terms...

How can I do that? Thank you!

Answer 1

Begin with the first couple of cases $d_3$ and $d_4$, which are easy to see. Then for the inductive step simply use the rules of determinants (see https://people.richland.edu/james/lecture/m116/matrices/determinant.html) and expand along the top row of the n'th matrix to see the formula for $d_n$.

If you don't know about the expansion rule for determinants just give it a search - there's plenty of material out there.

EDIT: a quick edit to explain general inductive reasoning in case you aren't sure:

1. Do the first couple of cases by hand (sometimes called the 'base cases')

2. Assume the hypothesis for some $k < n$ (or all $k < n$ for strong induction)

3. Show that the $k+1$ formula follows from knowing the hypothesis above

Then since you know the first couple of cases for $n = 1,2$ it follows that the hypothesis is true for $n =3,4,5...$

Answer 2

Denote $D_n$ as the $n \times n$ matrix defined in your question. Taking cofactor expansion along the first row $(R_1)$ gives \begin{align} |D_n| & = 3|D_{n-1}| - 2 \text{det}\left(\left\{\begin{matrix} 1 & 2 & 0 & \dots \\ 0 & 3 & 2 & \dots \\ 0 & 1 & 3 & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{matrix}\right\}\right) \\ & = 3|D_{n-1}| - 2|D_{n-2}|. \end{align} The second equality is obtained by applying cofactor expansion along the first column $(C_1)$ of the last matrix.