Sábese se unha secuencia pode ser xerada por un polinomio?

 por Andrés Ventas

 $ \newcommand{\N}{\mathbb{N}} \newcommand{\R}{\mathbb{R}} \newcommand{\fa}[2]{\rlap{#1}\rule[9pt]{#2}{0.8pt}} \newcommand{\fd}[2]{\rlap{#1}\rule[-3pt]{#2}{0.8pt}} $

Esta entrada vén motivada por un problema proposto polo grupo Sementeira da Facultade de Matemáticas da USC no seu concurso de problemas que se atopa na web Búscase solución 2025-2026.

Un problema da primeira xornada indica:

Sexan $C_n= \dfrac{1}{n+1}\displaystyle\binom{2n}{n}, \forall n \in \N$, o n-ésimo número de Catalan e $P(x)$ un polinomio con coeficientes reais. Proba que é imposible que $P(k)=C_{n(k)} ,\forall k \in \N$, onde ${C_{n(k)}:k \in \N}$ é unha colección infinita numerable de números de Catalan.

-------------------------------------

Como todos os números de Catalan cumpren que $ C_{n+1} - C_{n} > C_{n}, \ n \ge 2$, se probamos que esa condición non a poden cumprir as secuencias polinómicas daquela estará probado o problema.

Unha condición necesaria e suficiente para que unha secuencia estea xerada por un polinomio está dada mediante as diferenzas finitas:

Supoñamos que $f:\N \rightarrow \R$ é unha secuencia. Entón $f$ é un polinomio se e só se existe $i$ tal que $\forall n, \ \Delta_n^i(f)=0$, onde $\Delta_n^i(f)=\Delta_{n+1}^{i-1}(f)−\Delta_n^{i-1}(f)$.

A fórmula para obter $n$ termos dunha secuencia $f(n)$ a partir das súas diferenzas finitas, independentemente da secuencia ser polinómica, é:

$f(n+1) = \displaystyle\sum_{k=0..n} \displaystyle\binom{n}{k} b(k)$ onde os $b_k$ son os primeiros coeficientes das $k$ diferenzas finitas, $b_k=\Delta_0^k$. (ver exemplo embaixo).

Voume referir a secuencias polinómicas en vez de secuencias xeradas por un polinomio, máis moitas veces fálase de polinomial sequences noutro sentido que sería o de secuencias de distintos polinomios, como por exemplo os polinomios de Chebyshev.

Para a seguinte proposición e a demostración imos considerar un polinomio $p(n) = a_k n^k + a_{n-1} x^{n-1} + \cdots + a_0$ onde $a_k \gt 0$. Para polinomios con $a_k \lt 0$ habería que trocar as desigualdades $\lt$ por $\gt$ e viceversa, $\gt$ por $\lt$.

Proposición

Dada unha secuencia infinita numerábel $f: \N \rightarrow \R$, se existe $i$ tal que para todo $n>i, f(n+1) - f(n) > f(n),$ daquela $f$ non é un polinomio.

Proba 1 da proposición

Dado un polinomio $f(n)=a_k n^k + a_{k-1} n^{k-1} + \ldots + a_0$ temos que:

$\begin{equation*} \begin{aligned} f(n+1) - f(n) &= a_k (n+1)^k + a_{k-1} (n+1)^{k-1} + \ldots a_0 - (a_k n^k + a_{k-1} n^{k-1} + \ldots + a_0) \\ &= a_k n^k + a_k \displaystyle\binom{k}{1} n^{k-1} + a_{k-1} n^{k-1} + \\ & + a_k \displaystyle\binom{k}{2} n^{k-2} + a_{k-1} \displaystyle\binom{k-1}{1} n^{k-2} + a_{k-2} n^{k-2} + \ldots + a_k + \ldots + a_1 + a_0 \\ & - a_k n^k + a_{k-1} n^{k-1} + \ldots + a_0 \\ &= b_{k-1} n^{k-1} + b_{k-2} n^{k-2} + \ldots + b_0. \end{aligned} \end{equation*}$

onde os $b_k$ son os coeficientes agrupados das potencias $n^k$.

Así temos que a partir dun $i$ suficientemente grande, para $n>i$ temos $ \ b_{k-1} n^{k-1} + b_{k-2} n^{k-2} + \ldots + b_0 \lt a_k n^k + \ldots$

Por tanto por contradición unha secuencia onde cada par de termos consecutivos a partir dun $i$ dan unha resta superior ao menor do par non pode ser polinómica.

Proba 2 da proposición

Supomos que a secuencia cumpre a condición necesaria e suficiente das diferenzas finitas e por tanto existe un $k=i$ a partir do que as diferenzas son $0$.

Calculamos os elementos $n$ e $n+1$ da secuencia $f(n)$ mediante os valores dados polas diferenzas finitas que por tanto serán constantes ata ese $k=i$ e $0$ a partir de $k=i+1$, temos:

$f(n) = b_0 \binom{n}{0} + b_1 \binom{n}{1} + b_2 \binom{n}{2} + \ldots b_i \binom{n}{i}.$

$f(n+1) = b_0 \binom{n+1}{0} + b_1 \binom{n+1}{1} + b_2 \binom{n+1}{2} + \ldots b_i \binom{n+1}{i}.$

Restando ambas as dúas:

$\Delta_n^1 = f(n+1) - f(n) = \sum_{k=0}^{i} b_k \bigg( \displaystyle\binom{n+1}{k} - \displaystyle\binom{n}{k}\bigg)=\sum_{k=0}^{i} b_k \dfrac{k\cdot n^{\fd{(k-1)}{25pt}}}{k!}.$

Sendo $n^{\fd{(i-1)}{25pt}}$ o factorial descendente e os $b_k$ os primeiros valores das $k$-ésimas diferenzas.

A partir dun $n>2i$ esa resta $f(n+1) - f(n)$ é menor que $f(n)$ pois cada termo un a un é menor que o pequeno da resta, isto é, para todo termo $k$-ésimo do sumatorio binomial, que denominamos $f(k,n)$, temos:

$f(k,2i+1) - f(k,2i)= b_k \bigg( \displaystyle\binom{n+1}{k} - \displaystyle\binom{n}{k}\bigg)= b_k \dfrac{k\cdot n^{\fd{(k-1)}{25pt}}}{k!}$

Para $k>i, f(k,n)=0$ e para $k \le i$ sendo $2i \le n$ (para que só sumen os termos binomiais por debaixo ou igual ao binomial central) cada termo cumpre:

$b_k \dfrac{k\cdot n^{\fd{(k-1)}{25pt}}}{k!} \le b_k \dfrac{ n^{\fd{(k)}{15pt}}}{k!} = b_k \dfrac{(n-k+1) n^{\fd{(k-1)}{25pt}}}{k!}$

pois para $k \lt n/2$ temos que $k \lt n-k+1$.

En conclusión, para todo sumando do sumatorio a resta é menor que o elemento pequeno, e por tanto a resta dos sumatorios tamén é menor $f(2i+1) - f(2i) \lt f(2i).$

Por tanto por contradición unha secuencia onde cada par de termos consecutivos a partir dun $i$ dan unha resta superior ao menor do par non se pode xerar mediante un polinomio.

Condición suficiente mais non necesaria

A proposición dá unha condición suficiente para NON ser unha sucesión polinómica. É necesaria? non. Pode haber secuencias con todos os elementos con diferenza menor que o pequeno dos dous consecutivos, e que aínda así non se poden representar por un polinomio. As típicas deste caso son as recorrentes, en concreto a secuencia de Fibonnacci onde as diferenzas dos elementos consecutivos forma reiteradamente a mesma secuencia e nunca chega a cero.

E para que queremos unha condición só suficiente se xa tíñamos unha condición necesaria e suficiente coas diferenzas? porque a condición das diferenzas que chegan a cero é por si soa inefectiva. Cantas diferenzas calculamos 3000, 15000? Se non chegamos a cero haberá que atopar outra regra que nos indique que nunca vai ser cero, por exemplo un padrón nos elementos cero das diferenzas. Polynomial representing a sequence of integers.

Para os números de Catalan:

$\begin{equation*} \begin{aligned} & f(n+1) - f(n) \lt f(n); \\ &\dfrac{1}{n+2} \displaystyle\binom{2n+2}{n+1} - \dfrac{1}{n+1} \displaystyle\binom{2n}{n} > \dfrac{1}{n+1} \displaystyle\binom{2n}{n}; \\ &\dfrac{(2n+2)^{\fd{n}{10pt}}}{(n+1)!} - \dfrac{(2n)^{\fd{n}{10pt}}}{(n+1)!} > \dfrac{(2n)^{\fd{n}{10pt}}}{(n+1)!}; \\ &(2n+2)(2n+1) (2n)^{\fd{n-2}{25pt}} - (2n)^{\fd{n-2}{25pt}} (n+2)(n+1) > (2n)^{\fd{n-2}{25pt}} (n+2)(n+1); \\ &(2n+2)(2n+1) > 2(n+2)(n+1); \\ & 2n+1 > n+2. \\ \end{aligned} \end{equation*} $

Exemplo curto con números:

$C_5 - C_4 = 42 - 14 = \dfrac{1}{6}\displaystyle\binom{10}{5} - \dfrac{1}{5}\displaystyle\binom{8}{4} = \dfrac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{6 \cdot 5!} - \dfrac{8 \cdot 7 \cdot 6 \cdot 5}{ 5!};$

$(10 \cdot 9 - 6 \cdot 5) 8 \cdot 7 > 8 \cdot 7 \cdot 6 \cdot 5; $

$10 \cdot 9 > 2 \cdot 6 \cdot 5; \quad 9 > 6. $

Este exemplo fai pensar nun corolario da proposición:

Corolario

Se unha secuencia $(a_n)$ a partir dun determinado elemento $i$, para todo $i > n, a_{n+1} - a_{n} > a_n$, daquela calquera subsecuencia infinita dela $(b_n)$, aínda que estea desordenada, non pode ser xerada por un polinomio.

Proba do corolario

Para todo $i > n, a_{n+1} - a_{n} > a_n$ implica $ a_{n+1} > 2 a_n$ e por tanto $ a_{n+h} > 2^h a_n$. Como non se pode obter unha subsecuencia infinita con todos os elementos en orde inversa sempre haberá polo menos dous elementos $a_p, a_q, p \lt q,$, consecutivos na subsecuencia, que cumpren $a_q - a_p > (2^{q-p}-1) a_p > a_p$, por tanto na subsecuencia temos $a_p=b_n; \ a_q=b_{n+1}; \ b_{n+1}-b_{n} > b_n$; contradicindo as demostracións da proposición que indican que a partir de determinado $i$ para todo $n,\ b_{n+1}-b_{n} \lt b_n$.

Exemplos numéricos de secuencias polinómicas

$p(x)= 2x^2 + 5x + 1$ para $x=0, 1, 2, 3, \ldots$ temos $a_n={1, 8, 19, 34, 53, 76, \ldots}$

Diferenzas:

$\Delta^0 = 1, 8, 19, 34, 53, 76, \ldots$

$\Delta^1 = 7, 11, 15, 19, 23, \ldots$ A partir do terceiro elemento as diferenzas son menores que o elemento pequeno. Iso é condición necesaria, non suficiente.

$\Delta^1 = 4, 4, 4, 4, \ldots$

$\Delta^2 = 0, 0, 0, \ldots$ Todas as diferenzas cero: condición necesaria e suficiente.

E agora calculamos a secuencia usando as diferenzas obtidas:

$a_0 = 1 \binom{0}{0} = 1.$

$a_1 = 1 \binom{1}{0} + 7 \binom{1}{1}= 8.$

$a_2 = 1 \binom{2}{0} + 7 \binom{2}{1} + 4 \binom{2}{2}= 1 + 14 + 4=19.$

$a_3 = 1 \binom{3}{0} + 7 \binom{3}{1} + 4 \binom{3}{2}= 1 + 21 + 12=34.$

$a_4 = 1 \binom{4}{0} + 7 \binom{4}{1} + 4 \binom{4}{2}= 1 + 28 + 4\cdot 6=53.$

$a_5 = 1 \binom{5}{0} + 7 \binom{5}{1} + 4 \binom{5}{2}= 1 + 35 + 4\cdot 10=76.$

$\ldots$

Vemos que a partir do elemento $a_2$ todos os coeficientes $b_k$ son iguais ($1, 7, 4$) e só varían os binomiais, e afinando máis só varían os números superiores dos binomiais.

$x^5 + 3x +4$ para $x \in \N$ dá ${4, 8, 42, 256, 1040, 3144, 7798, 16832, 32796, 59080, 100034, \ldots}$ e vemos que para $n=6; 16832 - 7798 = 9034$ (onde a diferenza segue a ser maior que $a_n$) mais para $n=7; 32796 - 16832 = 15964$ (menor que $a_n=16832$) e xa temos $a_{n+1} - a_n \lt a_n$ no resto da secuencia.

Na OEIS, secuencia A001006: Motzkin numbers, temos a fórmula por diferenzas dos números de Catalan cando comezan por $n=1$:

$C_n=1, 2, 5, 14, 42, 132, 429, \ldots$

$1, 3, 9, 28, 90, 297, \ldots$

$2, 6, 19, 62, 207, \ldots$

$4, 13, 43, 145, \ldots$

$\ldots$

Catalan(n+1) = Sum_{k=0..n} binomial(n,k)*a(k). E.g.: 42 = 1*1 + 4*1 + 6*2 + 4*4 + 1*9. - Doron Zeilberger, Mar 12 2015.

Tamén na OEIS, secuencia A005043, Riordan numbers. O primeiro elemento das distintas diferenzas é o que lle chaman "trasformación binomial inversa", pois a transformación binomial (directa) sería precisamente a de obter os números de Catalan a partir desta secuencia. Serían as diferenzas contando un elemento máis da secuencia anterior, isto é, comezando os números de Catalan por $n=0, C_n=1, 1, 2, 5, 14, 42, \ldots$ e por tanto $\Delta_0^n= 1, 0, 1, 1, 3, 6, 15, 36, \ldots$

Inverse binomial transform of A000108 (Catalan numbers). - Philippe Deléham, Oct 20 2006

Exemplo: $42 = 1*1 + 5*0 + 10*1 + 10*1 + 5*3 + 1*6$.

Bibliografía

Búscase solución 2025-2026.

Diferenzas finitas

Polynomial representing a sequence of integers.

A001006 Motzkin numbers.