Funções Geradoras e Relações de Recorrência Flashcards
Profundidade de uma relação de recorrência?
A ordem até qual a recorrência abrange.
O que torna uma relação uma relação de recorrência?
Os próximos resultados são escritos à custa dos anteriores.
Como resolvemos uma relação de recorrência?
Em geral, determinamos uma fórmula fechada para an.
Ex:
an=3n é uma solução de an=2an-1-an-2
com a1=3, a2=6 e uma vez que
3n = 2(3(n-1)) - 3(n-2)
Nota: an-1 = 3(n-1) e an-2= 3(n-2)
Qual será a fórmula de recorrência para o seguinte problema?
an - número de permutações do conjunto N. Isto é [n] = {1,2,..,n-1,n}
Dado que o número de permutações possíveis para a posição do número n é n.
E o número de permutações para os restantes n-1 números é an-1.
Tem-se:
an=n*an-1
Equação de Recorrência Linear Homogénea?
Quantas condições iniciais necessitamos para determinar a solução?
É uma equação de recorrência do tipo:
an = c1an-1 + c2an-2 + cr*an-r
ci é uma constante para i = {1,2,…,r}
Necessitamos de r condições iniciais.
Equação característica de uma equação de recorrência linear homogénea?
x^r - c1 * x^r-1 - c2 * x^r-2 - … - cr = 0
Ex:
x^2 - c1*x-c2 = 0
Solução Geral de uma equação de recorrência linear homogénea?
Dadas α e β raízes (não nulas) de uma equação característica, a solução geral vem dada da seguinte forma:
an = C1α^n + C2β^n
Se α = β
an = (C1+C2n)α ^n
C1 e C2 são coeficientes determinados pelas condições iniciais.
Raízes Características de uma Equação de Recorrência Linear Homogénea?
São as raizes reais ou complexas da equação característica.
Equação de recorrência linear não homogénea de ordem r?
an - c1an-1 - c2an-2 - … - cr*an-r = f(n)
Onde f(n) é uma função não nula.
A Solução Geral de equação de recorrência linear não homogénea de ordem r?
É dada por uma solução
solução geral an(1) da seguinte relação:
an = an(1) + an(2)
Igualamos a equação equação de recorrência linear não homogénea de ordem r a zero.
A solução geral será isso mesmo que determinamos numa equação de recorrência linear não homogénea.
1º Caso da Solução Particular de uma equação de recorrência linear não homogénea de ordem r?
1º Caso: f(n) = cq^n
Onde c e q são constantes , logo:
an(2) = An^m * q^n
Onde m é a multiplicidade de q enquanto raiz da equação característica da equação homogénea.
A é uma constante.
Se q = 1, f(n) = c, ou seja, um polinómio de grau zero.
2º Caso da Solução Particular de uma equação de recorrência linear não homogénea de ordem r?
2º Caso: f(n) é um polinómio de grau k.
an(2) = A0n^r + A1n^r+1 + … + Ak*n^r+k
Onde r é a multiplicidade de 1 enquanto raiz da equação característica da equação homogénea.
Caso não seja raiz, tem-se r=0.
A0, A1, … , Ak são constantes
3º Caso da Solução Particular de uma equação de recorrência linear não homogénea de ordem r?
3º Caso: f(n) 0 f1(n) + f2(n) + … + fk(n)
Temos uma solução particular para cada uma das equações com a seguinte estrutura:
an - c1an-1 - c2an-2 - … - cr*an-r = fk(n) , k = {1,2,..,k}
Ou seja, resolvemos cada uma das soluções particulares e a solução particular será a junção de todas elas:
an(2) = an1(2) + an2(2) + … + ank(2)
