Решение рекуррентного соотношения

[SergeiSX]

Здравствуйте! При анализе алгоритма с рекурсией получилось следующее рекуррентное соотношение
{C_N} = {C_{N - 1}} + s \cdot {C_{N - k}} где k < N,s < N
Для начала рассматриваю его в предположении что N кратно k. Предварительно вывел из комбинаторных соображений формулу для вычисления количества выполнений рекурсивной процедуры при длине данных N.
k \cdot \left( {{{\left( {\frac{N}{k} - 1} \right)}^s} + {{\left( {\frac{N}{k} - 2} \right)}^s} + \cdots + {2^s} + 1} \right) + s + 1
Потом решил пойти более строгим путем и вывести замкнутое выражение для решения данной рекуррентности через производящие функции. Выполнил стандартную процедуру из четырех этапов и на четвертом этапе получил следующее соотношение для производящей функции:
$G(z) = \frac{{s \cdot z + s \cdot {z^{k - 1}}}}{{1 - z - s \cdot {z^k}}}$
Согласно методу производящих функций для решения рекуррентных соотношений данную замкнутую форму производящей функции необходимо разложить в степенной ряд. Но знаменатель не раскладывается в общем случае на простые множители. Если же представлять данную функцию рядом Тэйлора то при длине данных например 100 или 200 придется брать производную от производящей функции соответствующего порядка что малореально.Подскажите пожалуйста, есть ли какой то иной способ представить данное соотношение G(z) в виде степенного ряда или нужно было использовать какой - либо другой вид производящей функции с самого начала ?

[thething]

SergeiSX
Подстановку ряда в ряд пробовали? Имею ввиду $\frac{1}{1-f(z)}=1+f(z)+f^2(z)+...$ при условии, что $\left\lvert{f(z)}\right\rvert<1$?

[Евгений Машеров]

А через корни уравнения
$x^k-x^{k-1}-s=0$ не получится?

[SergeiSX]

Евгений Машеров, спасибо! Вы имеете в виду деление всего соотношения для производящей функции на $z^k$ и дальнейшую подстановку $x=\frac{1}{z}$? Вопрос в том как дальше искать корни знаменателя. Это возможно сделать в общем виде или необходимо конкретизировать $k$ и $s$? Спасибо я попробую!
thething, спасибо! Вы предлагаете представить производящую функцию в виде соотношения ${\left( s \cdot z + s \cdot z^{k-1} \right)} \cdot \frac{1}{1-\left(z-s \cdot z^k \right)}$ и, затем, представить $\frac{1}{1-\left(z-s \cdot z^k \right)}$ в виде предлагаемого Вами разложения в ряд? Спасибо, надо попробовать!

[thething]

SergeiSX в сообщении #1285413 писал(а):

Вы предлагаете представить производящую функцию в виде соотношения ${\left( s \cdot z + s \cdot z^{k-1} \right)} \cdot \frac{1}{1-\left(z-s \cdot z^k \right)}$

Да, только у Вас опечатка, в скобке в знаменателе надо поставить знак "$+$"

[SergeiSX]

thething в сообщении #1285415 писал(а):

Да, только у Вас опечатка, в скобке в знаменателе надо поставить знак "$+$"

Спасибо! Действительно поспешил! Я попробую обязательно!

[DeBill]

thething в сообщении #1285321 писал(а):

Подстановку ряда в ряд пробовали?

Не, это ровно нас и вернет к исходному рек. уравнению.
И вааще, от характеристического уравнения для исходной задачи - его написал Евгений Машеров
- никуда нам не деться.... Единственно пользу может принести производяшая функция - это получить асимптотику (через радиус сходимости ее разложения в ряд Тейлора, который, как все знают, равен расстоянию от нуля до ближайшего полюса). Но ту же информацию можно извлечь и из хар. многочлена. Дохлый номер, мне кажицца...
SergeiSX
А это, случаем, не случайное блуждание с неравными шагами? Что то - в свое время - ничего путного у меня с этим не вышло

[Евгений Машеров]

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

[SergeiSX]

DeBill в сообщении #1285547 писал(а):

А это, случаем, не случайное блуждание с неравными шагами? Что то - в свое время - ничего путного у меня с этим не вышло

Здравствуйте! Это задача выбора оптимальной топологии разбиения скажем так связного множества квадратиков(связного в смысле наличия пути от каждого квадратика к каждому с помощью только горизонтальных и вертикальных перемещений) в квадратной области на фигуры определенной формы. Оптимальным считается то разбиение которое минимизирует общее количество получившихся фигур(оставшиеся необъединенными квадратики тоже считаются фигурами). Задача решается рекурсивным перебором. Если я правильно понимаю это и есть частный случай блуждания с неравными шагами или я ошибаюсь ?

Евгений Машеров в сообщении #1285650 писал(а):

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

Добрый день! То есть если я правильно понимаю нужно конкретизировать параметры $k$ и $s$ и решать для каждого конкретного случая отдельно ?

[DeBill]

Евгений Машеров в сообщении #1285650 писал(а):

Решение выражается через корни характеристического уравнения. Вот простого выражения для корней мне как-то в голову не приходит.

Ага. Да они плохие, видимо. И искать их придется приближенно.
Но есть эффективный алгоритм нахождения комплексных корней (точнее - максимального по модулю).
Такой (это - смешно): состряпать линейное рекуррентное уравнение именно с таким хар. многочленом. Для - случайного набора начальных значений, считать члены последовательности. Отношение соседних членов довольно быстро сходится к максимальному корню Блин....

[Евгений Машеров]

Теорию разностных уравнений можно найти во многих местах. Есть книги Гельфанда, Романко и др. Решение выражается через степени корней характеристического уравнения с коэффициентами, зависящими от начальных условий. Кратность корней имеет значение.
Красивого решения приведенного уравнения я не вижу, что не означает, что его нет. Подозреваю, что ввиду специального вида тут будет что-то тригонометрическое. Но если нет - надо решать численно, находя все k комплексных корней.

[SergeiSX]

Если комплексные корни будут найдены, то, если я правильно понимаю, дальнейший ряд тоже будет содержать комплексные коэффициенты и, соответственно, результат решения рекуррентного соотношения для некоторого номера $n$ тоже будет комплексный ?

[Евгений Машеров]

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

[SergeiSX]

Спасибо, Евгений Машеров! Начальные параметры действительны. И решать, насколько я понимаю, в общем виде не получится, необходимо конкретизировать $s$ и $k$? Затем решать численно ? А если не численно, какой метод лучше применить ?

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

[Евгений Машеров]

Ну, в общем мне красивого трюка для получения решения уравнения в общем виде придумать не удалось. Доказательство ли это моей глупости, лени или же сложности проблемы - не вем. Возможно, больше посвятив этой задаче, а также глубже изучив задачи такого рода, смог бы что-то придумать, но не уверен. Досужих размышлений на выходных не хватило для решения...
Поскольку с ростом N значение $C_N$ будет определяться максимаьным(и) по модулю корнем(-ями) характеристического уравнения, то можно попытаться поискать лишь его. Почему-то кажется, что тут Греффе-Лобачевский поможет. Или нет...