две рекуррентности

[maxal]

Докажите, что следующие две рекуррентные формулы:

$$a_{n+4} = \frac{(2 n^2 + 4 n + 2) a_n - (5 n^2 + 13 n + 8) a_{n+1} + (111 n^2 + 438 n + 417) a_{n+2} + (55 n^2 + 389 n + 685) a_{n+3}}{n^2 + 8 n + 16}$$

и

$$a_{n+3} = \frac{(8 + 19 n + 14 n^2 + 3 n^3 ) a_n - (54 + 92 n + 51 n^2 + 9 n^3) a_{n+1} + (1771 + 2488 n + 1140 n^2 + 171 n^3) a_{n+2}}{45 + 57 n + 23 n^2 + 3 n^3}$$

при соответствующих начальных значениях порождают одну и ту же последовательность:

$$a_0=1,\ a_1=13,\ a_2=409,\ a_3=16081,\ a_4=699121,\ a_5=32193253,\ \dots$$

[Руст]

Способ проверки имеется и он логиеский прост. Однако, формулы пугающе сложные, чтобы без ошибки их проверять.
Проверил. Действительно совпадают. Первое уравнение умноженное на (3n+8) есть линейная комбинация второго, записанного для a(n+4) и для a(n+3). Только отсюда никак не получается целочисленность последовательности. Если эта последовательность действительно целочисленная, то должна существовать ещё более короткое рекурентное целочисленное соотношение без знаменателей. Правда такое соотношение имеет место не для всяких начальных условий.

[Руст]

Довольно любопытная последовательность. Хотел получит более короткое рекурентное соотношение, получается иррациональные коэффициенты. Конечно целочисленность можно доказать и без этого.
Откуда появилась такая последовательность?

[maxal]

А какие коэффициенты в линейной комбинации?

Кстати, вопрос о целочисленности тоже интересный. Докажите, что рассматриваемая последовательность целочисленна.

[RIP]

maxal
Всё-таки интересно.

Руст писал(а):

Откуда появилась такая последовательность?

[maxal]

Чуть позже отвечу (чтобы не испортить задачу).

[RIP]

Насколько я знаю, целочисленность подобных последовательностей получается через предъявление явной формулы для $a_n$, откуда целочисленность становится очевидной (см., например, док-во Апери иррациональности $\zeta(3)$).
maxal, Вы умеете доказывать целочисленность?

[Руст]

Явное решение получается в виде:
$a_n=f_1(n)x_1^n+f_2(n)x_2^n+f_3(n)x_3^n$
где f1,f2,f3 целочисленные полиномы, x1,x2,х3 корни уравнения
$x^3-57x^2+3x-1=0$,
т.е. целые алгебраические числа.

[worm2]

RIP писал(а):

maxal
Всё-таки интересно.

Руст писал(а):

Откуда появилась такая последовательность?

Это очень простой вопрос.
На него можно ответить, даже не решая задачу.

[RIP]

Руст писал(а):

Явное решение получается в виде:
$a_n=f_1(n)x_1^n+f_2(n)x_2^n+f_3(n)x_3^n$
где f1,f2,f3 целочисленные полиномы, x1,x2,х3 корни уравнения
$x^3-57x^2+3x-1=0$,
т.е. целые алгебраические числа.

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

[Руст]

Да. Я так же пришёл к такому выводу. Точнее если представляется в таком виде, то многочлен, точнее ряд лорана степени -1, т.е $a_n=\sum_x \sum_{k=1}\frac{t_kx^n}{(n+c)^k}$. х - корни вышеприведённого характеристического уравнения, а $c=\frac{37x^2-5x+4}{9(19x^2-2x+1)}$ (конечно можно было избавиться от знаменателя, учитывая, что х корень соответствующего кубического уравнения). Только не проверил, обрывается суммирование конечным числом или нет. По идее можно сумма по к обрывается и не более 3 членов. Во всяком случае, эта формула даёт поведение при больших n.

[RIP]

Явную формулу надо искать в виде

$$a_n=\sum_{k=-\infty}^{\infty}a_{nk},$$

где $a_{nk}$ - целые числа (обычно это произведение каких-нибудь биномиальных коэффициентов). $a_{nk}$ надо подбирать с таким расчётом, чтобы можно было написать

$$(3n^3+23n^2+57n+45)a_{n+3,k}-(171n^3+1140n^2+2488n+1771)a_{n+2,k}+$$

$$+(9n^3+51n^2+92n+54)a_{n+1,k}+(3n^3+14n^2+19n+8)a_{nk}=A_{n,k+1}-A_{nk},$$

т.е. по $k$ можно явно просуммировать.
Если явная формула найдена, то существует алгоритм, позволяющий находить $A_{nk}$ (Gosper summation algorithm). Вся проблема в том, чтобы найти эту формулу (возможно, существует алгоритм, позволяющий находить её, но мне он неизвестен).

Добавлено спустя 17 минут 48 секунд:

Возможно как-то поможет диффур для производящей функции $F(z)=\sum_{n=0}^{\infty}a_nz^n$

$$z(1-55z-111z^2+5z^3-2z^4)F''(z)+(1-114z-105z^2+8z^3-6z^4)F'(z)-(13-15z+2z^3)F(z)=0$$

[Руст]

RIP писал(а):

Явную формулу надо искать в виде

$$a_n=\sum_{k=-\infty}^{\infty}a_{nk},$$

где $a_{nk}$ - целые числа (обычно это произведение каких-нибудь биномиальных коэффициентов). $a_{nk}$ надо подбирать с таким расчётом, чтобы можно было написать

$$(3n^3+23n^2+57n+45)a_{n+3,k}-(171n^3+1140n^2+2488n+1771)a_{n+2,k}+$$

$$+(9n^3+51n^2+92n+54)a_{n+1,k}+(3n^3+14n^2+19n+8)a_{nk}=A_{n,k+1}-A_{nk},$$

т.е. по $k$ можно явно просуммировать.
Если явная формула найдена, то существует алгоритм, позволяющий находить $A_{nk}$ (Gosper summation algorithm). Вся проблема в том, чтобы найти эту формулу (возможно, существует алгоритм, позволяющий находить её, но мне он неизвестен).

RIP как вы представляете сумму бесконечного (в обе стороны) ряда целочисленных величин. В архимедовой норме это можно представить только если число ненулевых элементов конечно.
В виде суммы ряда целых алгебраических чисел я уже написал. Причём сходимость имеется как в архимедовой, так и в неархимодовых нормах ($\frac{t_k}{c^k}$ алгебраический целые числа). Cоответственно целость результата обеспечена (правда, если окажется сумма бесконечной, там надо ещё доказать сходимость в каждой неархимедовой норме).

[RIP]

Руст писал(а):

RIP как вы представляете сумму бесконечного (в обе стороны) ряда целочисленных величин. В архимедовой норме это можно представить только если число ненулевых элементов конечно.

Так и есть, только конечное число членов отлично от нуля. Например, последовательность, удовлетворяющая рекуррентному соотношению $(n+2)^3a_{n+2}-(34n^3+153n^2+231n+117)a_{n+1}+(n+1)^3a_n=0$ и начинающаяся с $a_0=1$, $a_1=5$, задаётся формулой

$$a_n=\sum_{k}\binom nk^2\binom{n+k}k^2$$

(попробуйте это доказать )

[Руст]

Ваша формула очень похожа формуле maxalа. По видимому, ответом к задаче maxala так же является некоторая комбинаторная сумма, только с тремя биномиальными коэффициентами, содержащими n.