Sequências e Progressões: Parte 3 – Recursões Lineares Homogêneas.

As relações de recursão são muito importantes, tanto para problemas de álgebra, quanto para problemas de combinatória. Neste post, vamos demonstrar uma das relações mais importantes quando falamos de recursões: a fórmula para resolução de recursões lineares homogêneas. Porém, antes retomaremos aquela história do post sobre sequências e progressões (caso não tenha visto os dois posts, clique aqui e aqui.), aquela discussão que fizemos sobre as sequências definidas por fórmula fechada ou por relação de recorrência.

Como falamos no primeiro dos posts, perguntamos como problema adicionar se era possível encontrar uma fórmula fechada para

Bem, vamos resolver este problema antes de qualquer coisa:

­­

Reparemos que

Assim, podemos reparar que, como a₀,a₁=1,

Logo,

Portanto,

Agora, utilizaremos nosso teorema a demonstrar: a equação característica da recursão linear homogênea.

Adaptemos aos dois valores iniciais:

Logo,

Que é a fórmula fechada que desejamos.

Nesse momento, você pode estar se perguntando: Mais que droga é esse tal de teorema? Que equação característica? Não entendo mais nada!

Calma, eu digo: enunciemos direitinho o teorema. Mas antes, precisaremos da

Definição 1: Uma relação de recorrência linear homogênea é aquela na qual os termos são apenas multiplicados por constantes, sem expoentes.

Por exemplo, nossa relação não parecia ser uma dessas. Porém, assim que modificamos um pouco as coisas, tudo se esclareceu. Mas, pra que saber o que é uma recursão linear homogênea se não sabemos resolvê-la? Bom, é isso que queremos! Resolvê-la. É isso que nos ensinará o seguinte

Teorema 1: Uma relação de recorrência linear da forma

Tem seu termo geral da forma

A,B constantes dadas pelos termos iniciais da recorrência, e q, q₂ soluções da equação característica em t

Demonstração: Confesso, ao escrever essa demonstração, me deparei com algumas dificuldades: o tema recursão não é muito abordado antes do cálculo diferencial, enquanto, em países como Inglaterra e outros europeus, recursões e até Cálculo 1 são ensinados no ensino médio regular. Assim, não há uma demonstração amplamente conhecida aqui no Brasil para a fórmula fechada. Portanto, darei uma versão resumida de uma demonstração elaborada por mim.

Seja . Assim, daremos um “chute” calculado: quando observamos os termos desta progressão, parece que eles se comportam exponencialmente. Logo, devemos procurar por algum η tal que

Logo, substituindo na equação original, obteremos:

Que, simplificando, nos dará

Cujas raízes são, chamemos,

Bom, então teremos que, se as sequências definidas por , e satisfazem a relação de recorrência, então a sua soma deve satisfazer a relação. Logo, devemos ter

Onde A,B dependem dos termos iniciais. Ora, tudo muito bem, tudo muito bom, mas isto nos prova mesmo que estas sequências devem ser assim mesmo? Não! Precisamos conferir. Como? A resposta para todos os males da humanidade, postada por meu grande amigo Eduardo: INDUÇÃO! Não se desespere se você não sabe do que estamos falando: para conferir o post de indução, clique aqui.

Então, se definimos bem A,B para os dois primeiros termos, nossa base está liquidada. Agora, com nossa “exponenciação”, joguemos na recursão original

Mas

Então, só temos que conferir:

Que é verídico, portanto, concluindo a indução.

Este resultado nos diz que estamos oficialmente AUTORIZADOS a utilizar o teorema! Vamos ver alguns exemplos primários de como utilizar o teorema “mestre”.

Problema 1: Sejam duas sequências infinitas definidas por

Com a₀=b₀=1. Prove que existe uma única constante c tal que n|ca_n - b_n| < 2.

Resolução: O enunciado nos diz que

Logo,

Fazendo a equação fundamental,

Logo,

Portanto,

Então, aplicamos em (1) para obter:

Logo, como queremos

Substituímos nossas fórmulas, obtendo, assim:

Vamos provar que

Satisfaz , e que é a única que satisfaz para todos os termos.

Substituindo na fórmula, obtemos

Mas, uma verificação direta nos dá que .

Logo, pela propriedade das exponenciais, esta será, à medida que n aumenta, uma sequência decrescente, tendendo a zero,que satisfaz que ela seja menor que 2/n, como veremos mais uma vez por indução:

k=3 será nossa base:

Que é verificável

k+1 é o passo indutivo. Temos que, se supormos

Então

Mas, como, para k maior que 3,

Então

Os casos k=1,2 podem ser verificados diretamente.

Agora, quanto à unicidade desta constante, vejamos que, para n infinitamente grande,

Logo, temos que ter

Mas, como

Então

Onde r determina a razão entre um termo e seu antecessor quando os termos são suficientemente grandes. Mas ora, pela propriedade das recursões, quando n chega a um limite infinito, r chega a um limite finito, que é dado pela equação fundamental (raiz positiva). Logo, chegamos à conclusão de que

Assim, para n infinitamente grande,

Assim, as constantes que satisfazem a condição tendem ao limite de raiz de 3, que é a única constante que se adéqua para todos os n.

Agora, que tal alguns problemas?

Problemas sobre Recorrências – Nem sempre é preciso utilizar o Teorema

1 – Ache uma fórmula geral e fechada para a seguinte recorrência:

2 – Mostre que, dada a sequência definida por dois termos iniciais arbitrários a,b e pela fórmula

E que a soma dos n primeiros termos é S_n, mostre que S_n +u_n-1 é uma constante independente de n, calculando-a.

3 – Mostre que os termos da sequência

São todos quadrados perfeitos.

4 – Seja

Prove que, se 2^k divide a_n, então 2^k divide n.

LEMBRE-SE: Para que saibamos como estamos indo na nossa tarefa no blog, avalie o post aqui em baixo. É rapidinho, não demora nem 3 segundos. Se quiser participar enviando seu comentário, sinta-se livre. Convidamos você, leitor, a dar soluções aos problemas propostos, enviando-as por comentários ou para o e-mail joaopedroblogger@hotmail.com .