¿La función generadora tiene utilidad en relaciones de recurrencia que contienen división en subíndices?

Question

Es bien sabido que las funciones generadoras son estupendas para resolver relaciones de recurrencia de la forma $$a_n = A*a_{n-1} + B*a_{n-2} + \dots$$

Pero me preguntaba qué ocurre si la relación de recurrencia contiene división en los subíndices. Así es: $$a_n = A*a_{\lfloor \frac{n}{2} \rfloor} + B*a_{\lfloor \frac{n}{3} \rfloor} + \dots$$ donde $A$ y $B$ son algunos contantes. En esta etapa, ignoremos los casos límite (n=0, 1, etc.) y supongamos que $A$ y $B$ son iguales a $1$ .

Nota $A(x)$ como función generadora de la secuencia $<a_n>_{0}^\infty$ tenemos $$A(x) = (1+x)A(x^2) + (1+x+x^2)A(x^3)$$ si lo he entendido bien.

Lo he buscado en internet e incluso en el libro de gfologia de Wilf, pero no he encontrado explicacion para este caso. ¿Quizás no podemos resolver esta recurrencia fácilmente y en efecto, no podemos tener una forma cerrada para esta recurrencia? ¿Existen otras herramientas para resolverlo? Gracias de antemano.

Answer 1

Erdös et al, "The Asymptotic Behavior of a Family of Sequences" (Pacific Journal of Mathematics 126:2, pp 227-241, dic 1987, aquí una versión más legible que la de la revista) discuten exactamente este tipo de secuencias.

Answer 2

Pregunta interesante, pero creo que sólo las secuencias constantes lo verifican. toma $(a_n)$ una secuencia que verifica una ecuación de recurrencia :

$$a_n=\sum_{k=2}^r\lambda_ka_{\lfloor \frac{n}{k} \rfloor}$$

A continuación, evaluándolo para $n=0$ obtenemos :

$$a_0=\sum_{k=2}^r\lambda_ka_0 $$

Es decir $a_0=0$ o :

$$\sum_{k=2}^r\lambda_k=1 $$

En primer lugar, si $a_0=0$ puis $a_1=a_0*=0$ y con una inducción trivial se tiene que $a_n=0$ para todos $n$ .

Supongamos ahora que $a_0\neq 0$ entonces demostraremos por inducción que $a_n=a_0$ . El caso $n=0$ es trivial. Supongamos que $a_l=a_0$ para $0\leq l<n$ entonces para todos $k\geq 2$ :

$$\lfloor \frac{n}{k} \rfloor <n$$

Así que por hipótesis de inducción :

$$a_{\lfloor \frac{n}{k} \rfloor}=a_0 $$

Por último :

$$a_n=\sum_{k=2}^r\lambda_ka_{\lfloor \frac{n}{k} \rfloor}=\sum_{k=2}^r\lambda_ka_0=a_0$$

Si unimos todas las piezas esto demuestra que cualquier función que verifique una ecuación de recurrencia que implique una división debe ser constante.