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

[mihaild]

kotenok gav в сообщении #1481126 писал(а):

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

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

[maximkarimov]

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

Ограничение на глубину снизу смысла не имеет.

Два рекуррентных соотношения разной глубины дают одну и ту же явную формулу, но ни одно из таких соотношений не является "переписанной" явной формулой, не является квази-рекуррентным соотношением. В некоторых случаях это имеет значение.

[mihaild]

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

но ни одно из соотношений не является "переписанной" явной формулой

Я не думаю, что вы это сможете формализовать.

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

не является квази-рекуррентным соотношением

А это что такое?

Рассмотрим три семейства рекуррентных соотношения ($c$ и $d$ - константы):
1) $a_n = 3 a_{n - 1} - 2 a_{n - 2}$, глубина $2$
2) $a_n = c + d \cdot 2^n$, глубина $0$
3) $a_n = a_{n - 1} + d \cdot 2^{n - 1}$, глубина $1$
Им удовлетворяют одни и те же последовательности. Третье является "переписанной явной формулой", или нет?

[maximkarimov]

Позволю себе ответить вопросом на вопрос - как по Вашему выглядит рекуррентное соотношение B глубиной 2 в приведенном мною примере?

[mihaild]

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

как по Вашему выглядит рекуррентное соотношение B глубиной 2 в приведенном мною примере?

В угадайку играть не буду принципиально.
Вы задали вопрос, вам и отвечать на уточняющие вопросы.

[maximkarimov]

"Легким движением руки" явную формулу превращаем в рекуррентное соотношение любой глубины!
Я Вас правильно понял?

[mihaild]

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

"Легким движением руки" явную формулу превращаем в рекуррентное соотношение любой глубины!

Да, именно так. Поэтому искать формулу какой-то конкретной глубины без ограничения на вид формулы - бессмысленно.

[maximkarimov]

Ммм... Ограничения какого вида Вы имеете ввиду?

[mihaild]

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

Ограничения какого вида Вы имеете ввиду?

Да какие угодно. Например можно потребовать, чтобы рекуррентное выражение было линейным / однородным / с постоянными коэффициентами / еще каким-то.

[maximkarimov]

Вы правы. Уточняю ограничения на B - линейное, с постоянными коэффициентами.

[mihaild]

Т.е. вида $a_n = x_1 a^{n - 1} + \ldots + x_k a^{n - k}$? Для формулы из первого поста и большинства начальных членов (например для $3, 8, 23, 277$ - общая формула получится $a_n = 1 + n + 2^n + 4^n$) получающаяся последовательность такой формулой глубины меньше $4$ не задается.

[svv]

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

Уточняю ограничения на B - линейное, с постоянными коэффициентами.

... но, возможно, неоднородное.

[maximkarimov]

svv - верно.

[svv]

Пусть $S$ — оператор сдвига последовательности $(a_n)$ на один элемент влево, т.е. $(b_n)=S(a_n)$ означает $\forall n, b_n=a_{n+1}$.
Тогда исходное рекуррентное соотношение можно записать в операторной форме так:
$(S-4)(S-2)(S-1)(S-1)(a_n)=(0)$
Общее решение $a_n=A\cdot 4^n+B\cdot 2^n+C\cdot 1^n+D\cdot 1^n n$, где $A,B,C,D$ — произвольные константы.

Вычеркнем из оператора один множитель, например, $S-2$, и подействуем полученным оператором на общее решение. Ясно, что выживет (и преобразуется) только второе слагаемое:
$(S-4)(S-1)^2\;(a_n)=(S-4)(S-1)^2\;(B\cdot 2^n)=(-B\cdot 2^{n+1})$
Если $B$ известно, подставим его сюда и получим неоднородное рекуррентное соотношение 3 порядка.

[maximkarimov]

То есть B существует всегда, причем для всех $0<k<n$ и Вы обозначили, вообще говоря, путь для получения конкретного B?
P.S. Под B я подразумеваю искомое рекуррентное соотношение, а не коэффициент, для обозначения которого Вы использовали тот же символ (B).