31
edits
Changes
Técnicas Avançadas de Contagem (view source)
Revision as of 23:17, 25 November 2015
, 23:17, 25 November 2015no edit summary
==='''2. Resolução de recorrências com Maple'''===
Agora que sabemos como implementar relações de recorrência em Maple, e temos trabalhado com eles um pouco, vamos ver como usar Maple para resolver certos tipos de relações de recorrência.
Maple tem um poderoso solucionador de recorrência, rsolver, que discutiremos mais tarde. A sua utilização, no entanto, pode obscurecer algumas das ideias importantes que estão envolvidas. Portanto, devemos primeiro usar algumas das instalações mais rudimentares do Maple para resolver certos tipos de relações de recorrência, um passo de cada vez.
Dada uma seqüência definida recursivamente <math> \ {r_ {n} \} </math>, o que nós gostaríamos é encontrar algum tipo de fórmula, envolvendo apenas o índice n (e, talvez, outras constantes fixas e funções conhecidas) que não dependem do conhecimento da valor de r_ {k}, por qualquer índice k.
Para começar, vamos considerar relações de recorrência que são lineares, homogêneas, e que têm coeficientes constantes; ou seja, eles têm a forma
onde <math> a_{1}, a_{2}, \ldots , a_{k} </math> são constantes reais e <math> a_{k} </math> é diferente de zero. Lembre-se que o inteiro k é chamado de grau da relação de recorrrência. Para ter uma núnica solução, pelo menos o k inicial deve sere especificado.
O método geral para resolver tal relação de recorrência envolve encontrar as raízes de sua polinômio característico.l
<math> x^{k} - a_{1}x^{k-1} - a_{2}x^{k-2} - \cdots - a_{k-1}x - a_{k} </math>
Quando este polinômio tem raízes distintas, todas as soluções são combinações lineares das enésimas (palavra para número ordinal) potências dessas raízes. Quando não são raízes repetidas, a situação é um pouco mais complicado, como veremos.
Para começar, vamos considerar uma relação de recorrência linear homogênea com coeficientes constantes de grau dois:
<math> r_{n} = 2r_{n-1} + 3r_{n-2} </math>
sujeitos às condições iniciais
<math> r_{1} = 4 \hspace{3em}\mbox{and}\hspace{3em} r_{2} = 2 </math>
Então sua equação caracerística é Then its characteristic equation is
<math> x^{2} - 2x - 3 </math>