2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Возвратные последовательности
Сообщение12.05.2013, 00:56 
Аватара пользователя
Добрый вечер!
Дана целочисленная последовательность $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'''$ или для большего числа сомножителей?

 
 
 
 Re: Возвратные последовательности
Сообщение12.05.2013, 04:21 
Если я правильно понимаю, если иксы возвратные, то и любые от их функции тоже будут возвратные, нет?

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

 
 
 
 Re: Возвратные последовательности
Сообщение12.05.2013, 13:40 
Как я понял вы возвратными называете последовательность целых чисел, удовлетворяющихся рекурентному соотношению:
$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$ как возвратная. Для суммы еще проще соответствующий многочлен является произведением характеристических многочленов.

 
 
 
 Re: Возвратные последовательности
Сообщение12.05.2013, 14:33 
Не, ТС, похоже, имеет в виде не постоянные коэффициенты, а отдельную последовательность.

 
 
 
 Re: Возвратные последовательности
Сообщение12.05.2013, 15:16 
Судя по этому
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.$

 
 
 
 Re: Возвратные последовательности
Сообщение12.05.2013, 16:10 
Довольно-таки широкое, это правда. Тем не менее, никак не соберусь проверить формулу, если формула верна, значит, даже при таком широком толковании кое-что сказать про последовательности таки можно.

 
 
 
 Re: Возвратные последовательности
Сообщение12.05.2013, 19:02 
Аватара пользователя
Опять наверное невнятно излагаю. Хочется как лучше, а ... Давайте на примере: берем произвольную последовательность $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$ и т.д.

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

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

 
 
 
 Re: Возвратные последовательности
Сообщение12.05.2013, 20:05 
Аватара пользователя
ewert в сообщении #722951 писал(а):
Для случая постоянных коэффициентов подбор аналогичного уравнения для произведения любого количества последовательностей производится тривиально.

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

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group