Recorrências

Nestes problemas estamos interessados em descobrir termos de um sequência conhecendo os anteriores.

Exemplo (Cone Sul 2001 - Adaptada)

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$

Exemplo (Cone Sul 2001)

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