Escrito por Samuel Prieto
Recorrências Lineares: Um guia prático
Em vários problemas precisamos encontrar a forma fechada de um sequencia construida por uma regra em função dos termos anteriores, por exemplo:
\[a_1=1 , a_2=2 , a_n = a_{n-1}+2a_{n-2} , \forall n\ge2\]
sequencias em que cada termos é uma cobinação linear dos anteriores são chamadas de lineares, e para resolve-las ultilizmos do seguinte método:
1º Passo : Encontrar a equação característica.
uma equação linear tem grau d se cada termo é obtido a partir de uma combinação de d termos anteriores (nosso exemplo tem grau 2). Vamos trabalhar com equações de grau 1 ou 2 apenas. Um fato chave é que uma sequencia de grau n pode ser representado com a soma de n sequencias exponenciais, ou seja, no nosso exemplo existem A, B , C e D tais que :
\[ a_n=C.A^n +D.B^n, \forall n\ge 0 \]
Mas como encontrar A e B? simples, eles são as raízes da chamada Equação característica da sequencia , obtida substituindo $$a_n$$ por $$x^n$$ na equação de recorrência. no exemplo temos:
\[\rightarrow a_n = a_{n-1}+2a_{n-2}\]
\[\rightarrow x^n = x^{n-1} + 2x^{n-2}\]
\[\rightarrow x^2=x+2\]
\[\rightarrow x^2 – x – 2 =0\]
2º Passo : Encontrar suas raízes
\[\rightarrow x^2 – x – 2 =0\]
\[\rightarrow (x-2)(x+1)=0\]
$$\rightarrow x=2$$ ou $$x=-1$$
Logo temos $$A=2$$ e $$B=-1$$, agora para encontrar as constantes C e D, precisamos olhar para os valores iniciais da sequência…
3º Passo: Ajustar as constantes
Sabemos que $$a_1=A^1.C+B^1.D$$ e $$a_2=A^2.C+B^2.D$$ ,logo com já conhecemos os valores de $$a_1,a_2,A$$ e $$B$$, podemos resolver o seguinte sistema de duas equações em C e D, no noso exemplo temos:
\[(2)^1C+(-1)^1D=1\]
\[(2)^2C+(-1)^2D=2\]
Resolvendo encontramos $$C=\frac{1}{2}$$ e $$D=0$$
4º Passo: Provar que funciona (Indução) :
Apesar de este método ser bem conhecido, é necessário provar que a formula encontrada funciona, mas isso é bem direto usando indução. Formalmente falando , vamos propor que $$a_n=C.A^n+D.B^n$$ é uma formula que descreve todos $$a_n$$ corretamente. De volta para nosso exemplo:
Casos Iniciais: para n=1, \[a_1=\frac{1}{2}.(2)^1+0.(-1)^1=1\], que é verdade
para n=2, \[a_2=\frac{1}{2}.(2)^2+0.(-1)^2=2\], que é verdade
Hipótese: $$\forall n\ge m\ge 1,a_m=\frac{1}{2}.(2)^m+(0).(-1)^m=2^{m-1}$$, vamos provar que $$a_{n+1}=\frac{1}{2}.(2)^{n+1}+(0).(-1)^{n+1}=2^{n}$$
temos \[a_{n +1}= a_n+2a_{n-1}\]
\[\rightarrow a_{n+1}=(\frac{1}{2}.2^n)+2(\frac{1}{2}.2^{n-1})=2^{n-1}+2.2^{n-2} (*) \]
\[=2^{n-1}+2^{n-1}=2^n\]
Logo a indução está completa e está provada nossa fórmula:)
Vale a pena lembrar de o porque a igualdade (*) ocorreu: nesse caso é bem facil observar que a soma de duas potencias de dois é uma potência de dois, mas por que nos tomamos A e B como as raízes da nossa equação caracteristica, sempre poderemos substituir o resultado do lado esquerdo pelas próxima potências de A e B, mas isso ficará mais claro nos exemplos a seguir:
Problemas:
1.(Sequencia de Fibonacci)Seja $$f_0,f_1,f_2…$$ uma sequência de números reais definida por $$f_0=0,f_1=1, f_{n+2}=f_{n+1}+f_{n}$$. Encontre a fórmula fechada de $$f_n$$
2.Seja $$a_0,a_1,a_2…$$ uma sequência de números reais definida por $$a_0=1$$ e $$a_{n+1}=2a_n+1,\forall n \ge 0$$. Encontre a fórmula fechada de $$a_n$$.