Рекуррентная последовательность полиномов

[RIP]

Рассмотрим последовательность многочленов $P_n=P_n(z_1,z_2,\dots,z_n)\in\mathbb Z[z_1,\dots,z_n]$, $n\in\mathbb N$:
$P_1=1$, $P_{n+1}=z_1\sum_{k=1}^n\frac{\partial P_n}{\partial z_k}z_{k+1}-(2n-1)z_2P_n$ ($n\in\mathbb N$).

1. Пусть $\{a_n\}_{n=1}^\infty$ - произвольная (числовая) последовательность, такая что $a_1=1$; $b_n:=P_n(a_1,\dots,a_n)$. Доказать, что $P_n(b_1,\dots,b_n)=a_n$.

2. Для произвольных чисел $a,b$ доказать
$P_n\left(1,a-b,(a-b)(a-2b),\dots,\prod_{k=1}^{n-1}(a-kb)\right)=\prod_{k=1}^{n-1}(b-ka)$.

[maxal]

Для доказательства п.1 достаточно показать, что для всех $n\geq 1$ выполняется полиномиальное тождество

$$P_n(P_1(z_1),P_2(z_1,z_2),\dots,P_n(z_1,z_2,\dots,z_n))=z_1^{n-2} z_n.$$

Начнем доказательство издалека
Для начала "сведём" все переменные в единую (экспоненциальную) "производводящую функцию":

$$Z(t) = \sum_{j=1}^{\infty} z_j \frac{t^j}{j!}$$

и определим последовательность функций:

$$Q_n(t) = P_n(Z'(t),Z''(t),\dots,Z^{(n)}(t)).$$

Рекуррентная формула для $P_n$ немедленно дает формулу для $Q_n$:

$$Q_{n+1}(t) = Z'(t) Q'_n(t) - (2n-1) Z''(t) Q_n(t)$$

с начальным условием $Q_1(t)\equiv 1.$

Умножим это тождество на $\frac{x^n}{n!}$:

$$Q_{n+1}(t)\frac{x^n}{n!} = (Z'(t) Q'_n(t) + Z''(t) Q_n(t))\frac{x^n}{n!} - 2 Z''(t) Q_n(t)\frac{x^n}{(n-1)!}$$

и суммируем по $n$ от $1$ до $\infty$:

$$\frac{\partial}{\partial x} G(x,t) - 1 = \frac{\partial}{\partial t} (Z'(t) G(x,t)) - 2 x Z''(t) \frac{\partial}{\partial x} G(x,t)$$

или

$$(2 x Z''(t) + 1)\frac{\partial}{\partial x} G(x,t) - \frac{\partial}{\partial t} (Z'(t) G(x,t)) = 1$$

где

$$G(x,t)=\sum_{n=1}^{\infty} Q_n(t) \frac{x^n}{n!}.$$

Делаем замену $H(x,t) = Z'(t) G(x,t) + t$ и сводим полученное дифференциальное уравнение к классическому:

$$\frac{\partial}{\partial t} H(x,t) - \frac{2 x Z''(t) + 1}{Z'}\frac{\partial}{\partial x} H(x,t) = 0.$$

Его общим решением является:

$$H(x,t)=\Phi(x Z'(t)^2+Z(t))$$

или

$$G(x,t) = \frac{\Phi(x Z'(t)^2+Z(t)) - t}{Z'(t)},$$

где $\Phi(\cdot)$ - произвольная функция, но так как $G(0,t)\equiv 0,$ то $\Phi(y)=Z^{-1}(y).$
Итак, производящая функция равна:

$$G(x,t) = \frac{Z^{-1}(x Z'(t)^2+Z(t)) - t}{Z'(t)}.$$

Теперь вернемся к нашим баранам Легко видеть, что

$$R(y)=\sum_{n=1}^{\infty} P_n(z_1,\dots,z_n) \frac{y^n}{n!} = \sum_{n=1}^{\infty} Q_n(0) \frac{y^n}{n!} = G(y,0) = \frac{Z^{-1}(y Z'(0)^2)}{Z'(0)}$$

и, в частности,

$$Z(R(y)Z'(0))=yZ'(0)^2,$$

$$R^{-1}(s) = \frac{Z(s Z'(0))}{Z'(0)^2}$$

и

$$R'(0)=1.$$

Если мы в качестве $Z(t)$ возьмем $\tilde Z(t)=R(t)=G(t,0)$, то

$$\tilde G(x,0) = \frac{R^{-1}(x R'(0)^2+R(0)) - 0}{R'(0)} =R^{-1}(x) = \frac{Z(xZ'(0))}{Z'(0)^2}$$

и коэффициент при $\frac{x^n}{n!}$ в ней равен

$$P_n(P_1(z_1),\dots,P_n(z_1,\dots,z_n))=Z'(0)^{n-2} Z^{(n)}(0)=z_1^{n-2}z_n$$

что и требовалось доказать.

Так, надо сделать передышку...

Добавлено спустя 55 минут 53 секунды:

Кстати, забыл сделать (очевидный, впрочем) вывод из предыдущих построений, а именно:

$$(\star)\qquad P_n(z_1,\dots,z_n) = n! [x^n] \frac{Z^{-1}(xZ'(0)^2)}{Z'(0)}.$$

Этой формулы достаточно, чтобы разделаться с пунктом 2. А именно, нам всего лишь надо рассмотреть другую $Z$:

$$Z_{a,b}(t) = \sum_{j=1}^{\infty} \frac{t^j}{j!a} \prod_{k=0}^{j-1} (a-bk) = \frac{1}{a}\sum_{j=1}^{\infty} \frac{(bt)^j}{j!} \prod_{k=0}^{j-1} (\frac{a}{b}-k) =$$

$$= \frac{1}{a}\sum_{j=1}^{\infty} (bt)^j{a/b\choose j}=\frac{(1+bt)^{a/b}-1}{a}.$$

Понятно, что обратная функция имеет вид:

$$Z_{a,b}^{-1}(s) = \frac{(1+as)^{b/a} - 1}{b} = Z_{b,a}(s)$$

Тогда в соответствии с формулой (*) имеем:

$$P(1,a-b,\dots,\prod_{k=1}^{n-1} (a-bk)) = n! [x^n] Z^{-1}_{a,b}(x) = n! [x^n] Z_{b,a}(x)=\prod_{k=1}^{n-1}(b-ak).$$

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

P.S. А откуда, кстати, такая зубодробильная задачка? Что-то мне подсказывает, что у нее из какого-то классического результата ноги растут...

[maxal]

У меня был еще один метод вроде как более простой, но одного шага я так и не успел сделать (как в голову пришло указанное выше решение). Пожалуй тоже выложу - там кое-какие свойства интересные упоминаются.

Докажем, что для всех $m\geq 1$ выполняется полиномиальное тождество

$$P_m(P_1(z_1),P_2(z_1,z_2),\dots,P_m(z_1,z_2,\dots,z_m))=z_1^{m-2} z_m.$$

Немного упростим обозначения. Пусть $\bar z_k=(z_1,z_2,\dots,z_k)$, $\bar z'_k=(1,z_2,z_1 z_3,\dots,z_1^{k-2} z_k)$ и $\bar P_k=(P_1(\bar z_1),P_2(\bar z_2),\dots,P_k(\bar z_k))$. И более того, в случае когда вектор выступает аргументом и его размерность понятна, то нижний индекс будем опускать. Эти три вектора связаны так: если в $\bar z_k$ или $\bar z'_k$ подставить $z_i=P_i(\bar z),$ то получится $\bar P_k$; а утверждение, которое нам нужно доказать, эквивалентно тому, что если в $\bar P_k$ подставить $z_i=P_i(\bar z),$ то получится $\bar z'_k$.

Итак, нам нужно доказать:

$$(\star)\qquad P_m(\bar P) = z_1^{m-2} z_m$$

Докажем это утверждение индукцией по $m$.
Случай $m=2,3$ тривиалны. Предположим, что тождества выполняются для всех $3\leq m\leq n$, докажем его для $m=n+1$.

Будем плясать от (*) для $m=n$:

$$(1)\qquad P_n(\bar P) = z_1^{n-2} z_n.$$

Во-первых, заметим, что подстановка в тождество (1) значений $z_i=P_i(\bar z)$ влечёт:

$$(2)\qquad P_n(\bar z') = P_n(\bar z).$$

Беря производную по $z_1$ и снова подставляя $z_i=P_i(\bar z)$, имеем:

$$(3)\qquad\sum_{k=2}^n (k-2) \frac{\partial P_n}{\partial z_k}(\bar P) P_k(\bar z) = \frac{\partial P_n}{\partial z_1}(\bar P)$$

или

$$(4)\qquad\sum_{k=1}^n (k-2) \frac{\partial P_n}{\partial z_k}(\bar P) P_k(\bar z) = 0$$

Далее я хотел доказать следующее свойство:

$$(5)\qquad\sum_{k=1}^n \frac{\partial P_n}{\partial z_k}(\bar P) P_k(\bar z) = (n-1)z_1^{n-2} z_n$$

но простого доказательства для (5) я так и не успел найти (из производящей функции оно, конечно же, легко следует).

Группируя (4) и (5) получаем:

$$(6)\qquad\sum_{k=1}^n (2k-1) \frac{\partial P_n}{\partial z_k}(\bar P) P_k(\bar z) = 3(n-1)z_1^{n-2} z_n$$

Во-вторых, из тождества (1) следует, что

$$(7)\qquad\frac{\partial P_n}{\partial z_n}(\bar P)\cdot \frac{\partial P_n}{\partial z_n}(\bar z) = z_1^{n-2}$$

и также, что для любого $2\leq k<n$,

$$(8)\qquad\sum_{j=k}^n \frac{\partial P_n}{\partial z_j}(\bar P)\cdot \frac{\partial P_j}{\partial z_k}(\bar z) = 0$$

и

$$(9)\qquad\sum_{j=1}^n \frac{\partial P_n}{\partial z_j}(\bar P)\cdot \frac{\partial P_j}{\partial z_1}(\bar z) = (n-2) z_1^{n-3} z_n.$$

В матричной форме это можно представить так (хотя нафиг не надо):

$$\begin{pmatrix} \frac{\partial P_n}{\partial z_n}(\bar z) & 0 & 0 & \dots & 0\\ \frac{\partial P_n}{\partial z_{n-1}}(\bar z) & \frac{\partial P_{n-1}}{\partial z_{n-1}}(\bar z) & 0 & \dots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ \frac{\partial P_n}{\partial z_2}(\bar z) & \frac{\partial P_{n-1}}{\partial z_2}(\bar z) & \frac{\partial P_{n-2}}{\partial z_2}(\bar z) & \dots & \frac{\partial P_2}{\partial z_2}(\bar z) \end{pmatrix} \begin{pmatrix} \frac{\partial P_n}{\partial z_{n}}(\bar P)\\ \frac{\partial P_n}{\partial z_{n-1}}(\bar P)\\ \vdots\\ \frac{\partial P_n}{\partial z_{2}}(\bar P) \end{pmatrix} = \begin{pmatrix} z_1^{n-2}\\ 0\\ 0\\ \vdots\\ (n-2) z_1^{n-3} z_n\end{pmatrix}$$

Теперь (*) для $m=n+1$ доказывается так:

$$P_{n+1}(\bar P) = \sum_{k=1}^n\frac{\partial P_n}{\partial z_k}(\bar P)\cdot P_{k+1}(\bar z) + (2n-1) z_2 z_1^{n-2} z_n=$$

(используем рекуррентную формулу для $P_{k+1}(\bar z)$)

$$=z_1 \sum_{k=1}^n\frac{\partial P_n}{\partial z_k}(\bar P)\sum_{\ell=1}^k \frac{\partial P_k}{\partial z_{\ell}}(\bar z) z_{\ell+1} - z_2 \sum_{k=1}^n (2k-1)\frac{\partial P_n}{\partial z_k}(\bar P) P_k(\bar z) + (2n-1) z_1^{n-2} z_2 z_n=$$

(используем формулы (8-9))

$$=(n-2) z_1^{n-2} z_2 z_n + z_1^{n-1} z_{n+1} - z_2 \sum_{k=1}^n (2k-1)\frac{\partial P_n}{\partial z_k}(\bar P) P_k(\bar z) + (2n-1) z_1^{n-2} z_2 z_n =$$

(используем формулу (6))

$$=z_1^{n-1} z_{n+1}$$

[RIP]

maxal писал(а):

P.S. А откуда, кстати, такая зубодробильная задачка?

Если $x=g(y)$ - функция, обратная к $y=f(x)$, то
$g^{(n)}(y)=\frac{P_n(f'(x),f''(x),\ldots,f^{(n)}(x))}{f'(x)^{2n-1}}$.
Так что задачка на самом деле почти устная. Нужно только знать, откуда у неё ноги растут.

[maxal]

RIP писал(а):

maxal писал(а):

P.S. А откуда, кстати, такая зубодробильная задачка?

Если $x=g(y)$ - функция, обратная к $y=f(x)$, то
$g^{(n)}(y)=\frac{P_n(f'(x),f''(x),\ldots,f^{(n)}(x))}{f'(x)^{2n-1}}$.
Так что задачка на самом деле почти устная. Нужно только знать, откуда у неё ноги растут.

Так эта формула в какой-то мере обращение частного случая (для $g(f(x))=x$) формулы Фаа ди Бруно, что дает такую связь с полиномами Белла 2-го рода (если нигде не напутал):

$$\delta_{n1} = D^n(g(f(x))) = \sum_{k=0}^n \frac{P_k(f'(x),f''(x),\ldots,f^{(k)}(x))}{f'(x)^{2k-1}} B_{n,k}(f'(x),f''(x),\ldots,f^{(n)}(x))$$

или в терминах $z_i$:

$$\sum_{k=0}^n \frac{P_k(z_1,z_2,\ldots,z_k)}{z_1^{2k-1}} B_{n,k}(z_1,z_2,\ldots,z_n)=\delta_{n1}.$$

Отсюда и до выражения $P_n$ через полиномы Белла должно быть рукой подать. Надо будет обдумать на досуге...

[RIP]

Обозначим при $n\in\mathbb N_0$

$$P_n(x,y)=\sum_{k=0}^n(-1)^k\binom{x+k-1}k\binom{y+n-k-1}{n-k}.$$

Докажите, что при $n\ge2$ справедливо равество
\begin{multline*} n(2x+y+2n-1)(x+2y+2n-1)P_n(x,y)P_{n-2}(x+1,y+1)=\\ =(x+y+n-1)(x+2n-1)(y+2n-1)P_{n-1}(x,y)P_{n-1}(x+1,y+1)-\\ -(x+y)(x+1)(y+1)P_{n-1}(x-1,y+2)P_{n-1}(x+2,y-1). \end{multline*}

[RIP]

Рассмотрим последовательность многочленов
$v_n=v_n(x,q,\lambda,\alpha)\in\mathbb Z[x,q,\lambda,\alpha]$,
определённую с помощью рекуррентного соотношения

$$v_0=x-1,\qquad v_n=(q^n-\lambda)v_{n-1}-\alpha^n\quad(n\in\mathbb N).$$

Далее, при $n\in\mathbb N$ рассмотрим определитель

$$V_n=\det(v_{i+j})_{i,j=0}^{n-1}\in\mathbb Z[x,q,\lambda,\alpha].$$

I. Сначала рассмотрим $V_n$ как многочлены от $q$ (т. е.
$V_n\in\mathbb Z[x,\lambda,\alpha][q]$).

I-1. Докажите, что

$$e_0(n):=\mathop{\mathrm{ord}}_{q=0}V_n=\binom n3,$$

причём коэффициент при $q^{e_0(n)}$ в $V_n$ равен

$$\begin{cases}\alpha^{n(n-1)/2}\lambda^{n(n-2)/4}(\lambda-(\lambda+\alpha)x)^{n/2},&\text{если $n$ чётно,}\\\alpha^{n(n-1)/2}\lambda^{(n-1)^2/4}(x-1)(\lambda-(\lambda+\alpha)x)^{(n-1)/2},&\text{если $n$ нечётно.}\end{cases}$$

I-$\widetilde1$. Обозначим

$$\widetilde V_n=V_n\Bigr|_{\lambda=0}\in\mathbb Z[x,\alpha][q].$$

Докажите, что

$$\widetilde e_0(n):=\mathop{\mathrm{ord}}_{q=0}\widetilde V_n=\begin{cases}\frac{n(n-2)(5n-2)}{24},&\text{если $n$ чётно,}\\\frac{n(n-1)(5n-7)}{24},&\text{если $n$ нечётно,}\\\end{cases}$$

причём коэффициент при $q^{\widetilde e_0(n)}$ в $\widetilde V_n$ равен

$$\begin{cases}(-1)^{n(n+2)/8}\alpha^{n(5n-2)/8}x^{n/2},&\text{если $n$ чётно,}\\(-1)^{(n-1)(n-3)/8}\alpha^{(n-1)(5n+1)/8}K_{(n-1)/2},&\text{если $n$ нечётно,}\end{cases}$$

где

$$K_n=K_n(x,\alpha)=\det\begin{pmatrix}x-1&-\alpha&-\alpha^2&\ldots&-\alpha^n\\x&x-1&-\alpha&\ldots&-\alpha^{n-1}\\&x&x-1&\ldots&-\alpha^{n-2}\\&&\ddots&\ddots&\vdots\\\text{\LARGE0}&&&x&x-1\end{pmatrix}.$$

Можно, конечно, для $K_n$ выписать и "явную" формулу, поскольку

$$K_0=x-1,\qquad K_1=(x-1)^2+\alpha x,$$

$$K_{n+2}=(x-1-\alpha x)K_{n+1}+\alpha x^2K_n\qquad(n\in\mathbb N_0),$$

но по понятным причинам я этого делать не буду.

I-2. Пусть $l\in\mathbb N$,

$$\Phi_l(q)=\prod_{\substack{1\le j\le l\\(j,l)=1}}(q-e^{2\pi ij/l})$$

--- круговой многочлен. Докажите, что $V_n$ делится на $\Phi_l(q)^{e_l(n)}$,
где

$$e_l(n)=\sum_{k=0}^{n-1}\left(\left\lfloor\frac{k+l}{3l}\right\rfloor+\left\lfloor\frac k{3l}\right\rfloor\right)=\text{лень считать.}$$

I-$\widetilde2$. Пусть $\lambda_0$ --- произвольный корень степени
$l$ из $1$ (т. е. $\lambda_0^l=1$). Обозначим

$$\widetilde V_n=V_n\Bigr|_{\lambda=\lambda_0}.$$

Докажите, что $\widetilde V_n$ делится на $\Phi_l(q)^{\widetilde e_l(n)}$, где

$$\widetilde e_l(n)=2\sum_{k=0}^{n-1}\left\lfloor\frac k{2l}\right\rfloor=\text{аналогично.}$$

II. Дальше будем рассматривать $V_n$ как многочлены от $x$.

II-1. Докажите, что коэффициент при $x^n$ в $V_n$ равен

$$q^{n(n-1)(2n-1)/6}\prod_{l=1}^n\bigl((q^l-1)(q^{l}-\lambda)\bigr)^{n-l}.$$

II-2. Докажите формулу для результанта

$$\mathop{\mathrm{Res}}(V_n,V_{n+1})=(-1)^{n(n+1)/2}\alpha^{n(n+1)(2n+1)/3}q^{n(n^2-1)(5n-2)/12}\prod_{l=1}^n\bigl((q^l-1)^3(\alpha+\lambda q^l)(q^{l}-\lambda)\bigr)^{(n-l)(n-l+1)}.$$

Have fun!