Una "identidad polinomial inusual"

Question

Para un entero positivo $q$ definir una secuencia de polinomio de la siguiente manera:

$$\begin{align} p_0(q)&\equiv1\\ p_1(q)&\equiv0\\ p_n(q)&=q^n-\sum_{k=1}^n{k+q-1\choose k}p_{n-k}(q),\ n\geq2 \end{align}$$

La experimentación sugiere que $$p_n(q)=(q-1)^qq^{n-q},\text{ for }n\geq q$$

Me encontré con este, mientras que tratando de resolver este problema en la probabilidad de que un seleccionados al azar polinomio en un campo con $q$ elementos no tiene raíces en el campo. Yo quería averiguar lo que la respuesta sería, por lo que me contó el no-desaparición de monic polinomios restando el número de polinomios con una raíz. Una $n$th-grado del polinomio con una raíz es un producto de $k>0$ términos de la forma $(q-a)$ veces no desapareciendo polinomio de grado $n-k,$ que representa la recurrencia de la relación anterior.

Mientras que estos experimentos me permitió adivinar la probabilidad correcta, yo no era capaz de probar cualquier cosa, porque los polinomios sí mismos complicarse muy rápido.

$$\begin{align} p_2(q)&=\frac{q \left(q - 1\right)}{2}\\ p_3(q)&=\frac{q^{3}}{3} - \frac{q}{3}\\ p_4(q)&=\frac{q \left(q - 1\right) \left(3 q^{2} + q + 2\right)}{8}\\ p_5(q)&=\frac{q \left(q - 1\right) \left(q + 1\right) \left(11 q^{2} - 5 q + 6\right)}{30}\\ p_6(q)&=\frac{q \left(q - 1\right) \left(53 q^{4} + 26 q^{3} + 19 q^{2} - 2 q + 24\right)}{144}\\ p_7(q)&=\frac{q \left(q - 1\right) \left(q + 1\right) \left(309 q^{4} - 154 q^{3} + 239 q^{2} - 154 q + 120\right)}{840}\\ &\vdots \end{align}$$

Jyrki Lahtonen ha dado una solución elegante al problema original, que por cierto se establece esta identidad al $q$ es una fuente primaria de energía, pero en mis experimentos, me di cuenta de que parece probable que sea cierto cuando $q$ es cualquier entero positivo. El uso de sympy, que calcula los polinomios $p_n$ para $n\leq25,$ y verificado la identidad de $q$ en el mismo rango.

No tengo buenas ideas acerca de cómo probar esto. Ya sabemos que esto es verdad para el primer poderes, pensé tratando de demostrar que si es cierto relativamente primer enteros $q$ e $r,$ entonces es verdadero para $qr,$ pero el problema es que tenemos que lidiar con $p_n$ cuando $n$ es pequeña, y 1) la inducción de la hipótesis de no cubre ese, y 2) los polinomios ellos mismos no tienen una conveniente explícito de la fórmula. Yo no soy lo suficientemente inteligente como para encontrar la fórmula explícita para la $p_n$ dado en Felix Matin de la respuesta.

Así que el único enfoque prometedor que puedo pensar es encontrar algo que la $p_n$ recuento, incluso cuando $q$ no es una fuente primaria de energía, pero no tengo idea de lo que sería.

Por supuesto, la definición de la $p_n$ es válido si $q$ es real (o incluso un complejo). Puede algo ser dicho en estos dominios más grandes?

