FANDOM


Em certas sequências $ (a_n) $ os termos $ a_n $ são dados em função de teremos anteriores. Em outras palavras, existe uma certa função $ f $ tal que

$ a_n=f(a_{n-1},a_{n-2},\dots,a_{n-p}). $

A igualdade acima é chamada de relação de recorrência (ou simplesmente de recorrência). Nela, $ p $ pode ou não depender de $ n $. Para podemos completar a sequência é preciso que saibamos os $ p $ primeiros termos $ a_1,a_2,\dots,a_p $.

Recorrências Lineares com Coeficientes Constantes e $ p $ independente de $ n $Editar

Estas expressões são da forma:

$ a_{n+1}=c_1a_{n-1}+c_2a_{n-2}+\dots+c_pa_{n-p}, $

onde $ c_1,c_2,\dots,c_p $ são constantes.

Exemplo (Cone Sul 2001 - Adaptada) Editar

Tem-se uma sucessão $ a_1,a_2,a_3,\dots,a_n,\dots $ de números inteiros positivos, com as seguintes propriedades:

(i) $ a_1=1 $

(ii) $ a_{3n+1} = 2a_n+1 $

(iii) $ a_{n+1} \geq a_n $

(iv) $ a_{2001}=200 $

Calcule o valor de $ a_{1000} $.

Solução: Vamos usar que $ a_1 $ e utilizar a condição (ii) sucessivamente, para encontrarmos valores de $ a_i $ para $ i $ próximo de $ 1000 $. Observe que

$ a_4=a_{3.1+1}=2a_1+1=3 $

$ a_{13}=a_{3.4+1}=2a_4+1=7 $

$ a_{40}=a_{3.13+1}=2a_{13}+1=15 $

$ a_{121}=a_{3.40+1}=2a_{40}+1=31 $

$ a_{364}=a_{3.121+1}=2a_{121}+1=63 $

$ a_{1093}=a_{3.364+1}=2a_{364}+1=127. $

Mas queremos falar sobre $ a_{1000} $ e não sobre $ a_{1093} $. E agora? Observe que podemos usar (iii) para mostrarmos que se $ m \geq n $, então $ a_m \geq a_n $. Desta forma, $ a_{1000} \leq a_{1093}=127 (*) $.

Seria interessante se tivéssemos outro valor de $ a_i $ para podermos repetir o mesmo raciocínio e concluir mais coisas sobre $ a_{1000} $. O único valor que temos é $ a_{2001} $. Mas ele é muito grande. Seria legal se tivéssemos um número pequeno. Façamos então $ a_3=k $. Desta forma,

$ a_{10} = a_{3.3+1}=2a_3+1=2k+1 $

$ a_{31} = a_{3.10+1}=2a_{10}+1=4k+3 $

$ a_{94} = a_{3.31+1}=2a_{31}+1=8k+7 $

$ a_{283} = a_{3.94+1}=2a_{94}+1=16k+15 $

$ a_{850} = a_{3.283+1}=2a_{283}+1=32k+31 $

$ a_{2561} = a_{3.850+1}=2a_{850}+1=64k+63 $

Vamos comparar com $ a_{2001} $. Observe que $ 64k+63 = a_{2561} \geq a_{2001}=200 $, de onde segue que $ k \geq 3 $. Conseguimos encontrar mais informações sobre $ k $? Vamos comparar $ a_3 $ com algum conhecido. Observe que

$ k=a_3 \geq a_4=3. $

Desta forma, $ k=3 $.

Agora já temos condições de calcular $ a_{1000} $. Observe que $ a_{1000} \geq a_{850}=32k+31=127(**) $. Se compararmos $ (*) $ e $ (**) $, poderemos concluir que $ a_{1000}=127 $.

Recorrências Lineares de Ordem $ 1 $Editar

Exemplo (Cone Sul 2001) Editar

Seja $ g $ uma função definida para todo inteiro positivo $ n $, que satisfaz

(i) $ g(1)=1 $

(ii) $ g(n+1)=g(n)+1 $ ou $ g(n+1)=g(n)-1 $ para todo $ n \geq 1 $

(iii) $ g(3n)=g(n) $ para todo $ n \geq 1 $

(iv) $ g(k)=2001 $ para algum inteiro positivo $ k $.

Ache o menor valor possível de $ k $ entre todas as funções $ g $ que cumprem as condições anteriores e demonstre que é o menor.

