53
edits
Changes
Jump to navigation
Jump to search
Técnicas Avançadas de Contagem (view source)
Revision as of 17:03, 3 December 2015
, 17:03, 3 December 2015no edit summary
onde <math> \alpha_{n}, \alpha_{n-1}, \ ldots, \alpha_{n-k}</math> e <math>c_{n} </math> são constantes. A única nova problemática é que, aqui, o <math>c_{n}</math> não precisa ser zero. Dito de outra forma, uma equação desta forma, na qual cada <math>c_{n}</math> é zero é homogênea, por isso as relações homogêneas são apenas um caso especial deste tipo mais geral. Para resolver a recorrência mais geral, precisamos fazer duas coisas:
1) Encontrar uma solução específica para a recorrência heterogênea;
A recorrência homogênea correspondente é apenas a obtida substituindo a sequência <math> c_ {{n}} </math> pela sequência zero:
<math>\alphaalpha_{n}r_{n} + \alpha{n-1}r_{n-1} + \cdots + \alpha{n-k}r_{n-k} = 0 </math>
Então, nós já sabemos como fazer o segundo passo.
O primeiro passo é mais difícil, mas com a ajuda do Maple, ele manejável.
rSolve (R r(0) = 0, r (n) = 3 * r (n-1) + 3 ^ N, r (n));
normal (%, expanded);
Isso nos diz que <math>r_{n} = n3^n </math> é uma solução para a relação de recorrência <math>r_{n} = 3r_{n-1} + 3^n</math>. Agora, todas as soluções são obtidos por adição de uma solução para este conjunto de soluções da recorrência homogênea correspondente.
rSolve (r (n) = 3 * r (n-1), r (n));
% + * 3 N ^ N;
Agora vamos resolver a Torre de Hanoi
<math>{H_} {n H_n = 2H_ {Nn-1} + 1</math>
o que dá o número de movimentos necessários para resolver o enigma da Torres de Hanoi com n discos. Lembre-se que <math>H_ {1} = 1.</math> . A relação de recorrência homogênea associada é
<math>h_ {n} = 2 h_ {n - 1}</math>
com polinômio característico
A única raiz disso é 2, portanto, todas as soluções da relação de recorrência homogênea têm a forma
<math>h_ {n} = \ alpha 2 ^ {n - 1}</math>
para alguma constante <math>/alfa </math>. (A potência de 2 é N-1, em vez de N, porque a recorrência começa no 1 em vez de 0.) Soluções para a H são obtidos a partir das soluções para h por adição de uma solução particular para H. Agora, H tem a solução constante <math>H_ N} = {-1</math>, para todo n, então todas as soluções para a H são da forma
