2014 dxdy logo

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

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



Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 18:58 


25/01/15
7
Всем доброго времени суток!
Не подскажите, как доказать, что множество линейных рекуррентных последовательностей замкнуто относительно сложения.

 Профиль  
                  
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 19:14 
Заслуженный участник


16/02/13
2812
Владивосток
Ну, вообще-то надо взять две рекуррентных последовательности, сложить и попробовать составить рекуррентную же формулу.
Попробуйте посмотреть на характеристические многочлены. Возьмите для примера пару ких-нить. Например, ряд Фибоначчи и его же ряд с другими начальными членами.

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


18/01/13
11122
Казань
А можно спросить: каково точное определение рекуррентных последовательностей? Ясно, что $a_{n+k}=f(a_{n}, a_{n+1}, ..., a_{n+k-1})$. Но каковы ограничения на вид функции $f$?

 Профиль  
                  
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 20:04 


25/01/15
7
Под линейной рекуррентной последовательностью я подразумевал
${x_n} = {a_1}{x_{n - 1}} + {a_2}{x_{n - 2}} + ... + {a_k}{x_{n - k}}$
Пытался складывать в общем виде две такие последовательности, и как раз выразить рекуррентную формулу для суммы не получилось.

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


18/01/13
11122
Казань
Надеюсь, что решение не сводится к использованию явного вида общего члена. Но сам он на некоторые мысли наводит.
Например, рассмотрим простейший случай: две геометрические прогрессии $x_n=2x_{n-1}$ и $y_n=3y_{n-1}$, то есть $x_n=x_0\cdot2^n, y_n=y_0\cdot3^n$. Их сумма не будет записываться рекуррентным соотношением первого порядка, а только второго.

Кстати какого именно?

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


13/12/05
3467
Kozyrr
Может быть надо надо доказать, что множество последовательностей, являющихся решением некоторого (фиксированного) линейного рекуррентного уравнения замкнуто относительно сложения? Это просто.
Или $x_n$ удовлетворяет одному уравнению, $y_n$ -- другому, и надо найти уравнение, которому удовлетворяет последовательность $z_n=x_n+y_n$?

 Профиль  
                  
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 20:41 


25/01/15
7
Задание звучит так: пусть ${a_1},{a_2},...,{a_k}$ - некоторые числа. Докажите, что множество числовых последовательностей, удовлетворяющих рекуррентному соотношению
${x_n} = {a_1}{x_{n - 1}} + {a_2}{x_{n - 2}} + ... + {a_k}{x_{n - k}}$
замкнуто относительно сложения.

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


18/01/13
11122
Казань
Padawan в сообщении #968206 писал(а):
$x_n$ удовлетворяет одному уравнению, $y_n$ -- другому, и надо найти уравнение, которому удовлетворяет последовательность $z_n=x_n+y_n$?
Скорее, доказать, что такое уравнение существует. Но если предъявить, то, конечно, еще лучше.
Сильно подозреваю, что тут нужно использовать характеристические уравнения.

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


13/12/05
3467
Kozyrr
Так я и думал :) Запишите аналогичное для $y_n$, потом запишите аналогичное уравнение для $z_n$, и подставьте в него $z_n=x_n+y_n$. Подумайте, почему оно будет верно.

 Профиль  
                  
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 20:45 
Заслуженный участник


11/05/08
31100
Kozyrr в сообщении #968216 писал(а):
Докажите, что множество числовых последовательностей, удовлетворяющих рекуррентному соотношению
${x_n} = {a_1}{x_{n - 1}} + {a_2}{x_{n - 2}} + ... + {a_k}{x_{n - k}}$
замкнуто относительно сложения.

Лучше б спросили честно: "доказать, что образует линейное пространство".

Это тривиально. Достаточно записать параллельно две строчки и сложить их.

 Профиль  
                  
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 20:49 
Заморожен


20/12/10
5623
provincialka в сообщении #968219 писал(а):
Сильно подозреваю, что тут нужно использовать характеристические уравнения.
Да нет, можно без них обойтись.

 Профиль  
                  
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 21:03 


25/01/15
7
Padawan
Я догнал, спасибо.
ewert
Остальные св-ва для линейного подпространства я доказал, поэтому решил сюда не писать о них.

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


18/01/13
11122
Казань
А! Ну, эта задача совсем простая. Я-то думала, уравнения произвольные. Интересно, а для произвольных уравнений есть такое свойство?

 Профиль  
                  
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 21:11 


25/01/15
7
provincialka
Я весь день как раз и думал, что "уравнения произвольные" :facepalm:
Надо мне в следующий раз лучше задание читать.

 Профиль  
                  
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 21:14 
Заслуженный участник


11/05/08
31100
provincialka в сообщении #968248 писал(а):
Интересно, а для произвольных уравнений есть такое свойство?

Естественно. Хотя бы просто потому, что сумма геометрических прогрессий (возможно, умноженных на многочлены) есть тоже нечто аналогичное.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу 1, 2  След.

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



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

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


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

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