Need help calculating this determinant using induction 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
 A: 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.
A: You have a tridiagonal matrix.
It's determinant can be written as a recurrence relation:
$$\det A \stackrel{\textrm{def}}{=} f_n = a_nf_{n-1} + c_{n-1}b_{n-1}f_{n-2}.$$
Define $f_0 = 1, f_{-1} = 0$.
However, your $a_n, b_n, c_n$ values are constant, so
$$ \det A = 3f_{n-1}+ 2 f_{n-2}.$$
Thus, you have
$$\begin{align*}
n = 1: & f_1 = 3f_0 + 2f_{-1} = 3 \\
n = 2: & f_2 = 3f_1 + 2f_0 = 3\cdot 3 + 2 = 11 \\
n = 3: & f_3 = 3f_2 + 2f_1 = 33 + 6 = 39 \\
\vdots & 
\end{align*}
$$
