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

[RIP]

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

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

Во-первых, даже если ряд и можно написать, то я уверен, что он будет расходиться для каждого $n$, т.е. этот ряд можно рассматривать максимум как асимптотический (это ни на чём не основанное имхо, просто я так думаю).
Во-вторых, члены этого ряда необязательно целые (ведь в знаменателе стоит $n+c$).
В-третьих, такое док-во вряд ли прокатит. То, что последовательность целочисленная - это просто чудо, существенно эксплуатирующее тот факт, что она начинается именно с $1,13,409,...$

[Руст]

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

[RIP]

worm2 писал(а):

RIP писал(а):

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

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

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

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

Такие последовательности возникают не на ровном месте, а обычно используются для доказательства иррациональности тех или иных чисел. Возможно, что и эта последовательность с чем-то связана.

[maxal]

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

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

Что меня поразило в данном случае - тот факт, что полиномы в первой формуле второй степени. Если попробовать получить из какой-то произвольной формулы для $a_{n+3}$ формулу для $a_{n+4},$ то в результате максимальная степень полиномиальных коэффициентов скорее всего не уменьшится (а то и увеличится). А для этой последовательности она таки уменьшается.

RIP писал(а):

maxal, Вы умеете доказывать целочисленность?

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

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

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

Рустем как всегда проницателен.

Я так понял, что без явной формулы дело заглохло. Что ж, вдохну свежую струю
Вот явная формула:

$$a_n = \sum_{k=n}^{3n} \sum_{i=n}^k (-1)^{k+i} {k\choose i} {i\choose n}^3$$

Осталось доказать, что она удовлетворяет рекуррентной формуле...

[RIP]

maxal писал(а):

Я так понял, что без явной формулы дело заглохло. Что ж, вдохну свежую струю
Вот явная формула:

$$a_n = \sum_{k=n}^{3n} \sum_{i=n}^k (-1)^{k+i} {k\choose i} {i\choose n}^3$$

Осталось доказать, что она удовлетворяет рекуррентной формуле...

Ну это уже не должно быть слишком сложно. А вот откуда взялась эта формула?

[maxal]

Что же, карты на стол (worm2 уже намекал на источник): cм. A126086

[maxal]

Еще одна задача подобного типа:

Последовательность $\{ a_n\}$ задана формулой:
$a_1 = 2,$
$a_{n+1} = a_n + \lfloor \sqrt{2}\cdot a_n\rfloor$ для $n\geq 1.$

Последовательность $\{ b_n\}$ задана формулой:
$b_1 = 2,\ b_2 = 4,$
$b_{n+1} = 1+\left\lfloor \frac{b_n^2}{b_{n-1}} \right\rfloor$ для $n\geq 2.$

Докажите, что эти последовательности совпадают.

[Руст]

Легко показать, что обе последовательности удовлетворяют рекурентному соотношению:
$a_{n+1}=2a_n+a_{n-1}-1$ с одинаковыми начальными условиями, т.е.
$a_n=\frac{(1+\sqrt 2 )^{n+1}+(1-\sqrt 2 )^{n+1}}{4}+\frac 12 .$