Recorrências

Introdução

Uma das mais poderosas técnicas de contagem é a chamada recorrência (ou recursão), isto é, uma sequência que associa cada termo com seus termos anteriores. Nesse artigo te apresentaremos algumas técnicas para descobrir o termo geral de uma recorrência e problemas para que você pratique o que aprendeu. Observe a seguir algumas maneiras de resolver uma recorrência.

Soma/Produto telescópico

Consiste basicamente em escrever diversas equações que relacionam termos da sequência e somar/multiplicar todas para que alguns termos se cancelem. Por exemplo, seja $a_0=1$ e $a_n=a_{n-1}+5$ .

Então

$a_1=a_0+5$

$a_2=a_1+5$

$a_3=a_2+5$

$\dots$

$a_n=a_{n-1}+5$

Somando todas, obtemos $a_n=a_0+5n=5n+1$ .

Equação característica

Como explicado neste material do POTI, dada uma recorrência homogênea linear com coeficientes constantes, podemos descobrir o termo geral ao calcular as raízes da equação característica. Isso é particularmente útil com recorrências de grau menor ou igual a $2$ . Em geral, dada a recorrência $c_na_n+c_{n-1}a_{n-1}+\dots+c_ka_k=0$ , onde $c_n, c_{n-1},\dots, c_k$ são coeficientes constantes e $k<n$ , sua equação característica será:

$c_n\lambda^{n-k}+c_{n-1}\lambda^{n-1-k}+\dots+c_{k+1}\lambda+c_k=0$

Solução de recorrências de 2ª ordem com a equação característica

Dada uma recorrência $xa_n+ya_{n-1}+za_{n-2}=0$ , sua equação característica será:

$x\lambda^2+y\lambda+z=0\Rightarrow\lambda^2+\dfrac{y}{x}\lambda+\dfrac{z}{x}=0$ com raízes $\lambda_1$ e $\lambda_2$

Podemos escrever (verifique!):

$a_n=A\lambda_1^n+B\lambda_2^n$

onde $A$ e $B$ são constantes que podemos descobrir usando valores de $a_n$ (geralmente $a_0$ e $a_1$ são os mais simples).

Exemplos

1. Encontre a quantidade de subconjuntos de $\{1, 2, \dots, n\}$ não vazios sem números consecutivos.

Solução

Seja $a_k, 1\leq k\leq n$ o número de subconjuntos contendo $k$ como o maior elemento e que não contém elementos consecutivos.

Note que $a_k=a_{k-2}+a_{k-3}+\dots+a_1+1~\forall k>1$ (adicione $k$ a cada um dos subconjuntos contados em $a_i~1\leq i\leq k-2$ e o conjunto que contém apenas $k$ ). Assim $a_k - a_{k-1}=a_{k-2}\iff a_k=a_{k-1}+a_{k-2}~\forall k>2$ .

Como $a_1=a_2=1$ e $a_k=a_{k-1}+a_{k-2}$ , $a_k=F_k$ onde $F_k$ é o k-ésimo termo da sequência de Fibonacci.

Assim, a quantidade de subconjuntos de $\{1, 2, \dots, n\}$ sem números consecutivos é $F_1+F_2+\dots+F_n$ , que pode ser calculada telescopicamente:

$F_1=F_3-F_2$

$F_2=F_4-F_3$

$\dots$

$F_n=F_{n+2}-F_{n+1}$

Somando todas, obtemos $F_1+F_2+\dots+F_n=F_{n+2}-F_2=\boxed{F_{n+2}-1}$ .

2 (Teste Cone Sul Brasil). Maria tem $14$ dias para se preparar para uma olimpíada. Se ela treina $3$ dias seguidos, terá fadiga muscular. Mas, se ela não treina por $3$ dias seguidos, terá atrofia muscular. Ela então decide planejar quais dias, dentre os $14$ , ela irá treinar, e quais não irá treinar, de modo que ela nunca treine $3$ dias seguidos nem fique sem treinar $3$ dias seguidos. De quantas maneiras diferentes Maria pode montar seu plano de treino?

Solução

