Взаимно-рекуррентные последовательности

[Dave]

$n$ и $m$ - некоторые натуральные числа. $n$ последовательностей $X^{(r)}=\lbrace x_k^{(r)} \rbrace _{k=1}^{\infty}$, $r=\overline{1,\,n}$ связаны линейными рекуррентными соотношениями

$$x_k^{(r)}=\sum_{i=1}^m \sum_{j=1}^n \, a_{rj}^{(i)} \, x_{k-i}^{(j)} \, ,$$

для любых $k>m$, $r=\overline{1,\,n}$; где $a_{rj}^{(i)}$ , $r=\overline{1,\,n}$, $j=\overline{1,\,n}$, $i=\overline{1,\,m}$ - некоторые константы. Другими словами, очередной элемент каждой из последовательностей равен произвольной, но постоянной линейной комбинации предыдущих $m$ элементов этой и других последовательностей.
Докажите, что существуют такие числа $b_1,b_2,\ldots,b_{nm}$ , зависящие только от $a_{rj}^{(i)}$ , что каждая из последовательностей $X^{(r)}$ в отдельности удовлетворяет одному и тому же рекуррентному соотношению

$$x_k^{(r)}=\sum_{i=1}^{nm} \, b_i \, x_{k-i}^{(r)} \, ,$$

для любых $k>nm$, $r=\overline{1,\,n}$.

[TOTAL]

$$x_k^{(r)}=\sum_{i=1}^m \sum_{j=1}^n \, a_{rj}^{(i)} \, x_{k-i}^{(j)}$$

Запишем эти равенства в виде $Ax=0,$ где $x$ - вектор длины $n,$ а $A$ - матрица $n \times n,$ элементы которой являются полиномами степени $m$ (только диагональные элементы имеют ненулевые свободные члены равные -1). Коэффициенты в полиномах равны $a_{rj}^{(i)},$ степень слагаемых определяет сдвиг (уменьшение индекса). Умножим $Ax=0$ слева на транспонированную матрицу алгебраических дополнений и получим что надо.

[Dave]

Не понял. Возьмём простейший случай $n=m=1$, $x_{k}=ax_{k-1}$ (геометрическая прогрессия). Тогда в Вашем решении $A=(-1+ax)$; $Ax=0$ означает, что при умножении многочлена $-1+ax$ на какой-то произвольный скаляр (или $x$ ?) всегда будет $0$. Но это же не так!

[TOTAL]

Dave в сообщении #586460 писал(а):

Не понял. Возьмём простейший случай $n=m=1$, $x_{k}=ax_{k-1}$ (геометрическая прогрессия). Тогда в Вашем решении $A=(-1+ax)$; $Ax=0$ означает, что при умножении многочлена $-1+ax$ на какой-то произвольный скаляр (или $x$ ?) всегда будет $0$. Но это же не так!

В моем решении надо записать $Ax=0,$ затем $Det(A)x_k=0,$
что для $x_{k}=ax_{k-1}$ дает $(-1+at)x_k=0,$ где $t^s x_k=x_{k-s}$

Вот еще пример
$x_k=x_{k-1} + 2y_{k-1}+20y_{k-2}$
$y_k=3x_{k-1} + 4y_{k-1}$

Сразу получаем искомое соотношение
$((-1+t)\cdot(-1+4t)-(2t+20t^2)\cdot(3t))x_k=0$

[Dave]

Можно также искать коэффициенты $b_i$ и доказывать требуемое свойство через характеристический многочлен блочной матрицы

$$M = \begin{pmatrix} A_1 & A_2 & \cdots & A_{m-1} & A_m \\ E & 0 & \cdots & 0 & 0 \\ 0 & E & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & E & 0 \end{pmatrix},$$

где $A_i=a_{rj}^{(i)}$, $i=\overline{1,m}$ - матрицы размера $n \times n$, составленные из исходных коэффициентов, $E$ и $0$ - соответственно единичная и нулевая матрицы размера $n \times n$. Матрица $M$ имеет размер $nm \times nm$; $b_i$ будут коэффициентами её характеристического многочлена:

$$\det \, (M-\lambda E_{nm})=(-1)^{nm}(\lambda^{nm}-b_1 \lambda^{nm-1}-b_2 \lambda^{nm-2} - \ldots - b_{nm}),$$

а в доказательстве используется теорема Гамильтона-Кэли для этой матрицы.

К примеру, для соотношений
$x_k=x_{k-1} + 2y_{k-1}+20y_{k-2},$
$y_k=3x_{k-1} + 4y_{k-1}$
эта матрица имеет вид:

$$M=\begin{pmatrix} 1 & 2 & 0 & 20 \\ 3 & 4 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}.$$