целочисленная последовательность

[Руст]

Пусть $a_n$ определена рекурентна:
$(n+3)a_{n+1}=(4n+6)a_n-12na_{n-1}, \ a_0=1,a_1=2.$
Докажите, что она целочисленна.

[maxal]

Пусть $A(x)=\sum_{n=0}^{\infty} a_n x^n$ - производящая функция для этой последовательности. Тогда рекуррентное соотношение переписывается в виде:

$$\frac{(A(x)x^2)' - 2a_0 x - 3 a_1 x^2}{x^3} = 4\frac{(A(x)x^{\frac32})' - \frac32 a_0 x^{\frac12}}{x^\frac32} - 12 (A(x)x)'$$

или

$$(x-4x^2+12x^3)A'(x) + (2-6x+12x^2)A(x) - 2 = 0.$$

Решением этого диффура с учетом начальных условия является:

$$A(x) = \frac{\sqrt{1-4x+12x^2} + 2x - 1}{4x^2}$$

откуда в частности следует, что

$$a_n = \frac{1}{4}\sum_{k=\lceil (n+2)/2\rceil}^{n+2} {\frac12\choose k} {k\choose n+2-k} (-4)^{2k-n-2} 12^{n+2-k} = \frac{1}{2}\sum_{k=\lceil (n+2)/2\rceil}^{n+2} C_{k-1} {k\choose n+2-k} (-1)^{n+k-1} 3^{n+2-k},$$

где $C_k$ - числа Каталана.

Заметим, что $C_{k-1}$ нечётно, только если $k=2^t$. При этом ${2^t\choose n+2-2^t}$ нечетно, только если $n+2-2^t=0$ или $n+2-2^t=2^t$. Таким образом, в сумме в формуле для $a_n$ присутствуют нечетные слагаемые, только если $n+2$ является степенью 2-ки, но и в этом случае таких слагаемых ровно два: для $k=(n+2)/2$ и $k=n+2$. Поэтому $a_n$ всегда является целым числом.

[RIP]

Рассмотрим рекуррентную последовательность
$v_1=2$, $(n+1)v_{n+1}=nv_n+v_n^2$.
Верно ли, что все $v_n\in\mathbb Z$?

[Профессор Снэйп]

RIP писал(а):

Рассмотрим рекуррентную последовательность
$v_1=2$, $(n+1)v_{n+1}=nv_n+v_n^2$.
Верно ли, что все $v_n\in\mathbb Z$?

Тривиальное применение матиндукции позволяет доказать, что это она А доказав, что это она, внимательно читаем, что про неё написано, и узнаём, что $v_n \in \mathbb{Z}$ тогда и только тогда, когда $n \leqslant 41$

А вообще, конечно, интересно подумать над тем, как доказать, что $v_{42} \not\in \mathbb{Z}$, без ссылок на энциклопедию или большого объёма вычислений. Энциклопедия советует рассмотреть последовательность $s_n = (n+1)v_n \mod k$; для каких $k$ и как это надо делать, я пока не понял.

[maxal]

Профессор Снэйп в сообщении #191527 писал(а):

Энциклопедия советует рассмотреть последовательность $s_n = (n+1)v_n \mod k$; для каких $k$ и как это надо делать, я пока не понял.

Например, для $k=43$, чтобы убедиться, что $(43 v_{43})\not\equiv 0\pmod{43}$.

Вот значения $nv_n\bmod 43$ для $n=1,2,\dots,43$:

2, 6, 15, 40, 11, 21, 1, 37, 8, 21, 31, 13, 30, 31, 37, 32, 36, 14, 30, 2, 42, 3, 39, 27, 37, 18, 34, 15, 16, 41, 11, 42, 15, 28, 26, 7, 8, 5, 6, 19, 40, 10, 24

Как видим, последнее число не равно 0, а должно бы было, будь $v_{43}$ целым...

[Профессор Снэйп]

maxal писал(а):

Профессор Снэйп в сообщении #191527 писал(а):

Энциклопедия советует рассмотреть последовательность $s_n = (n+1)v_n \mod k$; для каких $k$ и как это надо делать, я пока не понял.

Например, для $k=43$, чтобы убедиться, что $s_{42}\not\equiv 0\pmod{43}$.

А Вы уверены, что $s_{42} \not\equiv 0\pmod{43}$? Как Вы это вывели?

$\mathbb{Z}_{43}$ вроде бы поле. Если все вычисления производить в нём по реккурентной формуле