Considere o plano de treino como uma sequência de letras $A$ e $B$ , de modo que $A$ representa os dias que ela treinará e $B$ os dias que não treinará.

Seja $X(n)$ a quantidade de sequências possíveis com $n$ letras e $X_{YZ}(n)$ a quantidade de sequências possíveis com $n$ letras que terminam em $YZ$ .

Então $X(1)=2$ , $X(2)=4$ , para $n>0$ ,

$X(n)=X_{AA}(n)+X_{BB}(n)+X_{AB}(n)+X_{BA}(n)$ (1)

$X_{AA}(n)=X_{BA}(n-1)$ (2)

$X_{BB}(n)=X_{AB}(n-1)$ (3)

$X_{AB}(n)=X_{BA}(n-1)+X_{BB}(n-1)$ (4)

$X_{BA}(n)=X_{AB}(n-1)+X_{AA}(n-1)$ (5).

Substituindo (2), (3), (4) e (5) em (1) obtemos para $n>2$

$X(n)=X_{AA}(n-1)+X_{BB}(n-1)+2X_{AB}(n-1)+2X_{BA}(n-1)$

$\iff X(n)=X(n-1)+X_{AB}(n-1)+X_{BA}(n-1)$

$\iff X(n)=X(n-1)+X_{BA}(n-2)+X_{BB}(n-2)+X_{AB}(n-2)+X_{AA}(n-2)$

$\iff X(n)=X(n-1)+X(n-2)$ .

Assim, obtemos $X(14)=1220$ e portanto Maria pode organizar seus treinos de $1220$ maneiras.

3 (Cone Sul/2017). Seja $n$ um inteiro positivo. Tem-se um tabuleiro quadriculado $4\times4n$ dividido em casinhas $1\times1$ , e $4n$ peças como a que se mostra na figura abaixo. Determinar de quantas maneiras se pode cobrir totalmente o tabuleiro com essas peças.

Solução

Seja $a_n$ a quantidade de maneiras para cobrir um tabuleiro $4\times 4n$ . Então $a_1=2$ .

Considere, sem perda de generalidade que a casa $1$ é coberta da seguinte maneira (a outra maneira seria apenas uma reflexão):

Assim as casas $2$ e $3$ só podem ser cobertas como mostrado e a casa $4$ pode ser coberta das seguintes formas:

(1)

Neste caso, podemos cobrir o resto do tabuleiro de $a_{n-1}$ maneiras.

(2)

Neste caso não é possível cobrir a casa $5$ .

(3)

Neste caso as casas $5$ , $6$ e $7$ só podem ser cobertas como mostrado e obtemos a mesma configuração que tínhamos para cobrir a casa $4$ , portanto podemos colocar uma peça e cobrir o resto do tabuleiro de $a_{n-2}$ maneiras como em (1) ou continuar como em (2) e assim obter $a_{n-3}+a_{n-4}+\dots+a_1$ maneiras.

Combinando as informações de (1), (2) e (3) obtemos $a_n=2(a{n-1}+a_{n-2}+\dots+a_1)~\forall n>1$ .

Assim, para $n>1$ obtemos

$a_n=2(a_{n-1}+a_{n-2}+\dots+a_1)$ (*)

$a_{n-1}=2(a_{n-2}+a_{n-3}+\dots+a_1)$ (**)

Fazendo (*) $-$ (**) obtemos $a_n-a_{n-1}=2a_{n-1}$

$\iff a_n=3a_{n-1}=3\cdot 3a_{n-2}=\dots=3^{n-1}a_1=$

$\iff \boxed{a_n=3^{n-1}\cdot2}$

4 (Sequência de Fibonacci). Dado que $F_1=F_2=1$ e que $F_{n+1}=F_n+F_{n-1}$ , encontre $F_n$ em função de $n$ .

Solução

Como temos que $F_{n+1}-F_n-F_{n-1}=0$ é uma recorrência de 2a ordem, podemos resolvê-la usando a sua equação característica. Como vimos acima, a equação característica da Sequência de Fibonacci será:

$\lambda^2-\lambda-1=0$ com raízes $\phi$ e $\bar\phi$

