Evaluate the $n$-th determinant 
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. 
 A: 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.
