Замкнутость линейных рекуррентных последовательностей

[Kozyrr]

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

[iifat]

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

[provincialka]

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

[Kozyrr]

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

[provincialka]

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

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

[Padawan]

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

[Kozyrr]

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

[provincialka]

Padawan в сообщении #968206 писал(а):

$x_n$ удовлетворяет одному уравнению, $y_n$ -- другому, и надо найти уравнение, которому удовлетворяет последовательность $z_n=x_n+y_n$?

Скорее, доказать, что такое уравнение существует. Но если предъявить, то, конечно, еще лучше.
Сильно подозреваю, что тут нужно использовать характеристические уравнения.

[Padawan]

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

[ewert]

Kozyrr в сообщении #968216 писал(а):

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

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

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

[nnosipov]

provincialka в сообщении #968219 писал(а):

Сильно подозреваю, что тут нужно использовать характеристические уравнения.

Да нет, можно без них обойтись.

[Kozyrr]

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

[provincialka]

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

[Kozyrr]

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

[ewert]

provincialka в сообщении #968248 писал(а):

Интересно, а для произвольных уравнений есть такое свойство?

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