Recorrências e funções geradoras

A aplicação resolve recorrências lineares com coeficientes constantes de qualquer ordem pela equação característica – também raízes múltiplas e complexas (a forma complexa da solução e a sua passagem à forma real pelo teorema de De Moivre) – e com lado direito da forma P(n)·qⁿ (também cos nφ, sin nφ, ressonância e soma de lados direitos). As condições iniciais determinam as constantes; como verificação, a aplicação calcula mais termos pela recorrência e compara-os com a fórmula.

O chip «Método» oferece também a função geradora (A(x) = Σ aₙxⁿ, frações parciais, séries geométricas), as potências de uma matriz (diagonalização) ou, na primeira ordem, o somatório. Uma recorrência de primeira ordem com coeficiente variável (aₙ₊₁ = (n + 1)aₙ) resolve-se por um produto (fatoriais), as recorrências não lineares convertíveis pela substituição bₙ = 1/aₙ ou bₙ = ln aₙ. Um sistema de duas recorrências resolve-se eliminando uma sucessão ou pela matriz, e uma recorrência de dividir para conquistar T(n) = aT(n/b) + f(n) por n = bᵏ – com a estimativa do teorema mestre.

Com a operação «Função geradora», a aplicação encontra a função geradora de uma sucessão dada por uma fórmula (n² + 2ⁿ) ou pelos primeiros termos (1, 0, 1, 0, …) e, ao contrário, a fórmula de aₙ a partir de uma função A(x). O número de soluções inteiras não negativas de x₁ + x₂ + … = N (também com limites ou coeficientes – pagar com moedas) é um coeficiente de uma função geradora.

O gráfico mostra os termos da sucessão como pontos (num sistema, as duas sucessões).

Como introduzir

`a(n+2) = 5a(n+1) - 6a(n), a(0) = 1, a(1) = 4`	Com parênteses, as condições após uma vírgula.
`a_{n+2} = 5a_{n+1} - 6a_n`	Com índices (também de uma foto). Sem condições: a solução geral com as constantes C₁, C₂.
`F_n = F_{n-1} + F_{n-2}, F_1 = F_2 = 1`	O índice pode descer (aₙ₋₁, aₙ₋₂); o mesmo valor pode ser dado a vários termos.
`a_{n+1} = a_n + 2b_n b_{n+1} = 3a_n + b_n a_0 = 1, b_0 = 0`	Um sistema – as equações em linhas, as condições na última.
`T(n) = 2T(n/2) + n, T(1) = 1`	Dividir para conquistar – um termo em n/b.
`n^2 + 2^n`	A fórmula de uma sucessão com a operação «Função geradora» (também aₙ = …).
`1, 0, 1, 0, ...`	Os primeiros termos separados por vírgulas.
`1/(1 - x - x^2)`	Uma função geradora em x (também A(x) = …) – a fórmula de aₙ.
`número de soluções x_1 + x_2 + x_3 = 10, x_1 <= 3`	O número de soluções inteiras não negativas com limites.

Exemplos

Duas raízes reais distintas, a verificação com mais termos.

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$

A sucessão de Fibonacci – a 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ízes complexas 1 ± i – a forma complexa e o 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$

O lado direito n, uma raiz dupla 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$

A mesma recorrência pela função geradora.

Enunciado: a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4 Função geradora

$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 mesma recorrência pelas potências de uma matriz.

Enunciado: a_{n+2} = 5a_{n+1} - 6a_n, a_0 = 1, a_1 = 4 Potências de uma 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$

Uma recorrência de primeira ordem por somatório.

Enunciado: a_{n+1} = 2a_n + 1, a_0 = 0 Somatório

$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$

Um coeficiente variável – o produto dá um fatorial.

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$

Uma recorrência não linear – a substituição 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$

Um sistema de duas recorrências eliminando a sucessão 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$

Dividir para conquistar (merge sort) – n = 2ᵏ e o teorema mestre.

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

A função geradora da sucessão n² + 2ⁿ.

Enunciado: n^2 + 2^n Função geradora

A fórmula de aₙ a partir de uma função geradora – frações parciais com raízes irracionais.

Enunciado: 1/(1 - x - x^2) Função geradora

O número de soluções de x₁ + x₂ + x₃ = 10 com x₁ ≤ 3.

Enunciado: número de soluções x_1 + x_2 + x_3 = 10, x_1 <= 3

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

Limitações conhecidas

Ainda não: recorrências lineares de ordem superior com coeficientes variáveis, sistemas de três ou mais recorrências, dividir para conquistar com vários termos (T(n/2) e T(n/3)) e recorrências não lineares que estas substituições não tornam lineares.