Известны первые члены линейной рекуррентной последовательности:

$$ 0,1,2,2,0,-9,-38,-123,-360,-1004,-2728,-7303,\ldots $$ Чему равен следующий?

Теорема. Пусть имеется последовательность $ \{x_j\}_{j=0}^{\infty} $. Если эта последовательность является решением линейного однородного разностного уравнения порядка $ \le n_{} $ , то все главные миноры $ S_0,S_1,S_2,\dots $ бесконечной ганкелевой матрицы

$$ S=\left( \begin{array}{lllll} x_0 & x_1 & x_2 & x_3 & \dots \\ x_1 & x_2 & x_3 & x_4 & \dots \\ x_2 & x_3 & x_4 & x_5 & \dots \\ \dots & & & & \end{array} \right) $$ начиная с порядка $ n+1 $ будут равны $ 0_{} $. В этом случае разностное уравнение должно иметь вид $$ \left| \begin{array}{llllll} x_0 & x_1 & x_2 & x_3 & \dots & x_n \\ x_1 & x_2 & x_3 & x_4 & \dots & x_{n+1} \\ x_2 & x_3 & x_4 & x_5 & \dots & x_{n+2}\\ \dots & & & & & \dots \\ x_{n-1} & x_n & x_{n+1} & & \dots & x_{2n-1} \\ {\color{RubineRed} x_K} & {\color{RubineRed} x_{K+1}} & {\color{RubineRed} x_{K+2}} & & \dots & {\color{RubineRed} x_{K+n}} \end{array} \right|_{n+1}=0 \ . $$ При дополнительных условиях $$ S_n \ne 0, \tilde S_n = \left| \begin{array}{lllll} x_1 & x_2 & \dots & x_{n-1} & x_n \\ x_2 & x_3 & \dots & x_n & x_{n+1}\\ x_3 & x_4 & & x_{n+1} & x_{n+2} \\ \dots & & & & \dots \\ x_{n} & x_{n+1} & \dots & x_{2n-2} & x_{2n-1} \end{array} \right| \ne 0 $$ это уравнение будет уравнением в точности $ n_{} $-го порядка.

Доказательство. Если элементы последовательности удовлетворяют некоторому уравнению вида $$ a_0x_{n+K}+a_1 x_{n+K-1}+ \dots+ a_n x_K = 0 \quad npu \ K\in \{0,1,2,\dots \} $$ при хотя бы одном коэффициенте из $ a_0,a_1,\dots,a_n $ отличном от нуля, то справедливы равенства $$ \begin{array}{lllll} a_n x_0&+ a_{n-1}x_1& + \dots &+a_0x_n & =0, \\ a_n x_1&+ a_{n-1}x_2& + \dots &+a_0x_{n+1} & =0, \\ \dots & & & & \dots \\ a_n x_n&+ a_{n-1}x_{n+1}& + \dots &+a_0x_{2n} & =0. \end{array} $$ Эти равенства составляют систему линейных однородных уравнений относительно коэффициентов. По предположению, система совместна и имеет нетривиальное решение. Но тогда (см. ☞ ЗДЕСЬ) ее определитель $$ \left| \begin{array}{llllll} x_0 & x_1 & x_2 & x_3 & \dots & x_n \\ x_1 & x_2 & x_3 & x_4 & \dots & x_{n+1} \\ x_2 & x_3 & x_4 & x_5 & \dots & x_{n+2}\\ \dots & & & & & \dots \\ x_{n-1} & x_n & x_{n+1} & & \dots & x_{2n-1} \\ x_{n} & x_{n+1} & x_{n+2} & & \dots & x_{2n} \end{array} \right|_{n+1} $$ должен быть равен нулю. Этот определитель совпадает с $ S_{n+1} $ из условия теоремы. Равенство нулю $ S_{n+2}, S_{n+3}, \dots $ доказывается аналогично: если последовательность удовлетворяет уравнению $$ a_0x_{n+K}+a_1 x_{n+K-1}+ \dots+ a_n x_K = 0 \ , $$ то она удовлетворяет и уравнению $$ a_0x_{n+K+1}+a_1 x_{n+K}+ \dots+ a_n x_{K+1}+a_{n+1}x_K = 0 \quad npu \ a_{n+1}=0 \, . $$