$$ (n+1)^3 s_{n+1} = n(n+1)(n+2)s_n + (n+2)s_n^2 $$

то для $s_{42}$ как раз ноль и получим!

[maxal]

Профессор Снэйп
Рекуррентная формула для $s_n=nv_n$ такая:

$$s_{n+1} = s_n + (s_n / n)^2$$

Значения вплоть до $s_{43}$ по модулю 43 вычисляются по ней без проблем, так как $43$ - число простое и деление на $n<43$ в поле $\mathbb{Z}_{43}$ легко осуществляется. Числовые значения $s_n$ для $n=1,2,\dots,43$ я привел в предыдущем сообщении.

[Профессор Снэйп]

maxal писал(а):

Профессор Снэйп
Рекуррентная формула для $s_n=nv_n$ такая:

$$s_{n+1} = s_n + (s_n / n)^2$$

Это для $s_n = nv_n$ такая, а для $s_n = (n+1)v_n$ другая!

А для $s_n = nv_n$ в том, что $s_{42} \not\equiv 0\pmod{43}$, я ничего страшного не вижу. Где Вы тут нашли какое-то противоречие? Мы же в этом случае для того, чтобы получить $s_{42}$, умножаем $v_{42}$ на $42$, а не на $43$.

[maxal]

Профессор Снэйп
Противоречие такое:
$(43v_{43})\not\equiv 0\pmod{43}$

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

А именно, числовые расчеты дают $(43v_{43})\equiv 24\pmod{43}$ - см. выше.

[Профессор Снэйп]

А, ну всё, я понял Вас. Вы сами виноваты: у нас $s_n$ разные, а Вы мне про мою $s_n$ ответили, имея в виду свою.

Кстати, получается тогда, что здесь то ли ошибочное указание дали:

Цитата:

By considering s(n) := n*a(n) mod k, one finds that a(n) is nonintegral iff n>42

то ли они какое-то другое доказательство, отличное от Вашего, имели в виду (если переводить обозначения, то $v_n = a(n+1)$).

Вы по своей формуле $s_{43} = 43 \cdot v_{43}$ на компутере считали? Интересно, а без него никак?

[maxal]

Профессор Снэйп писал(а):

А, ну всё, я понял Вас. Вы сами виноваты: у нас $s_n$ разные, а Вы мне про мою $s_n$ ответили, имея в виду свою.

Кстати, получается тогда, что здесь то ли ошибочное указание дали:

Цитата:

By considering s(n) := n*a(n) mod k, one finds that a(n) is nonintegral iff n>42

Я вообще старался избегать $s_n$ - без него как-то нагляднее. В OEIS - да, ошибка. Начиная с формулы "a(n+1) = sum(a(k)^2,k=0..n)/n" по которой вообще нельзя получить значение a(1). И далее должно быть "By considering s(n) := n*a(n+1) ..."
Идея тут собственно в том, чтобы не делить на $n$ сразу, а показать, что делимое на него не делится нацело.

[Руст]

Всвязи с этой задачей возникает вопрос: существуют ли целые $a\not =0,b,c$, что рекурентно определённая последовательность $v_1=c, (n+1)v_{n+1}=v_n(v_n+an+b)$ (рассмотренный случай a=1,b=0,c=2) целочисленная?

[Профессор Снэйп]

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

Всвязи с этой задачей возникает вопрос: существуют ли целые $a\not =0,b,c$, что рекурентно определённая последовательность $v_1=c, (n+1)v_{n+1}=v_n(v_n+an+b)$ (рассмотренный случай a=1,b=0,c=2) целочисленная?

Например, $v_1 = 1$, $(n+1)v_{n+1} = v_n^2 + nv_n$ ($a=1$, $b=0$, $c=1$).

[maxal]

RIP писал(а):

Рассмотрим рекуррентную последовательность
$v_1=2$, $(n+1)v_{n+1}=nv_n+v_n^2$.
Верно ли, что все $v_n\in\mathbb Z$?

Теперь мы знаем, что эта последовательность не является целочисленной. А я задам такой вопрос: пусть значение $v_n$ представлено в виде несократимой дроби, возможна ли ситуация, что знаменатель этой дроби является чётным числом? Если да, то каково наименьшее такое $n$?

[Руст]

Несложно доказать, что если $v_{p^2}$ p-целое и $v_{p^2}=v_1\mod p^2$, то число p не встретится в знаменателе. Это верно для $p=2$.