por Andrés Ventas
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: $ \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}} $
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 sucesión polinómicas daquela estará probado o problema.
Unha condición necesaria e suficiente para que unha sucesión estea xerada por un polinomio está relacionada con un resultado das diferenzas finitas:
Supoñamos que $f:\N \rightarrow \R$ é unha sucesión. 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 sucesión $f(n)$ a partir das súas diferenzas finitas, independentemente da sucesión 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 sucesións polinómicas en vez de sucesións xeradas por un polinomio, máis moitas veces fálase de polinomial sequences noutro sentido que sería o de sucesións 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_{k-1} n^{k-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 sucesión 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 sucesión 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 sucesión 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 sucesión $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 sucesión 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 sucesións 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 sucesión de Fibonnacci onde as diferenzas dos elementos consecutivos forma reiteradamente a mesma sucesión 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 sucesión $(a_n)$ a partir dun determinado elemento $i$, para todo $i > n, a_{n+1} - a_{n} > a_n$, daquela calquera subsucesión 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 subsucesión infinita con todos os elementos en orde inversa sempre haberá polo menos dous elementos $a_p, a_q, p \lt q,$, consecutivos na subsucesión, que cumpren $a_q - a_p > (2^{q-p}-1) a_p > a_p$, por tanto na subsucesión 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 sucesións 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 sucesión 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 sucesión.
Na OEIS, sucesión 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$
$9, 30, \ldots$
$\ldots$
E agora copiado co mesmo formato de texto da OEIS:
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, sucesión 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$.
Ningún comentario:
Publicar un comentario