Многие определители порядка $n$ не удаётся сразу привести к треугольному виду, зато их легко выразить через определители того же вида меньшего порядка. Получается рекуррентное соотношение, и задача сводится к его решению.
Если $D_n=p\,D_{n-1}$ с постоянным $p$, то это геометрическая прогрессия: $$D_n=p^{\,n-1}D_1.$$ Пример — задача 293: $D_{2n}=(a^2-b^2)D_{2n-2}$, $D_2=a^2-b^2$, откуда $D_{2n}=(a^2-b^2)^n$.
Если множитель зависит от номера, $D_n=p_n\,D_{n-1}$, то $D_n=p_n\,p_{n-1}\cdots p_2\,D_1$. Так доказывается формула для определителя Вандермонда.
Если $D_n=p\,D_{n-1}+f_n$, то соотношение применяют последовательно («разматывают»): $$D_n=f_n+p\,f_{n-1}+p^2f_{n-2}+\dots+p^{\,n-2}f_2+p^{\,n-1}D_1.$$
Главный источник соотношений второго порядка — определитель $$D_n=\begin{vmatrix}a&b&0&\dots&0&0\\c&a&b&\dots&0&0\\0&c&a&\dots&0&0\\\vdots&&&&&\vdots\\0&0&0&\dots&a&b\\0&0&0&\dots&c&a\end{vmatrix}.$$ Разложим по первой строке: $$D_n=a\,D_{n-1}-b\begin{vmatrix}c&b&0&\dots\\0&a&b&\dots\\0&c&a&\dots\\\vdots&&&\end{vmatrix}.$$ В оставшемся определителе первый столбец равен $(c,0,\dots,0)^{\mathsf T}$; раскладывая по нему, получаем $c\,D_{n-2}$. Итак, $$\boxed{D_n=a\,D_{n-1}-bc\,D_{n-2}},\qquad D_1=a,\quad D_2=a^2-bc.$$ Удобно положить $D_0=1$: тогда $D_2=aD_1-bc\,D_0$, и соотношение верно уже с $n=2$.
Обратите внимание: в соотношение входит только произведение $bc$, а не $b$ и $c$ по отдельности.
Рассмотрим соотношение $$D_n=p\,D_{n-1}+q\,D_{n-2}\qquad(q\ne0).\tag{1}$$ Последовательность однозначно определяется двумя начальными значениями.
Ищем решения в виде геометрической прогрессии $D_n=\lambda^n$. Подставляя и сокращая на $\lambda^{n-2}$, получаем характеристическое уравнение $$\lambda^2=p\lambda+q,\qquad\text{то есть}\qquad\lambda^2-p\lambda-q=0.\tag{2}$$ Пусть $\lambda_1,\lambda_2$ — его корни (возможно, комплексные). По теореме Виета $p=\lambda_1+\lambda_2$, $q=-\lambda_1\lambda_2$, и (1) переписывается так: $$D_n-\lambda_1D_{n-1}=\lambda_2\,(D_{n-1}-\lambda_1D_{n-2}).\tag{3}$$ Значит, последовательность $D_n-\lambda_1D_{n-1}$ — геометрическая прогрессия со знаменателем $\lambda_2$. Дальше два случая.
Если $\lambda_1\ne\lambda_2$ (дискриминант $p^2+4q\ne0$), то $$\boxed{D_n=C_1\lambda_1^n+C_2\lambda_2^n,}$$ а постоянные $C_1,C_2$ находятся из начальных условий — системы двух линейных уравнений $$C_1+C_2=D_0,\qquad C_1\lambda_1+C_2\lambda_2=D_1$$ (или из $D_1$ и $D_2$). Её определитель $\lambda_2-\lambda_1\ne0$, так что решение единственно.
Обоснование. Каждая из прогрессий $\lambda_1^n$, $\lambda_2^n$ удовлетворяет (1), значит, удовлетворяет и любая их комбинация. Подобрав $C_1,C_2$ под начальные значения, получаем последовательность, которая совпадает с $D_n$ при $n=0,1$ и подчиняется тому же соотношению, — следовательно, совпадает с $D_n$ при всех $n$.
Если $\lambda_1=\lambda_2=\lambda$ (дискриминант $p^2+4q=0$, $\lambda=p/2$), то прогрессия $\lambda^n$ одна, и двух постоянных из неё не получить. Из (3): $$D_n-\lambda D_{n-1}=\lambda^{n-1}(D_1-\lambda D_0).$$ Разделим на $\lambda^n$ и обозначим $d_n=D_n/\lambda^n$: $$d_n-d_{n-1}=\frac{D_1-\lambda D_0}{\lambda}=\text{const},$$ то есть $d_n$ — арифметическая прогрессия. Поэтому $$\boxed{D_n=(C_1+C_2\,n)\,\lambda^n,}$$ и постоянные находятся из $C_1=D_0$, $(C_1+C_2)\lambda=D_1$.
Запомнить просто: при кратном корне второе решение — $n\lambda^n$.
Для определителя из п. 3 имеем $p=a$, $q=-bc$, характеристическое уравнение $$\lambda^2-a\lambda+bc=0,$$ начальные значения $D_0=1$, $D_1=a=\lambda_1+\lambda_2$. Отсюда:
Вторая формула получается из первой предельным переходом $\lambda_2\to\lambda_1$: сумма из $n+1$ слагаемых превращается в $(n+1)\lambda^n$. Поэтому вырожденный случай всегда можно проверить, подставив $\lambda_1=\lambda_2$ в развёрнутую сумму.
Если $a,b,c$ вещественны и $a^2<4bc$, корни комплексно сопряжены: $\lambda_{1,2}=r(\cos\theta\pm i\sin\theta)$, где $r=\sqrt{bc}$, $\cos\theta=\dfrac a{2r}$. По формуле Муавра $$D_n=\frac{\lambda_1^{\,n+1}-\lambda_2^{\,n+1}}{\lambda_1-\lambda_2}=r^n\,\frac{\sin(n+1)\theta}{\sin\theta}.$$ Ответ вещественный, хотя корни комплексные.
$$D_5=\begin{vmatrix}5&6&0&0&0\\1&5&6&0&0\\0&1&5&6&0\\0&0&1&5&6\\0&0&0&1&5\end{vmatrix}.$$ Здесь $a=5$, $bc=6$: $D_n=5D_{n-1}-6D_{n-2}$. Характеристическое уравнение $\lambda^2-5\lambda+6=0$, корни $\lambda_1=3$, $\lambda_2=2$. $$D_n=\frac{3^{n+1}-2^{n+1}}{3-2}=3^{n+1}-2^{n+1},\qquad D_5=729-64=665.$$ Проверка: $D_1=9-4=5$, $D_2=27-8=19=25-6$.
$$D_n=\begin{vmatrix}2&1&0&\dots&0\\1&2&1&\dots&0\\0&1&2&\dots&0\\\vdots&&&&\vdots\\0&0&0&\dots&2\end{vmatrix}.$$ $D_n=2D_{n-1}-D_{n-2}$, уравнение $\lambda^2-2\lambda+1=0$, кратный корень $\lambda=1$. Вырожденный случай: $$D_n=(n+1)\cdot1^n=n+1.$$ Проверка: $D_1=2$, $D_2=3$, $D_3=4$. Сравните с задачей 271, где $D_4=5$.
$$D_n=\begin{vmatrix}\alpha+\beta&\alpha\beta&0&\dots&0\\1&\alpha+\beta&\alpha\beta&\dots&0\\0&1&\alpha+\beta&\dots&0\\\vdots&&&&\vdots\\0&0&0&\dots&\alpha+\beta\end{vmatrix}.$$ $D_n=(\alpha+\beta)D_{n-1}-\alpha\beta D_{n-2}$; характеристическое уравнение $\lambda^2-(\alpha+\beta)\lambda+\alpha\beta=0$ имеет корни $\alpha$ и $\beta$.
Единая запись, годная в обоих случаях: $D_n=\alpha^n+\alpha^{n-1}\beta+\dots+\alpha\beta^{n-1}+\beta^n$.
Примеры 1 и 2 — частные случаи: $\alpha=3,\beta=2$ и $\alpha=\beta=1$.
На диагонали $c$, над ней $a$, под ней $b$: $D_n=cD_{n-1}-ab\,D_{n-2}$, уравнение $\lambda^2-c\lambda+ab=0$, $$\lambda_{1,2}=\frac{c\pm\sqrt{c^2-4ab}}2.$$
$$D_n=\begin{vmatrix}2\cos\theta&1&0&\dots&0\\1&2\cos\theta&1&\dots&0\\\vdots&&&&\vdots\\0&0&0&\dots&2\cos\theta\end{vmatrix}.$$ $D_n=2\cos\theta\,D_{n-1}-D_{n-2}$, уравнение $\lambda^2-2\cos\theta\,\lambda+1=0$, корни $\lambda_{1,2}=\cos\theta\pm i\sin\theta$.
Вырожденные значения согласованы с общей формулой: $\lim\limits_{\theta\to0}\dfrac{\sin(n+1)\theta}{\sin\theta}=n+1$.
Задача 311 (на диагонали $x$, рядом единицы) сводится к этой подстановкой $x=2\cos\theta$ при $|x|<2$; при $x=\pm2$ — вырожденный случай, $D_n=(\pm1)^n(n+1)$.
$$D_n=\begin{vmatrix}1&1&0&\dots&0\\-1&1&1&\dots&0\\0&-1&1&\dots&0\\\vdots&&&&\vdots\\0&0&0&\dots&1\end{vmatrix}.$$ Здесь $a=1$, $bc=-1$: $D_n=D_{n-1}+D_{n-2}$, $D_1=1$, $D_2=2$ — последовательность $1,2,3,5,8,13,\dots$ Корни уравнения $\lambda^2-\lambda-1=0$: $\lambda_{1,2}=\dfrac{1\pm\sqrt5}2$, и $$D_n=\frac1{\sqrt5}\left[\Bigl(\frac{1+\sqrt5}2\Bigr)^{n+1}-\Bigl(\frac{1-\sqrt5}2\Bigr)^{n+1}\right]$$ (формула Бине).
$$D_n=\begin{vmatrix}\alpha&\alpha\beta&0&\dots&0\\1&\alpha+\beta&\alpha\beta&\dots&0\\0&1&\alpha+\beta&\dots&0\\\vdots&&&&\vdots\\0&0&0&\dots&\alpha+\beta\end{vmatrix}.$$ От примера 3 отличается только левый верхний элемент. Чтобы миноры были определителями того же вида, раскладываем по последней строке: соотношение прежнее, $D_n=(\alpha+\beta)D_{n-1}-\alpha\beta D_{n-2}$, корни те же — $\alpha$ и $\beta$. Но начальные значения другие: $$D_1=\alpha,\qquad D_2=\alpha(\alpha+\beta)-\alpha\beta=\alpha^2.$$ При $\alpha\ne\beta$ из $C_1\alpha+C_2\beta=\alpha$, $C_1\alpha^2+C_2\beta^2=\alpha^2$ получаем $C_1=1$, $C_2=0$, то есть $$D_n=\alpha^n.$$ При $\alpha=\beta$ тот же ответ: из $(C_1+C_2)\alpha=\alpha$, $(C_1+2C_2)\alpha^2=\alpha^2$ следует $C_1=1$, $C_2=0$.
Вывод: корни характеристического уравнения определяются соотношением, а постоянные — начальными значениями; их нужно считать отдельно в каждой задаче.
Соотношение $D_n=p\,D_{n-1}+q\,D_{n-2}$, характеристическое уравнение $\lambda^2-p\lambda-q=0$.
Фаддеев: 281, 306, 307, 308, 310, 311, 312.