Question

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

Short answer

The solution of the recurrence relation is \({d_n} = 1 + n\).

Step-by-step solution

Linear Homogeneous Recurrence Relations with Constant Coefficients definition

Let\({c_1}\)and\({c_2}\)be real numbers.

Suppose that\({r^2} - {c_1}r - {c_2} = 0\)has two distinct roots\({r_1}\)and\({r_2}\).

Then the sequence\(\left\{ {{a_n}} \right\}\)is a solution of the recurrence relation\({a_n} = {c_1}{a_{n - 1}} + {c_2}{a_{n - 2}}\)if and only if\({a_n} = {\alpha _1}r_1^n + {\alpha _2}r_2^n\)for\(n = 0,1,2, \ldots \), where\({\alpha _1}\)and\({\alpha _2}\)are constants.

Use Recurrence Relations

Let\({d_n}\)represents the determinant of\({{\bf{A}}_n}\)

\({{\bf{A}}_n} = \left( {\begin{array}{*{20}{c}}2&1&0& \ldots &0\\1&2&1& \ldots &0\\0&1&2& \ldots &0\\ \vdots & \vdots & \vdots &{}& \vdots \\0&0&0& \ldots &2\end{array}} \right)\)

Calculate the determinant by expanding the determinant along the upper row, which is the linear combination of the values in the r of the matrix.

The first element in the first row is a 2, while the corresponding minor is a matrix of the form\({{\bf{A}}_{n - 1}}\)which has determinant\({d_{n - 1}}\).

\({d_n} = {( - 1)^{1 + 1}}2{d_{n - 1}} + \ldots \)

Determinant\({d_{n - 1}}\)

\({d_n} = {( - 1)^{1 + 1}}2{d_{n - 1}} + {( - 1)^{2 + 1}}{d_{n - 2}} + \ldots \)

The other terms in the first row are 0:

\(\begin{array}{c}{d_n} = {( - 1)^{1 + 1}}2{d_{n - 1}} + {( - 1)^{2 + 1}}{d_{n - 2}}\\ = 2{d_{n - 1}} - {d_{n - 2}}\end{array}\)

When\(n = 1\):

\({{\bf{A}}_1} = (2){\rm{ }}{d_1} = \left| {{{\bf{A}}_1}} \right| = 2\)

When\(n = 2\)

\(\begin{array}{c}{{\bf{A}}_2} = \left( {\begin{array}{*{20}{l}}2&1\\1&2\end{array}} \right)\\{d_2} = \left| {{{\bf{A}}_2}} \right|\\ = 2 \cdot 2 - 1 \cdot 1\\ = 4 - 1\\ = 3\end{array}\)

Use Recurrence Relations once again

Let\({d_n} = {r^2},{d_{n - 1}} = r\)and\({d_{n - 2}} = 1\)

Equation is:\({r^2} = 2r - 1\)

Subtract\(2r - 1\)from each side:\({r^2} - 2r + 1 = 0\)

Factorize:\({(r - 1)^2} = 0\)

Zero product property:\(r - 1 = 0\)

Solve each equation:\(r = 1\)

The solution of the recurrence relation is of the form\({a_n} = {\alpha _1}r_1^n + {\alpha _2}nr_1^n + \ldots + {\alpha _k}{n^{k - 1}}r_1^n\)with\({r_1}\)a root with multiplicity\(k\)of the characteristic equation.

\(\begin{array}{c}{d_n} = {\alpha _1} \cdot {1^n} + {\alpha _2}n \cdot {1^n}\\ = {\alpha _1} + {\alpha _2}n\end{array}\)

Initial conditions:\(2 = {d_1} = {\alpha _1} + {\alpha _2},3 = {d_2} = {\alpha _1} + 2{\alpha _2}\)

Subtract the previous two equations\(1 = {\alpha _2}\)

Determine\({\alpha _1}\)from\(2 = {\alpha _1} + {\alpha _2}\)and\({\alpha _2} = 1\)

\(\begin{array}{c}{\alpha _1} = 2 - {\alpha _2}\\ = 2 - 1\\ = 1\end{array}\)

Thus the solution of the recurrence relation is\({d_n} = 1 + n\).