Escrevendo $F_n=A\phi^n+B\bar\phi^n$ temos:

$F_2-F_1=0=F_0=A+B\Rightarrow B=-A$

e ainda:

$F_1=1=A\phi+B\bar\phi$

$\Rightarrow A(\phi-\bar\phi)=1$

$\Rightarrow A=-B=\dfrac{1}{\sqrt5}$

Assim, temos que:

$F_n=\dfrac{1}{\sqrt5}\left( \dfrac{1+\sqrt5}{2} \right)^n-\dfrac{1}{\sqrt5}\left( \dfrac{1-\sqrt5}{2} \right)^n$

Problemas

Abaixo há uma lista de problemas desafiadores para treinar suas habilidades. Recomendamos que tente todos os problemas e olhe as dicas (depois de tentar resolver sem), antes de buscar uma solução. Os problemas estão, no geral, em ordem de dificuldade, da menor para a maior.

1. Dado um tabuleiro $2\times 2n$ , de quantas formas podemos cobri-lo usando apenas peças $2\times 1$ ?

Dica

Quais são as possíveis posições dos dominós no primeiro quadrado $2\times 2$ do tabuleiro da esquerda pra direita?

2 (EGMO/2020). Uma permutação dos inteiros $1$ , $2$ , $\dots$ , $m$ é chamada fresh se não existe inteiro positivo $k<m$ tal que os $k$ primeiros números na permutação são $1$ , $2$ , $\dots$ , $k$ em alguma ordem. Seja $f_m$ o número de permutações fresh dos inteiros $1$ , $2$ , $\dots$ , $m$ . Prove que $f_n\geq n\cdot f_{n-1}$ para todo $n\geq 3$ . Por exemplo, se $m = 4$ , então a permutação $(3,1,4,2)$ é fresh, enquanto a permutação $(2,3,1,4)$ não é fresh.

Dica

Associe cada permutação fresh dos inteiros $1$ , $2$ , $\dots$ , $n-1$ com pelo menos $n$ permutações fresh dos inteiros $1$ , $2$ , $\dots$ , $n$ .

3 (SO 2001). Seja $f(n)$ o número de sequências ternárias (apenas com números $0$ , $1$ e $2$ ) de tamanho $n$ em que não existem $0$ 's vizinhos. Encontre $f(n)$ em função de $n$ .

Dica

Tente construir cada sequência dividindo em $3$ casos: quando ela começa com $0$ , com $1$ e com $2$ . Construa a recorrência a partir disso.

4. As cidades A, B, C e D estão conectas por estradas, todas com $10$ km de comprimento. João planeja fazer uma viagem saindo da cidade A e andando pelas estradas passando pelas cidades para que enfim chegue de volta à cidade de onde partiu.

Porém, ele planeja andar exatamente $10n$ km. De quantas formas ele consegue fazer isso?

Dica

Observe o que ocorre quando no $10(n-1)$ -ésimo quilômetro João está na cidade A. Relacione isso com o número de caminhos válidos que João tem para $10(n-1)$ km e gere a recorrência a partir disso.

5 (USAJMO/2018). Para cada inteiro positivo $n$ , encontre a quantidade de inteiros positivos com $n$ dígitos que satisfazem ambas as condições:

não tem dígitos consecutivos iguais;
o último dígito é um número primo.

Dica

Considere os seguintes casos e defina uma recorrência:

O segundo dígito é diferente de $0$ ;

O segundo dígito é igual a $0$ .

6 (OBM/2004). Considere $a_n$ um sequência de reais definida por: $a_0=a_1=a_2=a_3=1$ e $a_na_{n-4}= a_{n-1}a_{n-3} + a_{n-2}^2$ . Prove que todos termos da sequência são inteiros.

Dica

Prove por indução que: $mdc(a_n,a_{n+1})=mdc(a_n,a_{n+2})=mdc(a_n,a_{n+3})=mdc(a_n,a_{n+4})=1$ . Isso vai facilitar quando você tentar provar por indução que: $a_{n-4}| a_{n-1}a_{n-3} + a_{n-2}^2$ que é equivalente a provar que $a_n$ é inteiro.