(Linear algebra required ) Let $A_{n}$ be the $n \times n$ matrix with $2s$ on its main diagonal, $1s$ in all positions next to a diagonal element, and $0s$ everywhere else. Find a recurrence relation for $d_{n},$ the determinant of $A_{n}.$ Solve this recurrence relation to find a formula for $d_{n}.$