Далее, при равенстве нулю определителя матрицы системы уравнений $$ \left(\begin{array}{lllll} x_0 & x_1 & x_2 & \dots & x_n \\ x_1 & x_2 & x_3 & \dots & x_{n+1} \\ \vdots & & & & \vdots \\ x_{n-1} & x_n & x_{n+1} & \dots & x_{2n-1} \\ x_{n} & x_{n+1} & x_{n+2} & \dots & x_{2n} \end{array} \right) \left( \begin{array}{l} a_n \\ a_{n-1} \\ a_{n-2} \\ \vdots \\ a_0 \end{array} \right)= \mathbb O $$ ее фундаментальная система решений будет состоять из единственного набора значений если $ S_n \ne 0 $. Этот набор решений может быть построен с помощью алгебраических дополнений к элементам последней строки матрицы: $$ a_n= (-1)^n\left|\begin{array}{llll} x_1 & x_2 & \dots & x_n \\ x_2 & x_3 & \dots & x_{n+1} \\ \vdots & & & \vdots \\ x_n & x_{n+1} & \dots & x_{2n-1} \end{array} \right| , a_{n-1}= (-1)^{n-1}\left|\begin{array}{llll} x_0 & x_2 & \dots & x_n \\ x_1 & x_3 & \dots & x_{n+1} \\ \vdots & & & \vdots \\ x_{n-1} & x_{n+1} & \dots & x_{2n-1} \end{array} \right|, \dots, a_0= S_n \ . $$ Но это и означает, что разностное уравнение имеет то представление в виде определителя, что указано в теореме. ♦

Пример 1. Известны первые члены линейной рекуррентной последовательности:

$$ 0,1,2,2,0,-9,-38,-123,-360,-1004,-2728,-7303,\ldots $$ Чему равен следующий?

Решение. Имеем: $$ S= \left( \begin{array}{rrrrrrrr} 0 & 1 & 2 &2 &0 & -9 & -38 & \dots \\ 1 & 2 & 2 & 0 & -9 & -38 & -123 & \dots \\ 2 & 2 & 0 & -9 & -38 & -123 & -360 & \dots \\ 2 & 0 & -9 & -38 & -123 & -360 & -1004 & \dots \\ 0 & -9 & -38 & -123 & -360 & -1004 & -2728 & \dots \\ -9 & -38 & -123 & -360 & -1004 & -2728 & -7303 & \dots \\ \dots & & & & & & \end{array} \right) $$ Вычисляем главные миноры: $$ S_1=0,S_2=2,S_3=0,S_4=25,S_5=0,S_6=0,\dots $$ Больше главных миноров вычислить невозможно поскольку последовательность обрывается. Выдвинем в качестве рабочей гипотезы, что наша последовательность «разворачивается в бесконечность» как линейная рекуррентная последовательность порядка $ \le 4 $. Тогда, в соответствии с теоремой эта последовательность является решением разностного уравнения $$ \left| \begin{array}{rrrrr} 0 & 1 & 2 &2 &0 \\ 1 & 2 & 2 & 0 & -9 \\ 2 & 2 & 0 & -9 & -38 \\ 2 & 0 & -9 & -38 & -123 \\ x_K & x_{K+1} & x_{K+2} & x_{K+3} & x_{K+4} \end{array} \right|=0 $$ Раскладываем определитель по последней строке: $$ 25\,x_{K+4}-100\,x_{K+3}+75\,x_{K+2}+50\,x_{K+1}-25\,x_K=0 \iff x_{K+4}=4\,x_{K+3}-3\,x_{K+2}-2\,x_{K+1}+\,x_K \ . $$ По имеющейся у нас информации нельзя гарантировать абсолютную истинность полученного ответа: любую последовательность можно так «испортить» в одном-единственном элементе, чтобы после обращения в нуль любого подряд идущего набора главных миноров матрицы $ S_{} $, очередной главный минор стал бы отличным от нуля. Так что ответ в задаче приходится формулировать так:

Ответ. Если автор задачи не задумал особенную подлость, то очередной элемент последовательности равен $ (-19380) $.

Справедлив и более общий результат, который основан на понятии ранга бесконечной матрицы. По аналогии с конечными матрицами, будем считать ранг бесконечной матрицы равным $ \mathfrak r \in \mathbb N $ если все ее миноры порядка $ \mathfrak r+1 $ равны нулю, и существует хотя бы один минор порядка $ \mathfrak r $ отличный от нуля.

Теорема. Бесконечная ганкелева матрица

