Videoaula

Definimos o que é uma sequência e apresentamos duas formas de descrever os termos de uma sequência. A primeira é a forma fechada, em que exibimos uma fórmula que apresenta o n-ésimo termo da sequência em função de n. A segunda é a forma recursiva, em que para obtermos o próximo termo da sequência nós utilizamos termos anteriores da sequência. Neste módulo, estudaremos as sequências obtidas desta segunda forma e também conhecidas como recorrências.

Damos alguns exemplos de sequências expressas por recorrências. Enfatizamos que para descrever uma sequência de forma recursiva é necessário, além de uma fórmula que relacione o próximo termo com os anteriores, exibir também termos iniciais da sequência para que ela fique bem determinada. Finalmente, reconhecemos progressões aritméticas e geométricas como exemplos de recorrências e ensinamos como descrevê-las desta forma.

Nesta aula damos alguns exemplos de recorrências que utilizam em sua fórmula mais de um dos termos anteriores para descrever o próximo termo. Entre os exemplos, encontra-se a famosa sequência de Fibonacci e uma sequência cuja lei de formação é tomar a média aritmética dos números que já surgiram.

Começamos a exemplificar como recorrências aparecem naturalmente em alguns tipos de problema. Nesta aula, encontramos duas fórmulas de recorrência. A primeira diz respeito ao valor da soma dos ângulos internos de um polígono convexo em função do seu número de vértices. A segunda trata sobre o número de diagonais de um polígono convexo.

Ensinamos um jogo conhecido como a Torre de Hanói. Neste jogo, há três hastes e uma pilha com um certo número de discos empilhados em uma das hastes. O jogo consiste em transferir, utilizando a menor quantidade de movimentos possíveis, todos os discos da haste original para alguma outra haste, obedecendo determinadas regras. Utilizamos a ideia de recorrência para encontrar uma relação em que a quantidade mínima de movimentos para ganhar o jogo com n discos deve satisfazer.

Apresentamos o problema da Pizza de Steiner: Qual é o maior número de regiões em que se pode dividir o plano com n retas? A Pizza de Steiner fornece um novo exemplo de como podemos encontrar recorrências.

Nesta aula, encontramos uma equação de recorrência para a seguinte questão: De quantas formas diferentes podemos cobrir um tabuleiro 2xn usando peças de dominó? Surpreendentemente, a fórmula encontrada é uma recorrência bastante famosa.

Após apresentarmos diversos problemas que podem ser entendidos utilizando recorrências, iniciamos um estudo mais aprofundado de tipos especiais de recorrência. Nesta aula, introduzimos as recorrências lineares de primeira ordem e mostramos dois exemplos de como encontrar uma fórmula fechada para recorrências deste tipo, isto é, de apresentar o n-ésimo termo como uma função apenas de n, sem fazer menção aos termos anteriores. Os exemplos apresentados são uma progressão aritmética e uma progressão geométrica que apareceram anteriormente na aula "Exemplos iniciais de recorrências".

Utilizando as ideias da aula anterior, nós encontramos fórmulas fechadas para alguns dos problemas apresentados anteriormente: a soma dos ângulos internos de um polígono, o número de diagonais de um polígono e o problema da Pizza de Steiner. Isto é possível porque as recorrências de cada um destes problemas são de um tipo especial de recorrência de primeira ordem, em que o n-ésimo termo é dado pelo termo anterior mais uma função de n.

Nesta aula, tratamos as recorrências lineares de primeira ordem em que o próximo termo da sequência é igual a uma constante vezes o termo anterior mais uma outra constante. A técnica que desenvolvemos nas últimas aulas ainda funciona, mas precisamos trabalhar um pouco mais para conseguir os cancelamentos necessários. Com isto, conseguimos encontrar uma fórmula fechada para o problema da Torre de Hanói, apresentado em uma aula anterior.

Desenvolvemos uma nova técnica para encontrar fórmulas fechadas para recorrências. Usando como base o formato geral de solução para uma recorrência linear com coeficientes constantes de primeira ordem, conseguimos encontrar a solução para uma recorrência linear de segunda ordem e coeficientes constantes.

Nesta aula, utilizamos o método que desenvolvemos na aula anterior para encontrar uma fórmula fechada para o n-ésimo termo da sequência de Fibonacci. Este método funciona, pois a recorrência que define a sequência de Fibonacci é linear e homogênea de segunda ordem, e com coeficientes constantes. A fórmula encontrada é surpreendente, pois envolve potências n-ésimas de números irracionais, mas ainda assim sempre fornece números inteiros. Esta fórmula também é interessante, pois nos leva a pensar sobre qual é a forma mais útil de se expressar uma sequência, já que a sequência de Fibonacci possui uma fórmula de recorrência muito simples e uma fórmula fechada complicada.

Escrevemos, de maneira geral, qual é a fórmula fechada para uma recorrência linear de segunda ordem quando as raízes do polinômio característico são diferentes. Esta fórmula provém das técnicas que desenvolvemos nas últimas duas aulas. Além disso, fornecemos também a fórmula para quando o polinômio característico tiver uma raiz dupla.