Задача из теории рекурсии

[nbyte]

Здравствуйте.
Готовлюсь к экзамену и некак немогу понять как решать следующие задачи.
К примеру вот такая задача
Найти рекурсивную функцию $\[{{\rm{z}}_{\rm{n}}},{\rm{ }}0 \le {\rm{n}}\]$, если

$$\[{{\rm{z}}_{{\rm{n}} + {\rm{4}}}} = {\rm{ 4}}{{\rm{z}}_{{\rm{n}} + {\rm{3}}}} - {\rm{ 16}}{{\rm{z}}_{{\rm{n}} + {\rm{1}}}} + {\rm{16}}{{\rm{z}}_{\rm{n}}},{\rm{ }}{{\rm{z}}_{\rm{0}}} = {\rm{ }}{{\rm{z}}_{\rm{1}}} = {\rm{ 1}},{\rm{ }}{{\rm{z}}_{\rm{2}}} = {\rm{ }}{{\rm{z}}_{\rm{3}}} = {\rm{ 2}}\] $$

Помогите пожалуйста понять, как тут составить характеристический многочлен?

[vlad239]

Допустим, что последовательность $a^n$ годится (только в уравнение, про начальные условия пока не думаем). Какому условию должно удовлетворять $a$?

Влад.

[ewert]

кстати, а как потом решать уравнение четвёртой степени? чего-то коэффициенты подозрительные...

[nbyte]

Цитата:

чего-то коэффициенты подозрительные...

Я нашел похожие задачи только в книге Джеймс Андерсон - Дискретная математика и комбинаторика, но там только со 2 степенью вроде есть.
А именно такие нигде не нашел, поэтому тут и пишу.

Цитата:

Допустим, что последовательность $a^n$ годится (только в уравнение, про начальные условия пока не думаем). Какому условию должно удовлетворять $a$?

Незнаю

[vlad239]

А подставить в уравнение слабо?

Влад.

[nbyte]

А что куда?

[ewert]

$a^n$ в уравнение. Потом сократить на его же.

[nbyte]

Не пардон, непонимаю.

[ewert]

А вы подставьте, подставьте. Потом уж будете думать -- понимаете или нет.

[Утундрий]

nbyte в сообщении #224625 писал(а):

Здравствуйте.
Готовлюсь к экзамену и некак немогу понять как решать следующие задачи.
К примеру вот такая задача
Найти рекурсивную функцию $\[{{\rm{z}}_{\rm{n}}},{\rm{ }}0 \le {\rm{n}}\]$, если

$$\[{{\rm{z}}_{{\rm{n}} + {\rm{4}}}} = {\rm{ 4}}{{\rm{z}}_{{\rm{n}} + {\rm{3}}}} - {\rm{ 16}}{{\rm{z}}_{{\rm{n}} + {\rm{1}}}} + {\rm{16}}{{\rm{z}}_{\rm{n}}},{\rm{ }}{{\rm{z}}_{\rm{0}}} = {\rm{ }}{{\rm{z}}_{\rm{1}}} = {\rm{ 1}},{\rm{ }}{{\rm{z}}_{\rm{2}}} = {\rm{ }}{{\rm{z}}_{\rm{3}}} = {\rm{ 2}}\] $$

Помогите пожалуйста понять, как тут составить характеристический многочлен?

Подобные задачи решаются однотипно введением функции $\[f(x) \equiv \sum\limits_{n = 0}^\infty {z_n \cdot x^n } \]$. Умножьте теперь свое рекуррентное соотношение на $\[x^{n + 4} \]$ и просуммируйте от $0$ до $\infty$. Вынесите кое-где за скобки иксы в должных степенях, выразите усеченные суммы через полную функцию $f$ и получите относительно нее элементарное линейное уравнение. После чего искомые $\[{z_n }\]$ даются разложением $f$ в ряд Маклорена.

[ewert]

Господи, какой кошмар. Какие ряды?...

Хотя я, кажется, понял, в чём проблемы у автора. Он, видимо, просто не догадывается, что надо подставлять $z_n=a^n$. Т.е. что надо брать $a^n$ именно в качестве $z_n$.

[Утундрий]

А должен? Вообще говоря, это не угадывается, а выводится - причем именно из "кошмара". То, что решение будет сумой степеней, как-бы не очевидно.

[nbyte]

Цитата:

Т.е. что надо брать $a^n$ именно в качестве $z_n$.

Допустим тогда

$$\[{a^{n + 4}} = 4{a^{n + 3}} - 16{a^{n + 1}} + 16{a^n}\]$$

И как тогда дальше?

[Утундрий]

...сокращаем на $a^n$...

[ewert]

Утундрий в сообщении #224650 писал(а):

То, что решение будет сумой степеней, как-бы не очевидно.

Очевидно, если подходить к делу систематически (а у них, надо полагать, так и было, раз уж зашёл разговор о разностных уравнениях). Имеем дело с линейным однородным
уравнением, размерность пространства решений заведомо равна равно четырём. Стало быть, надо только подобрать базис. Ну и т.д., ровно по той же схеме, что и в аналогичной теории дифференциальных уравнений.