$$ H=\left[h_{i+j-2}\right]_{i,j=1}^{\infty} $$ имеет конечный ранг $ n_{} $ тогда и только тогда, когда существуют числа $ a_0,a_1,\dots,a_{n-1} $ такие, что $$ h_{n+K}=a_0h_{n+K-1}+a_1h_{n+K-2}+\dots+a_{n-1}h_{K} \quad npu \quad K\in \{0,1,\dots \} \, , $$ т.е. последовательность $ \{ h_j\}_{j=0}^{\infty} $ является линейной рекуррентной последовательностью порядка $ \le n $.

Пример 2. Найти линейное разностное уравнение задающее последовательность

$$ x_0=-2,\ x_1=-3,\ x_2=-1,\ x_3=2,\ x_4=4,\ x_5=-4,\ $$ $$ x_6=-5,\ x_7=26,\ x_8=11,\ x_9=-85,\ x_{10}=44,\ x_{11}=308,\dots $$

Решение. В отсутствие гипотезы о порядке линейного разностного уравнения, имеет смысл организовать процедуру вычисления кандидата последовательно, начиная с минимально возможного. Так, в рассмотренном примере мы могли бы выдвинуть сначала гипотезу о том, что этот порядок равен $ 1 $: $$ \left| \begin{array}{rr} -2 & -3 \\ x_{K} & x_{K+1} \end{array} \right|=0 \quad \iff \quad -2\, x_{K+1}+3\,x_K=0 \, . $$ Это уравнение правильно определяет элемент последовательности $ x_{1} $ по значению $ x_{0} $. Но величина $ x_2 $ определяется с ошибкой. Рассмотрим следующий по порядку определитель: $$ \left| \begin{array}{rrr} -2 & -3 & -1 \\ -3 & -1 & 2 \\ x_{K} & x_{K+1} & x_{K+2} \end{array} \right|=0 \quad \iff \quad -7\,x_{K+2}+7\,x_{K+1}-7\, x_K =0 \quad \iff \quad x_{K+2}=x_{K+1}-x_K \, . $$ Элементы последовательности $ x_2, x_3 $ определяются из этого уравнения (и из данных значений $ x_0,x_1 $) правильно, но $ x_4 $ определяется неверно. $$ \left| \begin{array}{rrrr} -2 & -3 & -1 & 2 \\ -3 & -1 & 2 & 4 \\ -1 & 2 & 4 & -4 \\ x_{K} & x_{K+1} & x_{K+2} & x_{K+3} \end{array} \right|=0 \quad \iff \quad -7\,x_{K+3}-42\,x_{K+2}+44\,x_{K+1}-52\, x_K =0 $$ $$ \iff \quad x_{K+3}=-6\,x_{K+2}+44/7\,x_{K+1}-52/7x_K \, . $$ Снова два значения $ x_{4} $ и $ x_5 $ определятся правильно, а $ x_6 $ — нет. $$ \left| \begin{array}{rrrrr} -2 & -3 & -1 & 2 & 4 \\ -3 & -1 & 2 & 4 & -4 \\ -1 & 2 & 4 & -4 & -5 \\ 2 & 4 & -4 & -5 & 26 \\ x_{K} & x_{K+1} & x_{K+2} & x_{K+3} & x_{K+4} \end{array} \right|=0 $$ $$ \iff 275\,x_{K+4}+356\,x_{K+3}+1311\,x_{K+2}-627\,x_{K+1}+1191\, x_K =0 $$ Теперь $ x_6 $ и $ x_7 $ находятся верно, но $ x_8 $ — нет: $ -9973/275 \ne 11 $. $$ \left| \begin{array}{rrrrrr} -2 & -3 & -1 & 2 & 4 & -4 \\ -3 & -1 & 2 & 4 & -4 & -5\\ -1 & 2 & 4 & -4 & -5 & 26 \\ 2 & 4 & -4 & -5 & 26 & 11 \\ 4 & -4 & -5 & 26 & 11 & -85 \\ x_{K} & x_{K+1} & x_{K+2} & x_{K+3} & x_{K+4} & x_{K+5} \end{array} \right|=0 $$ $$ \iff \ 12998\, x_{K+5}-12998\, x_{K+4}+38994\, x_{K+3}-77988\, x_{K+2}+25996\, x_{K+1}-12998\, x_{K}=0 \, . $$ $$ \iff x_{K+5}=x_{K+4}-3\, x_{K+3}+6\, x_{K+2}-2\, x_{K+1}+ x_{K} \, . $$ Этот вариант дает верные значения элементов последовательности для всех доступных значений $ K_{} $.

Имеется ли закономерность в формировании последовательноcти этих уравнений?

