Как понизить ранг (глубину) рекуррентного соотношения?

[maximkarimov]

Имеется рекуррентное соотношение A глубиной n. Можно ли ответить на вопрос: существует ли рекуррентное соотношение B глубиной k такое, что A и B соответствует одна и та же числовая последовательность и $k<n$? Если да - как из А получить B?
Например, рекуррентное соотношение A имеет вид:
$a(n)=8a(n-1) - 21a(n-2) +22a(n-3) -8a(n-4)$
Рекуррентное соотношение B по понятным причинам не указываю (оно существует, его глубина равна 2).

[Mihr]

Рекомендую посмотреть: Р. Грэхем, Д. Кнут, О. Паташник - Конкретная математика. Основание информатики. [1998, DjVu], стр. 371-385.

[kotenok gav]

В частных случаях, когда у этого рекуррентного уравнения есть решение в обобщенных гипергеометрических функциях, то поможет алгоритм Hyper из Chapter 8 из A=B.

[novichok2018]

Структура решения всё равно в общем случае мне кажется содержит 4 степени, и порядок рекурсии не уменьшить, не думаю что это возможно и для приведённой последовательности. Но после получения общего вида надо учесть начальные условия и найти неопределённые коэффициенты в общей формуле. Для них получается система линейных уравнений. Если в ней есть нулевые решения, то число членов в представлении решения уменьшается. Поэтому мне кажется, ответ такой: глубину рекурсии можно уменьшить, когда после нахождения общего решения в виде суммы степеней с неопределёнными коэффициентами часть этих неопределённых коэффициентов оказываются нулевыми. К сожалению, для нахождения этих коэффициентов придётся предварительно найти все корни характеристического уравнения.

[nnosipov]

maximkarimov в сообщении #1481017 писал(а):

Имеется рекуррентное соотношение A глубиной n.

Очень неконкретно. О каком классе рекуррентных соотношений идет речь? С постоянными коэффициентами? Однородные? (По крайней мере, в единственном иллюстрирующем примере это так.)

[maximkarimov]

Mihr в сообщении #1481018 писал(а):

Рекомендую посмотреть: Р. Грэхем, Д. Кнут, О. Паташник - Конкретная математика. Основание информатики. [1998, DjVu], стр. 371-385.

Ознакомился, спасибо.
Там описывается получение явной формулы методом производящих функций. Его применение к рекуррентному соотношению A глубиной 4, которое я привел выше в качестве примера, и к рекуррентному соотношению B глубиной 2, которое я не привел, дает одну и ту же формулу. Однако обнаружить там ответ мне не удалось - может я что-то упустил? На всякий случай повторюсь: дано рекуррентное соотношение глубиной четыре - нужно узнать есть ли для той же последовательности другое рекуррентное соотношение, глубина которого меньше и, если есть, получить его (речь о получении явной формулы не идет).

-- 28.08.2020, 12:12 --

nnosipov в сообщении #1481071 писал(а):

maximkarimov в сообщении #1481017 писал(а):

Имеется рекуррентное соотношение A глубиной n.

Очень неконкретно. О каком классе рекуррентных соотношений идет речь? С постоянными коэффициентами? Однородные? (По крайней мере, в единственном иллюстрирующем примере это так.)

Да, Вы совершенно правы. Уточняю:
A - линейное, однородное, с постоянными коэффициентами, B - любое меньшей глубины.

-- 28.08.2020, 12:26 --

novichok2018 в сообщении #1481066 писал(а):

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

Для рекуррентного соотношения A, которое приведено в качестве примера, коэффициенты найти не сложно.
Среди них нет нулевых, однако B глубиной 2 существует.

[Mihr]

maximkarimov в сообщении #1481086 писал(а):

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

Да, извините за невнимательность. Вам требовалось именно понизить глубину рекуррентного соотношения, но не уменьшать её до нуля. Тогда моя ссылка малополезна.

[mihaild]

Я чего-то не понимаю в формулировке. Можно привести разные последовательности, удовлетворяющие соотношению А, у которых совпадают первые два члена. Как эти последовательности могут удовлетворять одному и тому же соотношению глубины $2$?

[maximkarimov]

Какие брать начальные члены для А - значения не имеет.
Например, пусть будет $a=[1, 2, 6, 23]$. Соответствующую последовательность обозначим S(A,a). Размер a (глубину A) обозначим n (в данном, конкретном случае $n=4$).
Вопрос: существует ли рекуррентное соотношение B с вектором начальных членов b, размер которого равен k, такое, что $S(A,a)=S(B,b)$ и $k<n$?
P.S. Случай k=0 (явную формулу) не рассматриваем.

[svv]

Сформулирую вопрос mihaild по-другому, более подробно. Он весьма уместен.

У нас есть рекуррентное соотношение 4 порядка. Ему удовлетворяет множество последовательностей. Чтобы из этого множества выбрать одну конкретную, надо задать четыре начальных члена (скажем, $a_1,a_2,a_3,a_4$). Задания двух первых членов ($a_1,a_2$), очевидно, недостаточно, потому что существуют две последовательности (на самом деле, очень много), у которых первые два члена совпадают, а третий и четвёртый отличаются.

Если так, каким образом данное рекуррентное соотношение можно свести к более короткому, 2 порядка? Ведь если оно существует, первых двух членов $a_1,a_2$ будет достаточно для однозначного построения последовательности. (Можно даже сказать, при заданных $a_1,a_2$ последовательность помимо нашей воли будет продолжена однозначно.) Но мы только что видели, что для исходного соотношения 4 порядка при заданных $a_1,a_2$ существует бездна различных вариантов продолжения, различающихся членами $a_3,a_4$.

[maximkarimov]

Начальные члены A значения не имеют (подробнее см. выше).
Но уточнение mihaild и svv действительно важно - вопрос о существовании и получении B имеет смысл только с заданными начальными членами для А. Ну что ж - выше я их привел (в качестве примера).

[svv]

Ещё по-другому.
Предположим, что из соотношения 4 порядка можно получить соотношение 2 порядка без дополнительной информации. Тогда, пользуясь последним, можно по $a_1,a_2$ получить $a_3$. Но это противоречит независимости $a_3$ от $a_1,a_2$ при исходном соотношении 4 порядка.

Для конкретной последовательности, естественно, порядок можно уменьшить.

[maximkarimov]

Спасибо. Выше уточнил - для получения B берем A вместе с заданными начальными членами.

-- 28.08.2020, 15:23 --

svv в сообщении #1481119 писал(а):

Для конкретной последовательности, естественно, порядок можно уменьшить.

Всегда? Глубину рекуррентного соотношения Фибоначчи можно понизить до 1?
P.S. Случай уменьшения глубины до 0 (явную формулу) не рассматриваем.

[mihaild]

maximkarimov в сообщении #1481122 писал(а):

Всегда?

Если разрешена последовательность любого вида - то да. Ограничение на глубину снизу смысла не имеет.
Пусть у нас есть задание $B(n) = f(n)$ - глубина $0$. Тогда можно его переписать с глубиной $1$: $B(n) = B(n - 1) + (f(n) - f(n - 1))$. И аналогично с любой другой глубиной.

[kotenok gav]

mihaild в сообщении #1481124 писал(а):

Пусть у нас есть задание $B(n) = f(n)$ - глубина $0$. Тогда можно его переписать с глубиной $1$: $B(n) = B(n - 1) + (f(n) - f(n - 1))$. И аналогично с любой другой глубиной.

Так maximkarimov хочет глубину не увеличить, а уменьшить до конкретного числа.