Solução: Considere $ a_k $ o menor inteiro positivo tal que, dentre todas as funções $ g $ que satisfazem as condições do enunciado, vale que $ g(a_k)=k $. Queremos determinar $ a_{2001} $. Por que fizemos esta definição? Para podermos entender os pequenos casos.

Como $ g(1)=1 $, segue que $ a_1=1 $. Por (ii), $ g(2)=0 $ ou $ g(2)=2 $. Dentre essas, a que nos dá o menor $ t $ tal que $ g(t)=2 $ são aquelas em que $ g(2)=2 $. Com isso, $ a_2=2 $. Aliás, estas são as funções $ g $ que nos ajudará a descobrir outros valores de $ a_k $. Observe que, por (iii),

$ g(3)=g(1)=1, $

$ g(6)=g(2)=2. $

Para encontrarmos outros valores de $ a_k $, por (ii), podemos tomar $ g(4)=2 $ e $ g(5)=3 $. Com isso, $ a_3=5 $. Da mesma forma, podemos descobrir que $ a_4=14 $. Se observarmos estes pequenos casos, parece que $ a_{n+1}=3a_n-1 $.

Como podemos mostrar isto? Basta vermos que $ g(3a_n-1)=n+1 $ e $ g(k) \leq n $ para todo $ k < 3a_n-1 $.

Pela definição de $ a_n $, podemos dizer que $ g(k) \leq n-1 $.

Mas como usar desigualdades aqui envolvendo $ g $? Observe que, pela condição (ii),

$ g(n+1) \leq g(n)+1. $

Já sabemos que $ g(3k)=g(k) $. Dá para falar sobre números da forma $ 3k+1 $ e $ 3k+2 $?

Observe que, por (ii) e (iii),

$ g(3k+1) \leq g(3k)+1=g(k)+1. (*) $

Além disso, por (ii) e (iii) novamente,

$ g(3k+2)-1 \leq g(3k+3)=g(3(k+1))=g(k+1), $

de onde segue que

$ g(3k+2) \leq g(k+1)+1.(**) $

Podemos usar $ (*) $ e $ (**) $ (combinado com (iii)) para mostrar que $ g(k) \leq 3 $ para $ k \leq 12 $.

Qual a vantagem de podermos mexer com números desta forma? Se observarmos que para todo $ t \leq a_n-1 $ vale que

$ g(3t)=g(t) \leq n-1 $

$ g(3t+1) \leq g(t)+1 \leq n-1+1=n $

$ g(3(t-1)+2) \leq g(t)+1 \leq n-1+1-n, $

então provaremos que $ g(t)\leq n $ para todo $ t \leq 3a_n-2 $.

Aliás, notemos que $ g(3a_n-3)=g(3(a_n-1))=g(a_n-1)=n-1 $. Por que isto vale? Como $ g(a_n)=n $, por (ii), segue que $ g(a_{n-1})=n-1 $ ou $ n+1 $. Assim $ g(a_{n-1})=n-1 $.

Podermos tomar $ g(3a_n-2)=n $ e $ g(3a_n-1)=n+1 $.

Desta forma, $ a_{n+1}=3a_n-1 $. Para finalizarmos, basta resolvermos esta congruência. Observe que quase temos uma progressão geométrica. Seria legal se tivéssemos uma coisa da forma

$ b_n=3b_{n-1}. $

Para isto, somemos algum número em ambos os lados. Qual? Vamos descobrir. Chamemos ele de $ x $. Então

$ a_{n+1}+x=3a_{n-1}+x-1 \Leftrightarrow a_{n+1}+x=3(a_n+\frac{x-1}{3}). $

Para termos o que queremos, precisamos que

$ x=\frac{x-1}{3} \Leftrightarrow x=-\frac{1}{2}. $

Desta forma,

$ a_{n+1}-\frac{1}{2}=3(a_n-\frac{1}{2}). $

Para $ b_n=a_n-\frac{1}{2} $ a igualdade acima se torna

$ b_{n+1}=3b_n. $

Aqui $ b_n $ é uma progressão geométrica de razão $ 3 $. Com isso, $ b_n=b_1.3^{n-1} $. E quanto a $ b_1 $? Observe que

$ b_1=a_1-\frac{1}{2}=1-\frac{1}{2}=\frac{1}{2}. $

Assim,

$ b_n=\frac{3^{n-1}}{2} \Leftrightarrow a_n=\frac{3^{n-1}+1}{2} $.

Com isso, $ a_{2001}=\frac{3^{2000}+1}{2} $.