Для ответа на этот вопрос выпишем их характеристические полиномы: $$ \mathcal H_1(x)=-2\, x+ 3 \ , $$ $$ \mathcal H_2(x)=-7\,x^2+7\,x-7 \ , $$ $$ \mathcal H_3(x)=-7\,x^3-42\,x^2+44\,x-52 \ , $$ $$ \mathcal H_4(x)= 275\,x^4+356\,x^3+1311\,x^2-627\,x+1191 \ , $$ $$ \mathcal H_5(x)=12998\,x^5-12998\,x^4+38994\,x^3-77988\,x^2+25996\,x-12998 \ . $$ Теперь разделим каждый полином, начиная c $ \mathcal H_3 $, на предыдущий (с остатком): $$ \mathcal H_3(x)\equiv (x+7) \mathcal H_2(x) + (2\,x-3) \equiv (x+7) \mathcal H_2(x)- \mathcal H_1(x) \ ; $$ $$ \mathcal H_4(x)\equiv \frac{1}{7}(-275\,x+1294) \mathcal H_3(x)-\frac{75625}{49} \mathcal H_2(x) \ ; $$ $$ \mathcal H_5(x)\equiv \left(\frac{12998}{275}\,x-\frac{8201738}{75625} \right) \mathcal H_4(x)-\frac{168948004}{75625} \mathcal H_3(x) \ . $$ Итак, с точностью до числового сомножителя, остаток от деления $ \mathcal H_{k}(x) $ на $ \mathcal H_{k-1}(x) $ совпадает с $ \mathcal H_{k-2}(x) $. Наблюдение имеет под собой теоретическое обоснование.

Для произвольной числовой последовательности $ \{c\}=\{c_0,c_1,c_2,\dots \} $ определитель $$ \mathcal H_k(x; \{c\}) = \left| \begin{array}{lllll} c_0 & c_1 & c_2 & \ldots & c_{k} \\ c_1 & c_2 & c_3 &\ldots & c_{k+1} \\ \vdots & & & \ddots& \vdots \\ c_{k-1} & c_{k} & c_{k+1} & \ldots & c_{2k-1} \\ 1 & x & x^2 & \ldots & x^{k} \end{array} \right|_{(k+1) \times (k+1)} $$ является полиномом по $ x_{} $; он называется ганкелевым полиномом k-го порядка, порожденным последовательностью $ \{c\} $. Его каноническое представление имеет коэффициентами числовые определители $ k_{} $-го порядка: $$ \mathcal H_k(x; \{c\})\equiv x^{k} \left| \begin{array}{lllll} c_0 & c_1 & \ldots & c_{k-2} & c_{k-1} \\ c_1 & c_2 & \ldots & c_{k-1} & c_{k} \\ \vdots & & \ddots& & \vdots \\ c_{k-1} & c_{k} & \ldots & c_{2k-3} & c_{2k-2} \end{array} \right|- x^{k-1} \left| \begin{array}{lllll} c_0 & c_1 & \ldots & c_{k-2} & c_{k} \\ c_1 & c_2 & \ldots & c_{k-1} & c_{k+1} \\ \vdots & & \ddots& & \vdots \\ c_{k-1} & c_{k} & \ldots & c_{2k-3} & c_{2k-1} \end{array} \right|+ $$ $$ + \dots +(-1)^k \left| \begin{array}{lllll} c_1 & c_2 & \ldots & c_{k-1} & c_{k} \\ c_2 & c_3 & \ldots & c_{k} & c_{k+1} \\ \vdots & & \ddots& & \vdots \\ c_{k} & c_{k+1} & \ldots & c_{2k-2} & c_{2k-1} \end{array} \right| \ . $$ Коэффициенты будем обозначать $ h_{kj} $; таким образом $$ \mathcal H_k(x; \{c\})\equiv h_{k0} x^k +h_{k1} x^{k-1} +\dots + h_{kk} \quad npu \quad h_{k0}= H_k \ ; $$ Коэффициент $ h_{k0} $ может обращаться в нуль, так что степень ганкелевого полинома $ k_{} $-го порядка может оказаться меньше $ k_{} $.

Теорема [Якоби, Йоахимшталь].¹⁾ Любые три ганкелевых полинома $ \mathcal H_{k-2}(x), \mathcal H_{k-1}(x), \mathcal H_{k}(x) $ связаны тождеством

$$ H_k^2\mathcal H_{k-2}(x) + \left(H_kh_{k-1,1}-H_{k-1}h_{k1}-H_kH_{k-1}x\right)\mathcal H_{k-1}(x) + H_{k-1}^2 \mathcal H_{k}(x) \equiv 0 \, . $$

