Pensando Sobre Matemática #52 - Recorrência

Uma vez nesse blog eu comentei sobre o P.I.F.

Cuidado! Esse post necessita de Javascript pois hoje usaremos o MathJax!

Se você perdeu o post sobre o P.I.F., fique tranquilo pois ele não é estritamente necessário, mas saiba que ele está intimamente ligado com o que vamos falar agora. Ah sim, outra coisa que também está intimamente ligada são as sequências matemáticas. Só que a sequência é muito fácil de definir.

Sequência: Lista ordenada de elementos.

Sério, isso é uma sequência, eis aqui uma sequência simples e uma sequência mais abstrata. $$A=\{1,4,9\}$$ $$B=\{a_0,a_1,a_2\}$$ O que eu quero dizer com isso é que sequências não necessariamente tem padrões, exceto aquelas que nos interessam. Existem duas coisas das quais nós gostamos: Sequências com padrões, e procurar padrões em sequências ainda sem padrão; e um dos casos mais famosos são as sequências que possuem relações de recorrência, que são relações entre os próprios elementos da sequência que permitem que você tenha um padrão, e dessa forma consiga prever o próximo elemento. Com um pequeno custo associado.

Você precisa conhecer alguns elementos da sequência antes.

Relações de recorrência aparecem quando começamos a estudar progressões, sabe-se que os elementos da progressão aritmética diferem de uma razão r, Oras, nós podemos definir todos os elementos seguintes a partir do primeiro através da seguinte relação de recorrência: $$a_{n+1}=a_n+r$$ Mas note que pra definir todos os outros você precisa saber um cara: $$a_1$$ Que é o termo inicial da progressão.

As relações de recorrência ficaram mais famosas quando surgiu a sequência de Fibonacci. Saudosa sequência de Fibonacci. Eu irei dedicar um post inteiro a ela, mas o que eu quero dizer agora, é que as relações de recorrência podem usar mais de um elemento inicial. Por exemplo uma relação simples que usa ao inves do elemento diretamente anterior, mas sim um elemento que está a dois passos atrás: $$a_{n+2}=a_n+r$$ Você precisa de dois elementos iniciais. Nesse caso você até pode quebrar em duas sequências diferentes, mas é bem possível que a sua relação de recorrência use mais de um elemento anterior como por exemplo: $$a_{n+2}=2a_{n+1}-a_n$$ E daí nós vamos precisar de dois elementos para continuar escrevendo a sequência.

Legal, mas pra que serve isso? Recorrência é uma forma natural de modelar padrões da natureza. São coisas que ocorrem naturalmente, geralmente associa-se a relação de Fibonacci a reprodução de espécies, mas certamente existem muito mais exemplos dela.

Outro uso das relações de recorrência está na programação. Na verdade, quase tudo que você faz na computação é suprtado graças a recorrência. No paradigma de programação funcional, a única forma de você fazer loops é através da relação de recorrência com uma técnica chamada de recursão.

Acho que isso é tudo para falar sobre recorrência por enquanto!