There is a $n\times n$ matrix $A_n=(|i-j|)_{1\le i,j \le n}$ , denote its determinant as $D_n$. Prove $$D_n+4D_{n-1}+4D_{n-2}=0$$ And then find $D_n$.
Notice $a_{ij}=|i-j|$ , it's actually a symmetric matrix. All the techniques I got is add some columns to one column. Then bring up something from the determinant or split it by row or column. But this is a determinant with $n\times n$ elements. So I actually do not have too much experience with this. Thanks for help.
Not sure, where the recursion formula came from. but the determinant can be easily found in two steps.
The matrix $A_n$ has the form
\begin{align} A_n&= \begin{bmatrix} 0&1&2&\cdots&n-1 \\ 1&0&1&\cdots&n-2 \\ 2&1&0&\cdots&n-3 \\ \vdots&\vdots&\vdots&\vdots&\vdots \\ n-2&n-3&n-4&\cdots&1 \\ n-1&n-2&n-3&\cdots&0 \end{bmatrix} \end{align}
As the first step, for all columns of the matrix $A_n$, starting from the second, subtract the previous column.
The obtained matrix $B_n:\ \det(B_n)=\det(A_n)$ has the same first column as the matrix $A_n$ (with elements $0,1,\cdots,n-1$), the other entries that are above the main diagonal, are all $1$, all the rest elements (below and including the main diagonal), are $-1$.
\begin{align} B_n&= \begin{bmatrix} 0&1&1&\cdots&1 \\ 1&-1&1&\cdots&1 \\ 2&-1&-1&\cdots&1 \\ \vdots&\vdots&\vdots&\vdots&\vdots \\ n-2&-1&-1&\cdots&1 \\ n-1&-1&-1&\cdots&-1 \end{bmatrix} \end{align}
Next, add the first row of $B_n$ to all the rows of $B_n$, obtaining the matrix $C_n:\ \det(C_n)=\det(B_n)=\det(A_n)$ with the following structure: its first column is the same, as before, the last row is all zeros, except the first element $c_{n1}=n-1$, and the submatrix $c_{12} \dots c_{n-1,n}$ is upper triangular with the main diagonal that starts with $1$ and has all the rest $n-2$ elements $c_{i,i+1}=2$:
\begin{align} C_n&= \begin{bmatrix} 0&1&1&\cdots&1 \\ 1&0&2&\cdots&2 \\ 2&0&0&\cdots&2 \\ \vdots&\vdots&\vdots&\vdots&\vdots \\ n-2&0&0&\cdots&2 \\ n-1&0&0&\cdots&0 \end{bmatrix} \end{align}
so the determinant now can be easily found using the last row expansion:
\begin{align} \det(A_n)&=(-1)^{n-1}\cdot(n-1)\cdot 2^{n-2} \\ &=(-2)^{n-2}\cdot(1-n) , \end{align}
which agrees with the recursion formula.