Если $ H_{k} \ne 0, H_{k-1} \ne 0 $ то JJ-тождество может быть переписано в «более симметричном» виде:

$$ \frac{H_k}{H_{k-1}}\mathcal H_{k-2}(x)- \left(x-\frac{h_{k-1,1}}{H_{k-1}}+\frac{h_{k1}}{H_{k}} \right)\mathcal H_{k-1}(x)+\frac{H_{k-1}}{H_{k}}\mathcal H_{k}(x) \equiv 0 \, . $$

JJ-тождество позволяет организовать рекурсивную процедуру вычисления ганкелевых полиномов. Предположим, что канонические представления полиномов $ \mathcal H_{k-2}(x) $ и $ \mathcal H_{k-1}(x) $ уже известны: $$ \mathcal H_{k-1}(x) \equiv h_{k-1,0} x^{k-1}+h_{k-1,1}x^{k-2}+\dots+ h_{k-1,k-1} \quad npu \ h_{k-1,0}=H_{k-1} \, . $$ Тогда в JJ-тождестве известны значения всех констант, за исключением $ H_k $ и $ h_{k1} $. Для последних имеются лишь детерминантные представления: $$ H_k = \left| \begin{array}{lllll} c_0 & c_1 & \dots & c_{k-2} & c_{k-1} \\ c_1 & c_2 & \dots & c_{k-1} & c_{k} \\ \vdots & \vdots & & \vdots & \vdots \\ c_{k-2} & c_{k-1} & \dots & c_{2k-4} & c_{2k-3} \\ c_{k-1} & c_{k} & \dots & c_{2k-3} & c_{2k-2} \end{array} \right| \ , \ h_{k1} = - \left| \begin{array}{lllll} c_0 & c_1 & \dots & c_{k-2} & c_{k} \\ c_1 & c_2 & \dots & c_{k-1} & c_{k+1} \\ \vdots & \vdots & & \vdots & \vdots \\ c_{k-2} & c_{k-1} & \dots & c_{2k-4} & c_{2k-2} \\ c_{k-1} & c_{k} & \dots & c_{2k-3} & c_{2k-1} \end{array} \right| \, . $$ Эти определители отличаются от детерминантного представления $ \mathcal H_{k-1}(x) $ (транспонированного) $$ \left[\mathcal H_{k-1}(x) \right]^{\top} = \left| \begin{array}{llllll} c_0 & c_1 & c_2 & \ldots & c_{k-2} & 1 \\ c_1 & c_2 & c_3 &\ldots & c_{k-1} & x \\ \vdots & & & \ddots & \vdots & \vdots \\ c_{k-1} & c_{k} & c_{k+1} & \ldots & c_{2k-3} & x^{k-1} \end{array} \right| $$ только своими последними столбцами. Разложения определителей по элементам этих последних столбцов имеют одинаковые значения для соответствующих алгебраических дополнений, и поэтому следующие формулы $$ \left\{\begin{array}{rcl} h_{k0}=H_k&=&c_{k-1}h_{k-1,k-1}+c_{k}h_{k-1,k-2}+\dots+c_{2k-2}h_{k-1,0}, \\ h_{k1}&=&-(c_{k}h_{k-1,k-1}+c_{k+1}h_{k-1,k-2}+\dots+c_{2k-1}h_{k-1,0}) \end{array} \right. $$ позволяют вычислить $ h_{k0} $ и $ h_{k1} $ посредством уже известных коэффициентов полинома $ \mathcal H_{k-1}(x) $.

Формула из теоремы применима для рекурсивного вычисления $ \mathcal H_k(x) $. Однако она не работает в случае $ H_{k-1}=0 $. Именно эта ситуация встречается в примере $ 1 $ предыдущего пункта.

Доказательство JJ-формулы для ганкелевых полиномов и ее обобщения ☞ ЗДЕСЬ.

[1]. Иохвидов И.С. Ганкелевы и теплицевы матрицы и формы. М. Наука. 1974.

[2]. Jacobi C.G.J. De eliminatione variabilis e duabus aequationibus algebraicis. J.reine angew. Math. 1836. Bd. 15, S. 101-124

[3]. Joachimsthal F. Bemerkungen über den Sturm'schen Satz. J.reine angew. Math. 1854. Bd. 48, S. 386-416

[4]. Uteshev A., Baravy I., Kalinina E. Rational Interpolation: Jacobi's Approach Reminiscence. Symmetry, 2021, 13 (8), 1401 Текст — в открытом доступе ☞ symmetry-13-01401.pdf