2014 dxdy logo

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

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




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

 
 
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 19:14 
Ну, вообще-то надо взять две рекуррентных последовательности, сложить и попробовать составить рекуррентную же формулу.
Попробуйте посмотреть на характеристические многочлены. Возьмите для примера пару ких-нить. Например, ряд Фибоначчи и его же ряд с другими начальными членами.

 
 
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 19:20 
Аватара пользователя
А можно спросить: каково точное определение рекуррентных последовательностей? Ясно, что $a_{n+k}=f(a_{n}, a_{n+1}, ..., a_{n+k-1})$. Но каковы ограничения на вид функции $f$?

 
 
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 20:04 
Под линейной рекуррентной последовательностью я подразумевал
${x_n} = {a_1}{x_{n - 1}} + {a_2}{x_{n - 2}} + ... + {a_k}{x_{n - k}}$
Пытался складывать в общем виде две такие последовательности, и как раз выразить рекуррентную формулу для суммы не получилось.

 
 
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 20:13 
Аватара пользователя
Надеюсь, что решение не сводится к использованию явного вида общего члена. Но сам он на некоторые мысли наводит.
Например, рассмотрим простейший случай: две геометрические прогрессии $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 
Kozyrr
Может быть надо надо доказать, что множество последовательностей, являющихся решением некоторого (фиксированного) линейного рекуррентного уравнения замкнуто относительно сложения? Это просто.
Или $x_n$ удовлетворяет одному уравнению, $y_n$ -- другому, и надо найти уравнение, которому удовлетворяет последовательность $z_n=x_n+y_n$?

 
 
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 20:41 
Задание звучит так: пусть ${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 
Аватара пользователя
Padawan в сообщении #968206 писал(а):
$x_n$ удовлетворяет одному уравнению, $y_n$ -- другому, и надо найти уравнение, которому удовлетворяет последовательность $z_n=x_n+y_n$?
Скорее, доказать, что такое уравнение существует. Но если предъявить, то, конечно, еще лучше.
Сильно подозреваю, что тут нужно использовать характеристические уравнения.

 
 
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 20:45 
Kozyrr
Так я и думал :) Запишите аналогичное для $y_n$, потом запишите аналогичное уравнение для $z_n$, и подставьте в него $z_n=x_n+y_n$. Подумайте, почему оно будет верно.

 
 
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 20:45 
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 
provincialka в сообщении #968219 писал(а):
Сильно подозреваю, что тут нужно использовать характеристические уравнения.
Да нет, можно без них обойтись.

 
 
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 21:03 
Padawan
Я догнал, спасибо.
ewert
Остальные св-ва для линейного подпространства я доказал, поэтому решил сюда не писать о них.

 
 
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 21:05 
Аватара пользователя
А! Ну, эта задача совсем простая. Я-то думала, уравнения произвольные. Интересно, а для произвольных уравнений есть такое свойство?

 
 
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 21:11 
provincialka
Я весь день как раз и думал, что "уравнения произвольные" :facepalm:
Надо мне в следующий раз лучше задание читать.

 
 
 
 Re: Замкнутость линейных рекуррентных последовательностей
Сообщение25.01.2015, 21:14 
provincialka в сообщении #968248 писал(а):
Интересно, а для произвольных уравнений есть такое свойство?

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

 
 
 [ Сообщений: 22 ]  На страницу 1, 2  След.


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