109
edits
Changes
Jump to navigation
Jump to search
Técnicas Avançadas de Contagem (view source)
Revision as of 19:42, 8 December 2015
, 19:42, 8 December 2015no edit summary
Esieve(100);
Esieve(1000);
==='''5. Relações de recorrência'''===
==='''6. Exemplos Extras'''===
Exemplo 1 (página 415)
Resolva: <math>a_n = 2a_{(n-1)} + 3a_{(n-2)}, a_{(0)} = 0, a_{(1)} = 1 </math>
''Solução'':
Usando <math> a_{(n)} = r^n </math>, a equação característica a seguir é obtida:
<math>r^2 – 2r – 3 = 0 </math>
Os fatores do lado esquerdo como <math>{(r-3)(r+1)</math>, obtendo-se as raízes 3 e -1. Assim, a solução geral para a relação de recorrência dada é
<math>a_{(n)} = c3^n + d(-1)^n = 0</math>.
Usando as condições iniciais <math>a_{(0)} = 0</math> e <math>a_{(1)} = 1 </math> constrói-se um sistema de equações
<math> c . 3^0 + d (-1)^0 = 0</math>
<math> c . 3^1 + d (-1)^1 = 1</math>
ou
<math> c+d = 0</math>
<math> 3c-d = 1</math>
Com solução de <math> c = \left(\frac{1}{4} \right)</math> e <math> d = \left(\frac{-1}{4} \right)</math>. Dessa forma, a solução para a a relação de recorrência dada é
<math> a_{(n)} = \left(\frac{1}{4} \right).3^n \left(\frac{-1}{4} \right).(-1)^n</math>