Answer 1

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove armada]{\displaystyle{#1}}\,} \newcommand{\llaves}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\parcial #3^{#1}}} \newcommand{\raíz}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{\left.\vphantom{\LARGE} p_{n}\pars{q} \,\right\vert_{{\large n\ \geq\ 2} \cima {\large q\ \en\ \mathbb{N_{\ \geq\ 1}}}} = q^{n} - \sum_{k = 1}^{n}{k + q - 1 \elegir k} p_{n - k}\pars{q}\,,\ \left\{\begin{array}{rcl} \ds{p_{0}\pars{q}} & \ds{\equiv} & \ds{1} \\ \ds{p_{1}\pars{q}} & \ds{\equiv} & \ds{0} \end{array}\right.}$

$$ \bbx{\mbox{Permite}\ \mc{P}\pars{q,z} \equiv \sum_{n = 0}^{\infty}p_{n}\pars{q}z^{n} \implica p_{n}\pars{q} = \bracks{z^{n}}\mc{P}\pars{q,z}} $$

---

El anterior general de la recurrencia está muy bien escribir como $\pars{~\mbox{with}\ n \geq 2~}$: $$ p_{n}\pars{q} + qp_{n - 1}\pars{q} = q^{n} - \sum_{k = 2}^{n}{k + q - 1 \elegir k} p_{n - k}\pars{q} $$

---

A continuación, \begin{align} &\sum_{n = 2}^{\infty}p_{n}\pars{q}z^{n} + q\sum_{n = 2}^{\infty}p_{n - 1}\pars{q}z^{n} \\ = &\ \sum_{n = 2}^{\infty}q^{n}z^{n} - \ \sum_{n = 2}^{\infty}z^{n} \sum_{k = 2}^{n}{k + q - 1 \choose k} p_{n - k}\pars{q} \\[5mm] &\ \overbrace{\sum_{n = 0}^{\infty}p_{n}\pars{q}z^{n}} ^{\ds{\mc{P}\pars{q,z}}}\ -\ \overbrace{p_{0}\pars{q}}^{\ds{1}}\ -\ \overbrace{p_{1}\pars{q}}^{\ds{0}}\ z\ +\ q\ \overbrace{\sum_{n = 1}^{\infty}p_{n}\pars{q}z^{n + 1}} ^{\ds{z\bracks{\mc{P}\pars{q,z} - 1}}} \\ = &\ {q^{2}z^{2} \over 1 - qz} - \sum_{k = 2}^{\infty}\ \underbrace{k + q - 1 \choose k} _{\ds{{-q \choose k}\pars{-1}^{k}}}\ \underbrace{\sum_{n = k}^{\infty} p_{n - k}\pars{q}z^{n}}_{\ds{z^{k}\mc{P}\pars{q,z}}} \\[5mm] & \bracks{1 + qz + \sum_{k = 2}^{\infty}{-q \choose k}\pars{-z}^{k}} \mc{P}\pars{q,z} = 1 + qz + {q^{2}z^{2} \over 1 - qz} = {1 \over 1 - qz} \\[5mm] & \bracks{1 + qz + \pars{1 - z}^{-q} - 1 - qz}\mc{P}\pars{q,z} = {1 \over 1 - qz} \\[5mm] & \implies \bbx{\mc{P}\pars{q,z} = {\pars{1 - z}^{q} \over 1 - qz}} \end{align}

---

\begin{align} \mc{P}\pars{q,z} & = {\pars{1 - z}^{q} \over 1 - qz} = \bracks{\sum_{i = 0}^{\infty}{q \choose i}\pars{-z}^{i}} \bracks{\sum_{j = 0}^{\infty}\pars{qz}^{j}} \\[5mm] & = \sum_{i = 0}^{\infty}\sum_{j = 0}^{\infty}{q \choose i} q^{j}\pars{-1}^{i}\sum_{n = 0}^{\infty}z^{n} \bracks{i + j = n} \\[5mm] & = \sum_{n = 0}^{\infty}\braces{\sum_{i = 0}^{\infty}\sum_{j = 0}^{\infty}{q \choose i} q^{j}\pars{-1}^{i}\bracks{j = n - i}}z^{n} \\[5mm] & = \sum_{n = 0}^{\infty}\braces{\sum_{i = 0}^{\infty}{q \choose i} q^{n - i}\pars{-1}^{i}\bracks{n - i \geq 0}}z^{n} \\[5mm] & = \sum_{n = 0}^{\infty}\braces{q^{n} \sum_{i = 0}^{n}{q \choose i} \pars{-\,{1 \over q}}^{i}}z^{n} \end{align}

$$ \bbox[15px,#ffd,border:1px groove armada]{p_{n}\pars{q} = q^{n}\sum_{i = 0}^{n}{p \elegir i} \pars{-\,{1 \over q}}^{i}\,,\qquad q \in \mathbb{N}_{\ \geq\ 1}} $$

Cuando $\ds{n \geq q\,,\quad p_{n}\pars{q} = q^{n}\bracks{1 + \pars{-\,{1 \over q}}}^{q} = q^{n - q}\pars{q - 1}^{p}}$