This is the determinant of a matrix of ($n \times n$) that needs to be calculated:
\begin{pmatrix}
3 &2 &0 &0 &\cdots &0 &0 &0 &0\\
1 &3 &2 &0 &\cdots &0 &0 &0 &0\\
0 &1 &3 &2 &\cdots &0 &0 &0 &0\\
0 &0 &1 &3 &\cdots &0 &0 &0 &0\\
\vdots &\vdots &\vdots&\ddots &\ddots &\ddots&\vdots &\vdots&\vdots\\
0 &0 &0 &0 &\cdots &3 &2 &0 &0\\
0 &0 &0 &0 &\cdots &1 &3 &2 &0\\
0 &0 &0 &0 &\cdots &0 &1 &3 &2\\
0 &0 &0 &0 &\cdots &0 &0 &1 &3\\
\end{pmatrix}
The matrix follows the pattern as showed.
I have to calculate it using induction (we haven't learnt recursion so far).
Thanks
Best Answer
Let $D_n$ be the determinant of our matrix of size $n$. We can calculate $D_n$ by expansion of the first column: $D_n = 3 D_{n - 1} - 1 \cdot 2 \cdot D_{n - 2}$. For the second term we expanded again by the first row. We can see: $D_1 = 3$, $D_2 = 7$. By our recurence, we can count more terms: 3, 7, 15, 31, 63, …. Now we can guess that $D_n = 2^{n + 1} - 1$. The formula works for first terms. We will prove the formula by induction. Induction step is: if it works for all $k ≤ n - 1$, then it works for n. We have $D_n = 3 D_{n - 1} - 2 D_{n - 2} = 3 (2^n - 1) - 2 (2^{n - 1} - 1) = 2^{n + 1} - 1$. And we're done.