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

[Andrey A]

Добрый вечер!
Дана целочисленная последовательность $a_1,a_2,...,a_n$. Не равные последовательности $x_n',x_n'',x_n''',...$ объединены рекуррентным правилом $x_{n+1}=a_{n+1}x_n+x_{n-1}$. Ясно, что суммарная последовательность $x_n'+x_n''+x_n'''+...$ подчинена тому же правилу, но оказывается что $y_n=x_n'x_n''$ - тоже возвратная последовательность:
$y_{n+1}=\frac{a_{n+1}}{a_n}(a_na_{n+1}+1)y_n+(a_na_{n+1}+1)y_{n-1}-\frac{a_{n+1}}{a_n}y_{n-2}$.
Существует ли подобное правило для $Y_n=x_n'x_n''x_n'''$ или для большего числа сомножителей?

[iifat]

Если я правильно понимаю, если иксы возвратные, то и любые от их функции тоже будут возвратные, нет?

[Andrey A]

Если бы да, то все последовательности были бы возвратные, как функции от натурального ряда (натуральный ряд - возвратная: $x_{n+1}=2x_n-x_{n-1}$).
С другой стороны из примеров невозвратных, приводимых Маркушевичем, единственная целочисленная - последовательность простых.

[Руст]

Как я понял вы возвратными называете последовательность целых чисел, удовлетворяющихся рекурентному соотношению:
$y_n=a_1y_{n-1}+a_2y_{n-2}+...+a_ky_{n-k}, a_i\in Z$.
Они однозначно оапеделяются характеристическим многочленом $f(x)=x^k-a_1x^{k-1}-...-a_k=\prod_{i=1}^k (x-\alpha_k)$ и начальными данными $y_0,...,y_{k-1}$.
Если имеются две возвратные поcледовательности $y_n, z_n$ с корнями $\alha_i, i=1,...,k$ и $\beta_1,...,\beta_m$, то последовательности $y_nz_n$ соответстывуют
корни $\alpha_i+\beta_j$ они так же алгебраический целые, т.е. существует характеристический многочлен с целыми коэффициентами со старшим коэффициентом 1, корнями которой являются эти числа. По начальным данным определяется полностью последовательность $t_n=y_nz_n$ как возвратная. Для суммы еще проще соответствующий многочлен является произведением характеристических многочленов.

[iifat]

Не, ТС, похоже, имеет в виде не постоянные коэффициенты, а отдельную последовательность.

[Руст]

Судя по этому

Andrey A в сообщении #722650 писал(а):

$y_{n+1}=\frac{a_{n+1}}{a_n}(a_na_{n+1}+1)y_n+(a_na_{n+1}+1)y_{n-1}-\frac{a_{n+1}}{a_n}y_{n-2}$.

получается слишком щирокое толкование для этих последовательностей:
$y_n=a_{1n}y_{n-1}+a_{2n}y_{n-2}+...+a_{kn}y_{n-k}, a_{in}\in Q.$
Так с непостоянными (к тому же рациональными) $a_{in}$ можно любую целочисленную последовательность можно так представить
$y_{n+1}=a_{n+1}y_n+y_{n-1}$ определив $a_{n+1}=\frac{y_{n+1}-y_{n-1}}{y_n}\in Q.$

[iifat]

Довольно-таки широкое, это правда. Тем не менее, никак не соберусь проверить формулу, если формула верна, значит, даже при таком широком толковании кое-что сказать про последовательности таки можно.

[Andrey A]

Опять наверное невнятно излагаю. Хочется как лучше, а ... Давайте на примере: берем произвольную последовательность $a_n=1,3,2,4,1,7,5,2,9,...$ и пары первых членов последовательностей $x'=2,3$ и $x''=1,4$ (тоже произвольные, но лучше вз. простые). Тогда
$x_3'=a_3x_2'+x_1'=2\cdot 3+2=8$
$x_4'=a_4x_3'+x_2'=4\cdot 8+3=35$ и т.д.
Получаем две последовательности
$x'=2,3,8,35,43,336,1723,3782,35761,...$ и
$x''=1,4,9,40,49,383,1964,4311,40763,...$
Тогда $y_1=x_1'\cdot x_1''=2\cdot 1=2;\ y_2=3\cdot 4=12;\ y_3=8\cdot 9=72$
$y_n=2,12,72,...$ Вопрос: можно ли получить остальные члены последовательности $y_n$ напрямую, как функцию от $a_n$? Вот эта задача решена: ${\tiny y_4=\frac{a_4}{a_3}(a_4a_3+1)y_3+(a_4a_3+1)y_2-\frac{a_4}{a_3}y_1= \frac{4}{2}(4\cdot 2+1)\cdot 72+(4\cdot 2+1)\cdot 12-\frac{4}{2}\cdot 2=1400=35\cdot 40}$
$y_5=\frac{1}{4}(1\cdot 4+1)\cdot 1400+(1\cdot 4+1)\cdot 72-\frac{1}{4}\cdot 12=2107=43\cdot 49$ и т.д.

Действительно, понятие "возвратная последовательность" трактуется шире. Но я думаю, это позволительно т.к. общепринятое понятие оказывается частным случаем. Последовательность произведений пар Фибоначчи с постоянной разностью номеров, во всяком случае, получить отсюда легко. А вот для троек Фибоначчи надо решить аналогичную задачу для трех множителей, и тут уперся.

[ewert]

Последовательность Фибоначчи -- это решение разностного уравнения с постоянными коэффициентами. Для случая постоянных коэффициентов подбор аналогичного уравнения для произведения любого количества последовательностей производится тривиально. Каждая такая последовательность есть некая линейная комбинация геометрических прогрессий (возможно, умноженных на многочлен от номера). Надо тупо перемножить эти комбинации, раскрыть скобки, по полученному набору прогрессий и многочленов определить корни характеристического уравнения и их кратности и потом по характеристическому уравнению восстановить разностное.

[Andrey A]

ewert в сообщении #722951 писал(а):

Для случая постоянных коэффициентов подбор аналогичного уравнения для произведения любого количества последовательностей производится тривиально.

Ну, тройки Фибоначчи не были целью, это просто для примера взято. Вопрос-то в начале.