Recurrencias y funciones generadoras

Sin a₀ hay muchas sucesiones posibles: elegir a₀=1 o a₀=2 produce listas distintas. Para una regla que despeja aₙ a partir de k términos anteriores, dar esos k términos de inicio permite continuar por iteración.

Una fórmula explícita calcula aₙ directamente en función de n. Para probar que resuelve la recurrencia hay que verificar el inicio y la regla para todo índice de su rango. Si ambos se cumplen, la unicidad por iteración, o una inducción equivalente, identifica toda la sucesión.

Comprobar solo varios términos no es una demostración general.

Para aₙ=c₁aₙ₋₁+⋯+cₖaₙ₋ₖ, con coeficientes constantes y cₖ≠0, probamos una solución rⁿ.

Sus raíces no son términos de la sucesión: son bases de soluciones que combinaremos para ajustar los valores iniciales.

Sobre los complejos, una raíz r de multiplicidad m aporta rⁿ, nrⁿ,…, nᵐ⁻¹rⁿ. Estas k soluciones forman una base del espacio de soluciones, que tiene dimensión k por la elección libre de los k inicios. Una forma de entender los factores n es el operador de avance E: (E−r)(rⁿp(n))=rⁿ⁺¹[p(n+1)−p(n)], que reduce el grado del polinomio p.

Aplicarlo m veces anula grados menores que m.

Con coeficientes reales las raíces complejas aparecen conjugadas; sus combinaciones reales se expresan con cosenos y senos. No se omiten las raíces repetidas ni la segunda solución de una pareja conjugada: hacen falta suficientes constantes para ajustar todos los inicios.

Si aₙ satisface una regla lineal con un término conocido gₙ, la diferencia entre dos soluciones satisface la regla homogénea. Por eso buscamos una solución particular y le sumamos la familia homogénea. Los valores iniciales fijan después las constantes que faltan.

A veces un cambio de variable elimina el término añadido. Si se ensaya una forma que ya es solución homogénea, puede no servir como particular: aparece resonancia y se necesitan factores n apropiados. Este método de coeficientes constantes no resuelve por sí solo toda recurrencia, como una que dependa de a⌊n/2⌋ o incluya productos de términos.

Aquí z es un símbolo: dos series son iguales si coinciden todos sus coeficientes. [zⁿ]A(z) significa “coeficiente de grado n”. No estamos todavía sumando números ni eligiendo un valor de z.

Sumar es sumar columnas. En un producto, el coeficiente de grado n recibe las contribuciones de grados k y n−k para 0≤k≤n: una suma finita. Esa finitud define el producto formal sin discutir convergencia. Operaciones infinitas que aporten infinitos sumandos a una misma columna necesitarían una definición adicional.

zA(z) tiene coeficientes 0, a₀, a₁, a₂,…: multiplicar por z mueve una columna.

Si la suma empieza en n=2, se restan a₀ y a₁z del lado no desplazado.

Escribe primero el rango y solo después cambia el índice. Los términos que se restan contienen las condiciones iniciales. Un denominador correcto con un numerador equivocado puede describir una sucesión diferente. La tabla muestra la progresión 2,6,18,54,… y cómo se desplaza.

Si A tiene coeficientes aₙ y B tiene bₙ, el coeficiente de zⁿ en AB es Σₖ₌₀ⁿaₖbₙ₋ₖ. Esto es una convolución: escogemos cuánto grado aporta el primer factor y cuánto falta en el segundo, multiplicamos los coeficientes y sumamos todos los repartos.

En conteo, si un objeto es un par ordenado de componentes de tamaños k y n−k, los coeficientes cuentan opciones para cada componente. La construcción debe ser única. Cuando los tamaños solo pueden valer cero o uno, las generadoras son polinomios; cuando pueden ser cualquier entero no negativo, aparece la geométrica formal.

Trabajamos con coeficientes reales o complejos.

Recíprocamente, si q₀≠0, se fija b₀=1/q₀ y cada coeficiente siguiente se despeja a partir de los anteriores: bₙ=−(Σⱼ₌₁ⁿqⱼbₙ₋ⱼ)/q₀. Eso construye una inversa única.

Como 1−cz tiene constante uno, su inversa es Σcⁿzⁿ. La misma expansión como función numérica converge cuando |cz|<1, pero la identidad formal no necesita escoger z. La serie z no tiene inversa dentro de series de potencias con exponentes no negativos: su producto con cualquier serie tiene constante cero.

Al sumar una recurrencia lineal homogénea de coeficientes constantes, el denominador recoge la regla y el numerador los términos iniciales. Factorizar el denominador y usar fracciones simples transforma el cociente en series cuyos coeficientes conocemos. Un factor (1−cz) se corresponde con potencias cⁿ.

Un factor repetido (1−cz)ᵐ aporta C(n+m−1, m−1)cⁿ: al multiplicar m geométricas, cada reparto de n en m cantidades no negativas pesa cⁿ. Para c≠0, ese coeficiente es un polinomio en n de grado m−1 por cⁿ, coherente con raíces repetidas de la ecuación característica.

Los recubrimientos del dibujo tienen T₀=T₁=1 y generadora 1/(1−z−z²); la sucesión Fibonacci del ejercicio final empieza con 0,1 y tiene z/(1−z−z²). La relación es Tₙ=Fₙ₊₁: reconocer la regla no permite olvidar el índice inicial.

La derivada formal se define por (zⁿ)′=nzⁿ⁻¹ y linealidad coeficiente a coeficiente.

El cero en n=0 aparece automáticamente: derivar elimina el término constante.

Las reglas de suma y producto se verifican comparando los coeficientes finitos correspondientes; se puede derivar también una identidad formal. No es una justificación para evaluar fuera de un radio de convergencia. La operación zD, derivar y luego multiplicar por z, permite ponderar repetidamente por n sin desplazar las posiciones finales.