Поиск рекуррентного соотношения для цел-ч последовательности

[maximkarimov]

В ходе изучения классов эквивалентности на множестве состояний объекта X, получена целочисленная последовательность:
0, 1, 2, 2, 3, 3, 5, 4, 7, 6, 11, 9, 17, 14, 25, 21...
Как найти для нее рекуррентное соотношение - какова техника, методы поиска? Где об этом можно почитать?
Замечания:
1. Вопрос именно о способах поиска рекуррентного соотношения для заданной последовательности, а не о методах его решения.
2. Указанная выше последовательность может быть продолжена бесконечно: все ее четные члены представляют собой целочисленную последовательность A002379, нечетные - А212464.

[Sender]

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

[maximkarimov]

Sender в сообщении #1435994 писал(а):

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

Коэффициенты должны быть целыми? Если нет - как перебрать все допустимые наборы коэффициентов?

[Sender]

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

Если нет - как перебрать все допустимые наборы коэффициентов?

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

[=SSN=]

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

Как найти для нее рекуррентное соотношение - какова техника, методы поиска? Где об этом можно почитать?

Алгоритм Берлекэмпа — Мэсси?

[arseniiv]

Если ТС ничего не путал, то очевидно следует использовать очень сильное утверждение

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

Указанная выше последовательность может быть продолжена бесконечно: все ее четные члены представляют собой целочисленную последовательность A002379, нечетные - A212464.

(я бы только сказал, что ноль туда не вписывается, но если заменить единицей, то да; теги oeis для удобства в цитате добавил).

Если у нас есть рекуррентные формулы для той и этой, то простым способом получится и формула для последовательности, полученной их перемежением: если $a(n) = A(a, n)$, $b(n) = B(b, n)$, где $A(a, n), B(b, n)$ — какие-то выражения, поминающие соответственно $a$ и $b$ от каких-то связанных с $n$ аргументов, и $c(n) = ((n+1)\bmod2)a(\frac{n+1}2) + (n\bmod2)b(\frac n2)$, то $c(n) = ((n+1)\bmod2) A(c, 2n) + (n\bmod2) B(c, 2n)$. Основную проблему представляет найти выражения $A, B$.

(Или ТС неправ и его последовательность может оказаться проще. Вообще подозрительное конечно описание, если вот честно.)

-- Пн янв 20, 2020 03:51:59 --

Хотя иногда зависимость от $n$ напрямую в рекуррентной формуле не допускают. Ну тогда всё просто ещё хуже.

[maximkarimov]

=SSN= в сообщении #1436005 писал(а):

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

Как найти для нее рекуррентное соотношение - какова техника, методы поиска? Где об этом можно почитать?

Алгоритм Берлекэмпа — Мэсси?

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