Changes

Uma relação de recorrência descreve uma relação que um membro de uma sequência {<math>{a_n}</math>} de valores tem de outro membro da sequência que o precedem. Por exemplo, a famosa sequência de Fibonacci {<math>F_n</math>} satisfaz a relação de recorrência

O famoso enigma conhecido como Torre de Hanoi é discutido no texto, onde a relação de recorrência:

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.

Agora vamos generalizar o que temos feito e escrever um procedimento em Maple para resolver uma relação de recorrência geral homogênea com coeficientes constantes, de grau 2, considerando que as raízes do polinômio característico da relação de recorrência são distintos. Vamos escrever um procedimento RecSol2 que resolve a recorrência

Nós temos, até agora, discutido relações de recorrência lineares homogêneas com coeficientes constantes. No entanto, as técnicas utilizadas para resolvê-los podem ser estendidas para fornecer soluções para as recorrências heterogêneas deste tipo. Estas são relações de recorrência da forma

Agora que vimos como é possível usar Maple para implementar um algoritmo para resolver relações de recorrência simples, é hora de introduzir próprios utilitários do Maple para trabalhar com relações de recorrência. Já vimos o comando Maple solve para trabalhar com equações e sistemas de equações polinomiais. Da mesma forma, há um comando rSolve em Maple, que é especialmente projetado para lidar com relações de recorrência. É uma versão sofisticada de nosso procedimento RecSol2, que pode lidar com relações de recorrência de grau arbitrário, e pode lidar com raízes repetidas, bem como relações de recorrência não-lineares. Para usar rSolve, você precisa dizer a ele qual é a relação de recorrência, e algumas condições iniciais. Você também deve especificar o nome da função recursiva para resolver. Por exemplo, para resolver a recorrência Fibonacci, você pode digitar

Um bom exemplo de relações de “Divide and Conquer” é a fornecida pelo algoritmo de busca binária. Aqui, vamos considerar uma aplicação prática deste algoritmo em uma implementação de uma busca binária em uma lista ordenada de números inteiros. O algoritmo procura por chave no IList.

Nós vamos começar a ver, nesta seção, a segunda das duas principais técnicas de contagem abrangida no Capítulo 5 desse texto – O princípio de inclusão e exclusão. Vamos ver como usar Maple para resolver problemas com essa técnica. No cerne do princípio de inclusão e exclusão está a fórmula

Funções geradoras são ferramentas poderosas para modelar conjuntos de objetos e suas construções. Por exemplo, se um conjunto de objetos é construído a partir de dois outros através da realização de um produto cartesiano de dois conjuntos subjacentes, em seguida, a função geradora para o novo conjunto é muitas vezes apenas o produto das funções geradoras pelos dois conjuntos subjacentes. Assim, saber como um conjunto é construído pode nos ajudar a construir a sua função geradora.

<math>g (x) = \ frac {-1} {x ^ {2} + x - 1}</math>

Esta seção apresentará algumas soluções em Maple para alguns dos problemas. Nós nem sempre deve apresentado aqui uma solução completa; em alguns casos, nós apenas sugerimos uma ou duas coisas para você experimentar, e deixar a implementação detalhado para você.

'''Solução'''

'''Solução''

Esieve(1000);

'''Exemplo 1 (página 415)'''

<math> 5c + 5d = 5</math>