2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Возвратные последовательности
Сообщение12.05.2013, 00:56 
Заслуженный участник
Аватара пользователя


21/11/12
1967
Санкт-Петербург
Добрый вечер!
Дана целочисленная последовательность $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 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Возвратные последовательности
Сообщение12.05.2013, 08:31 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Возвратные последовательности
Сообщение12.05.2013, 13:40 
Заслуженный участник


09/02/06
4397
Москва
Как я понял вы возвратными называете последовательность целых чисел, удовлетворяющихся рекурентному соотношению:
$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 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Возвратные последовательности
Сообщение12.05.2013, 15:16 
Заслуженный участник


09/02/06
4397
Москва
Судя по этому
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 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Возвратные последовательности
Сообщение12.05.2013, 19:02 
Заслуженный участник
Аватара пользователя


21/11/12
1967
Санкт-Петербург
Опять наверное невнятно излагаю. Хочется как лучше, а ... Давайте на примере: берем произвольную последовательность $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 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Возвратные последовательности
Сообщение12.05.2013, 20:05 
Заслуженный участник
Аватара пользователя


21/11/12
1967
Санкт-Петербург
ewert в сообщении #722951 писал(а):
Для случая постоянных коэффициентов подбор аналогичного уравнения для произведения любого количества последовательностей производится тривиально.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group