Recurrencias y funciones generatrices

La aplicación resuelve recurrencias lineales con coeficientes constantes de cualquier orden mediante la ecuación característica – también raíces múltiples y complejas (la forma compleja de la solución y su paso a la real por el teorema de De Moivre) – y con un lado derecho de la forma P(n)·qⁿ (también cos nφ, sin nφ, resonancia y suma de lados derechos). Las condiciones iniciales determinan las constantes; como comprobación, la aplicación calcula más términos con la recurrencia y los compara con la fórmula.

Con el chip «Método» se puede elegir también la función generatriz (A(x) = Σ aₙxⁿ, fracciones parciales, series geométricas), las potencias de una matriz (diagonalización) o, en primer orden, la suma. Una recurrencia de primer orden con coeficiente variable (aₙ₊₁ = (n + 1)aₙ) se resuelve con un producto (factoriales), las recurrencias no lineales convertibles con la sustitución bₙ = 1/aₙ o bₙ = ln aₙ. Un sistema de dos recurrencias se resuelve eliminando una sucesión o con la matriz, y una recurrencia de divide y vencerás T(n) = aT(n/b) + f(n) con n = bᵏ, junto con la estimación del teorema maestro.

Con la operación «Función generatriz» la aplicación halla la función generatriz de una sucesión dada por una fórmula (n² + 2ⁿ) o por sus primeros términos (1, 0, 1, 0, …) y, al revés, la fórmula de aₙ a partir de una función A(x). El número de soluciones enteras no negativas de x₁ + x₂ + … = N (también con cotas o coeficientes: pagar con monedas) es un coeficiente de una función generatriz.

La gráfica muestra los términos de la sucesión como puntos (en un sistema, las dos sucesiones).

Cómo introducirlo

`a(n+2) = 5a(n+1) - 6a(n), a(0) = 1, a(1) = 4`	Con paréntesis, las condiciones tras una coma.
`a_{n+2} = 5a_{n+1} - 6a_n`	Con subíndices (también de una foto). Sin condiciones: la solución general con constantes C₁, C₂.
`F_n = F_{n-1} + F_{n-2}, F_1 = F_2 = 1`	El índice puede bajar (aₙ₋₁, aₙ₋₂); un mismo valor puede darse a varios términos.
`a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0`	Un sistema: las ecuaciones en líneas, las condiciones en la última.
`T(n) = 2T(n/2) + n, T(1) = 1`	Divide y vencerás: un término en n/b.
`n^2 + 2^n`	La fórmula de una sucesión con la operación «Función generatriz» (también aₙ = …).
`1, 0, 1, 0, ...`	Los primeros términos separados por comas.
`1/(1 - x - x^2)`	Una función generatriz en x (también A(x) = …): la fórmula de aₙ.
`número de soluciones x_1 + x_2 + x_3 = 10, x_1 <= 3`	El número de soluciones enteras no negativas con cotas.

Ejemplos

Dos raíces reales distintas, comprobación con más términos.

Enunciado: a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

La sucesión de Fibonacci: la fórmula de Binet.

Enunciado: F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1

$F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1$

$F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1$ $F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1$

Raíces complejas 1 ± i: la forma compleja y el teorema de De Moivre.

Enunciado: a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2

$a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$

$a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$ $a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$ $a_{n+2} = 2a_{n+1} - 2a_n, a_0 = 1, a_1 = 2$

El lado derecho n, una raíz doble 2.

Enunciado: a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0

$a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$

$a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$ $a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$ $a_{n+2} = 4a_{n+1} - 4a_n + n, a_0 = 0, a_1 = 0$

La misma recurrencia con la función generatriz.

Enunciado: a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4 Función generatriz

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

La misma recurrencia con potencias de una matriz.

Enunciado: a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4 Potencias de una matriz

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

$a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$ $a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4$

Una recurrencia de primer orden sumando.

Enunciado: a_{n+1} = 2a_n + 1, a_0 = 0 Suma

$a_{n+1} = 2a_n + 1, a_0 = 0$

$a_{n+1} = 2a_n + 1, a_0 = 0$ $a_{n+1} = 2a_n + 1, a_0 = 0$

Un coeficiente variable: el producto da un factorial.

Enunciado: a_{n+1} = (n+1)a_n, a_0 = 1

$a_{n+1} = (n+1)a_n, a_0 = 1$

$a_{n+1} = (n+1)a_n, a_0 = 1$ $a_{n+1} = (n+1)a_n, a_0 = 1$

Una recurrencia no lineal: la sustitución bₙ = 1/aₙ.

Enunciado: a_{n+1} = a_n/(1 + a_n), a_0 = 1

$a_{n+1} = a_n/(1 + a_n), a_0 = 1$

$a_{n+1} = a_n/(1 + a_n), a_0 = 1$ $a_{n+1} = a_n/(1 + a_n), a_0 = 1$ $a_{n+1} = a_n/(1 + a_n), a_0 = 1$

Un sistema de dos recurrencias eliminando la sucesión bₙ.

Enunciado:

a_{n+1} = a_n + 2b_n
b_{n+1} = 3a_n + b_n
a_0 = 1, b_0 = 0

$a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$

$a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$ $a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$ $a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0$

Divide y vencerás (merge sort): n = 2ᵏ y el teorema maestro.

Enunciado: T(n) = 2T(n/2) + n, T(1) = 1

La función generatriz de la sucesión n² + 2ⁿ.

Enunciado: n^2 + 2^n Función generatriz

La fórmula de aₙ a partir de una función generatriz: fracciones parciales con raíces irracionales.

Enunciado: 1/(1 - x - x^2) Función generatriz

El número de soluciones de x₁ + x₂ + x₃ = 10 con x₁ ≤ 3.

Enunciado: número de soluciones x_1 + x_2 + x_3 = 10, x_1 <= 3

počet řešení x_1 + x_2 + x_3 = 10, x_1 <= 3

Limitaciones conocidas

Todavía no: recurrencias lineales de orden superior con coeficientes variables, sistemas de tres o más recurrencias, divide y vencerás con varios términos (T(n/2) y T(n/3)) y recurrencias no lineales que estas sustituciones no vuelven lineales.