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

clip_image002

Bem, vamos resolver este problema antes de qualquer coisa:

­­
clip_image004

Reparemos que

clip_image006

Assim, podemos reparar que, como a0,a1=1,

clip_image008

Logo,

clip_image010

Portanto,

clip_image012

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

clip_image014

clip_image016

clip_image018

clip_image020

Adaptemos aos dois valores iniciais:

clip_image022
clip_image024

clip_image026

clip_image028

clip_image030

clip_image032

Logo,

clip_image034

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

clip_image036

Tem seu termo geral da forma

clip_image038

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

clip_image040

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 clip_image036[1]. 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

clip_image042

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

clip_image044

Que, simplificando, nos dará

clip_image046

Cujas raízes são, chamemos, clip_image048

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

clip_image054

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

clip_image056

clip_image058

Mas

clip_image060

Então, só temos que conferir:

clip_image062

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

clip_image064
clip_image066

Com a0=b0=1. Prove que existe uma única constante c tal que n|can - bn| < 2.

Resolução: O enunciado nos diz que

clip_image064[1]
clip_image066[1]

Logo,

clip_image068

clip_image070

clip_image072

Fazendo a equação fundamental,

clip_image074

clip_image076

Logo,

clip_image078

clip_image080

clip_image082

clip_image084

clip_image086

clip_image088

Portanto,

clip_image090

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

clip_image092
clip_image094

Logo, como queremos

clip_image096

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

clip_image098

clip_image100

Vamos provar que

clip_image102

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

Substituindo na fórmula, obtemos

clip_image104

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

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:

clip_image108

Que é verificável

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

clip_image110

Então

clip_image112

Mas, como, para k maior que 3,

clip_image114

Então

clip_image116

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

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

clip_image118

Logo, temos que ter

clip_image120

clip_image122

clip_image124

Mas, como

clip_image126

Então

clip_image128

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 clip_image130

Assim, para n infinitamente grande,

clip_image132

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:

clip_image146

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

clip_image148

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

3 – Mostre que os termos da sequência

clip_image150

São todos quadrados perfeitos.

4 – Seja

clip_image152
clip_image154

Prove que, se 2k divide an, então 2k 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 .

Comentários

Postar um comentário

Você pode comentar! A equipe do blog encoraja todos a comentar.

Porém, lembre-se que comentários que desrespeitem as regras abaixo serão excluídos:

-É proibido ofender qualquer pessoa ou grupo em seu comentário.
-Os comentários deverão ser minimamente relacionados com o tópico. Lembrem-se, estamos falando de um blog de matemática!
-Proibido flood.
-Proibido palavras de baixo calão.
-Proibido colocar qualquer tipo de conteúdo improprio para menores de 18 anos (há menores de idade que acessam o blog).

A equipe do blog agradece seu comentário, e tenha certeza que será muito enriquecedor. Tentaremos respondê-los o quanto antes possível.