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.
[spoiler title=’Solução’ style=’white’ collapse_link=’false’]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}$$.[/spoiler]
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?
[spoiler title=’Solução’ style=’white’ collapse_link=’false’]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.[/spoiler]
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.
[spoiler title=’Solução’ style=’white’ collapse_link=’false’]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}$$
[/spoiler]
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$$.
[spoiler title=’Solução’ style=’white’ collapse_link=’false’] 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$$
[/spoiler]
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$$?
[spoiler title=’Dica’ style=’white’ collapse_link=’false’]Quais são as possíveis posições dos dominós no primeiro quadrado $$2\times 2$$ do tabuleiro da esquerda pra direita?[/spoiler]
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.
[spoiler title=’Dica’ style=’white’ collapse_link=’false’]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$$.[/spoiler]
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$$.
[spoiler title=’Dica’ style=’white’ collapse_link=’false’]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.[/spoiler]
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?
[spoiler title=’Dica’ style=’white’ collapse_link=’false’]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.[/spoiler]
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.
[spoiler title=’Dica’ style=’white’ collapse_link=’false’]Considere os seguintes casos e defina uma recorrência:
O segundo dígito é diferente de $$0$$;
O segundo dígito é igual a $$0$$.[/spoiler]
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.
[spoiler title=’Dica’ style=’white’ collapse_link=’false’]
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.
[/spoiler]