MATERIAL OBMEP - RECORRÊNCIA

Escrito por João Rafael e João Ferreira.

Introdução

Recorrências não são tão comuns em provas da OBMEP quanto outros assuntos, mas quando estão na prova são questões desafiadoras, por isso trouxemos esse material pra você. Note que como é um assunto que geralmente necessita de certa noção teórica esse artigo será de nível mais avançado para a OBMEP. Recorrências consistem em usar casos anteriores para definir ou descobrir algo sobre o caso atual de uma sequência ou construção. Abaixo segue uma lista de teoria e de problemas de treinamento relacionados ao tema. Tente resolver todos eles antes de ir para as dicas e soluções no final do material e divirta-se!

Recorrências de primeira ordem

São um tipo de recorrência em que cada termo é definido com base no termo exatamente anterior a ele.

Ex: A sequência dos números ímpares positivos onde o $n$-ésimo número ímpar é definido como $a_n=a_{n-1}+2$ e $a_1=1$.

Ex: Uma progressão aritmética em que o $n$-ésimo termo é definido por $a_n=a_{n-1}+r$.

Ex: Uma progressão geométrica em que o $n$-ésimo termo é definido por $a_n=a_{n-1}q$.

Estratégias para achar o $a_n$ em função do $a_1$:

Em recorrência de primeira ordem basicamente sempre conseguimos achar um termo geral usando produtos ou somas telescópicas(nome bonito para somar ou multiplicar várias vezes termos da sequência formada).

Ex$_1$: Ache o termo geral de uma progressão aritmética(P.A) de razão 5 e $a_1=2$

Solução: Seja $a_n$ o $n$-ésimo termo dessa P.A. Sabemos que:

$\begin{cases}a_n=a_{n-1}+5 \\ a_{n-1}=a_{n-2}+5 \\ \vdots \\ a_3=a_2+5 \\ a_2=a_1+5\end{cases}$ $\underbrace{\Rightarrow}_{somando}$ $a_n+a_{n-1}+a_{n-2}+\dots+a_2=a_{n-1}+a_{n-2}+\dots+a_2+a_1+\underbrace{5+5+\dots+5}_{n-1 vezes}\Rightarrow a_n=a_1+(n-1)5$ $\blacksquare$

Ex$_2$: Encontre o termo geral da recorrência gerada pela relação $a_n=na_{n-1}$ em função de $a_1$ e $n$.

Solução: Sendo $a_n$ um termo qualquer da sequência, temos:

$\begin{cases}a_n=na_{n-1} \\ a_{n-1}=(n-1)a_{n-2} \\\vdots \\ a_3=3a_2 \\ a_2=2a_1\end{cases}$ $\underbrace{\Rightarrow}_{multiplicando}$ $a_na_{n-1}\dots a_2=a_{n-1}\dots a_2a_1\times n\times n-1\times\dots\times2\times1\Rightarrow a_n=n!\times a_1$ como queriamos. $\blacksquare$

Nos Ex$_1$ e Ex$_2$ nos utilizamos somas e produtos telescópicos, respectivamente. Agora, exercite um pouco dessa ideia:

Exercícios:

$1.$(EUA) Os quatro primeiros termos de uma P.A. são $a$, $x$, $b$, $2x$. Determine o valor da razão $\dfrac{a}{b}$.

$2.$ Determine o produto dos $n$ primeiros números pares.

$3.$ Encontre o valor de $a_{2020}$ onde $a_n=2a_{n-1}+1$ e $a_1=1$.

$4.$ Numa P.A, temos $a_p=q$ e $a_q=p$. Calcule $a_{p+q}$.

Recorrência de segunda ordem

Esse tipo de recorrência tem cada termo definido por dois termos anteriores.

Ex: A sequência de Fibonacci em que sendo $F_n$ o $n$-ésimo termo, $F_{n+1}=F_n+F_{n-1}$

Ex: Sequências definidas da seguinte forma: $a_n=pa_{n-1}+qa_{n-2}$

Estratégias de solução para recorrências de segunda ordem:

Para resolver esse tipo de recorrência geralmente usamos um método um pouco mais avançado em relação da OBMEP, mas que sempre é bom saber: equações características. Porém, a nível OBMEP, algumas recorrências de segunda ordem podem ser resolvidas usando somas telescópicas ou as vezes podemos até fazer à mão os termos.

Exercícios:

$1.$ Ache o termo geral da recorrência $a_n=3a_{n-1}-2a_{n-2}$ onde $a_2=2$ e $a_1=1$

$2.$ Ache o termo geral na recorrência $2a_n=5a_{n-1}-2a_{n-2}$ com $a_2=a_1=1$

Problemas

1 (OBMEP/2011-F2-N2-P4). Começando com qualquer número natural não nulo é sempre possível formar uma sequência de números que termina em $1$, seguindo repetidamente as instruções abaixo:

• se o número for ímpar, soma-se $1$;
• se o número for par, divide-se por $2$.

Por exemplo, começando com o número $21$, forma-se a seguinte sequência:

$21\rightarrow22\rightarrow11\rightarrow12\rightarrow6\rightarrow3\rightarrow4\rightarrow2\rightarrow1$

Nessa sequência aparecem nove números; por isso, dizemos que ela tem comprimento $9$. Além disso, como ela começa com um número ímpar, dizemos que ela é uma sequência ímpar.

a) Quantas são as sequências pares e quantas são as sequências ímpares de comprimento $6$? E de comprimento $7$?

b) Existem ao todo $377$ sequências de comprimento $15$, sendo $233$ pares e $144$ ímpares. Quantas são as sequências de
comprimento $16$? Dessas, quantas são pares? Não se esqueça de justificar sua resposta.

2 (OBMEP/2019-F2-N2-P5). Dizemos que uma fila de cadeiras de cinema está ocupada de forma quase-cheia quando não há duas cadeiras consecutivas ocupadas, mas a próxima pessoa a chegar será obrigada a sentar-se ao lado de uma cadeira já ocupada. Uma fila de $5$ cadeiras tem exatamente quatro ocupações quase-cheias, mostradas abaixo. As cadeiras marcadas com X indicam que elas estão ocupadas.

a) Quantas são as ocupações quase-cheias em uma fila de $8$ cadeiras em que a segunda cadeira já está ocupada?

b) A tabela abaixo apresenta o número de ocupações quase-cheias para algumas filas de cadeiras. Calcule o total de ocupações quase-cheias em uma fila com $19$ cadeiras. Justifique.

 

3 (OBMEP/2014-F2-N2-P6). Fábio gosta de brincar em escadas, subindo ou descendo seus degraus da seguinte maneira:

•  começa no degrau de número $1$;
•  a cada movimento ele sobe ou desce um ou dois degraus e, ao subir ou descer dois degraus, não pisa no degrau intermediário;
•  pisa em todos os degraus exatamente uma vez.

Por exemplo, em uma escada com três degraus ele pode brincar de duas maneiras diferentes: $1\rightarrow2\rightarrow3$, $1\rightarrow3\rightarrow2$; com quatro degraus ele pode brincar de quatro maneiras diferentes: $1\rightarrow2\rightarrow3\rightarrow4$, $1\rightarrow2\rightarrow4\rightarrow3$, $1\rightarrow3\rightarrow2\rightarrow4$ e $1\rightarrow3\rightarrow4\rightarrow2$.

a) Explique por que sempre é possível terminar a brincadeira no degrau de número $2$ em qualquer escada com dois ou mais degraus.

b) Há $31$ e $68$ maneiras diferentes de se brincar em escadas com nove e onze degraus, respectivamente. De quantas maneiras diferentes Fábio pode brincar em uma escada com doze degraus?

4 (OBMEP/2018-F2-N2-P5). A nova mania de Fábio é triangular polígonos, ou seja, decompor polígonos em triângulos desenhando diagonais que não se cruzam no interior do polígono. Fábio notou que há apenas duas maneiras de triangular um quadrilátero e cinco maneiras de triangular um pentágono, como nas figuras.

a) De quantas maneiras Fábio pode triangular um hexágono?

b) De quantas maneiras Fábio pode triangular um heptágono?

5 (OBMEP/2012-F1-N2-P9). Renata montou uma sequência de triângulos com palitos de fósforo, seguindo o padrão indicado na figura.

Um desses triângulos foi construído com $135$ palitos de fósforo. Quantos palitos formam o lado do triângulo maior?

6 (OBMEP/2010-BANCO/P219). Construa uma figura com seis triângulos equiláteros adjacentes, o primeiro com lado de comprimento $1$ e os triângulos seguintes com lado igual à metade do lado do triângulo anterior, como indicado na figura. Qual é o perímetro dessa figura?

Dicas

1. b) Quantas sequências ímpares e pares de comprimento $16$ cada sequência de comprimento $15$ gera?

2. b) O que acontece quando a primeira cadeira está ocupada? E quando a segunda está ocupada?

3. a) Mostre um algoritmo que permita terminar a brincadeira no degrau $2$.

b) Analise os casos dependendo dos movimentos iniciais de Fábio.

4. Trace diagonais a partir de um único vértice para obter recorrências.

5. Conte o número de pálitos em cada termo da sequência formada e tente achar um recorrência

6. Escreva o lado de cada triângulo em função do triângulo imediatamente maior que ele.

Soluções

1. a) Com o diagrama abaixo concluímos que existem $3$ sequências pares e $2$ ímpares de comprimento $6$ e $5$ sequências pares e $3$ ímpares de comprimento $7$.

b) As $144$ sequências ímpares de comprimento quinze dão origem a $144$ sequências pares de comprimento dezesseis; já as $233$ sequências pares de comprimento quinze dão origem a $233$ sequências pares de comprimento dezesseis e $233$ sequências ímpares de comprimento dezesseis. Assim, temos $233$ sequências ímpares de comprimento dezesseis e $233+144=377$ sequências pares de comprimento dezesseis, num total de $233+377=610$ sequências.

2. a) Como a segunda cadeira já está ocupada, a primeira e terceira cadeiras necessariamente devem ficar livres. Assim, os demais a chegar devem ocupar, de modo quase cheio, as $5$ cadeiras restantes. Como visto no enunciado, há $4$ possibilidades para a ocupação dessas cadeiras.

b) Em uma ocupação quase cheia de $19$ cadeiras, exatamente uma das duas primeiras cadeiras deve estar ocupada. Com a primeira cadeira ocupada e consequentemente a segunda livre, as demais pessoas devem ocupar, de modo quase cheio, as outras $17$ cadeiras. De acordo com a tabela, há $114$ possibilidades para essa ocupação. Com a segunda cadeira ocupada e consequentemente as duas ao lado livres, as demais pessoas devem ocupar, de modo quase cheio, as outras $16$ cadeiras. De acordo com a tabela, há $86$ possibilidades para essa ocupação. Portanto, há um total de $114+86=200$ ocupações quase cheias para $19$ cadeiras.

3. a) Fábio pula sobre os degraus ímpares em ordem crescente até o último ímpar, daí pula para o maior degrau par e depois pula apenas sobre os degraus pares em ordem decrescente, terminando a brincadeira no degrau $2$.

b) Se ele começar com o movimento $1\rightarrow2$, o problema recairá no caso com $11$ degraus e, portanto, será possível completá-lo de $68$ maneiras.

Se ele começar com $1\rightarrow3\rightarrow2$, então ele terá que ir para o degrau $4$ e o problema recairá na mesma situação da escada com $9$ degraus e ele terá $31$ maneiras para completá-lo.

Se ele começar com os movimentos $1\rightarrow3\rightarrow4$, os degraus $2$ e $5$ ficarão a uma distância de 3 degraus um do outro e não será possível terminar a brincadeira.

Se ele começar com os movimentos $1rightarrow3\rightarrow5$, ele não poderá mais descer ou subir um degrau, até atingir o último ímpar para depois voltar pelos pares como descrito no item b) e, portanto, haverá apenas uma maneira.

Assim o número total de maneiras que Fábio pode brincar em uma escada com doze degraus é $68+31+1=100$.

4. Seja $f(x)$ igual à quantidade de maneiras de se triangular um polígono de $x$ lados, $A$ um vértice qualquer do polígono e $B$ o k-ésimo vértice no sentido horário a partir de $A$ e também o primeiro vértice que está conectado a $A$ no sentido horário. Assim, $B$ deve estar conectado ao primeiro vértice a partir de $A$ no sentido horário, caso contrário, $A$ estaria conectado à outro vértice anterior a $B$ no sentido horário. Assim obtemos um triângulo no meio do polígono e outros dois polígonos interiores, com $k$ vértices e $n-(k-1)$ vértices (exceto quando $B$ é o segundo ou o penúltimo vértice conectado a $A$, em que obtemos um triângulo e um polígono com $n-1$ vértices) e portanto essa configuração pode ser triangulada de $f(k)f(n-k+1)$, sendo $n$ a quantidade total de lados do polígono inicial. Observe que podemos obter esta configuração para qualquer vértice $B$ que esteja entre a segunda e a penúltima posição, ao contar os vértices no sentido horário a partir de $A$, portanto a quantidade total de maneiras de se triangular um polígono de $n$ lados é $f(n)= f(2)f(n-1)+f(3)f(n-2)+f(4)f(n-3)+\dots+f(n-2)f(3)+f(n-1)f(2)$, assumindo $f(2)=f(3)=1$. Assim podemos resolver os itens a) e b).

a) $f(6)=f(2)f(5)+f(3)f(4)+f(4)f(3)+f(5)f(2)=5+2+2+5=14$.

b) $f(7)=f(2)f(6)+f(3)f(5)+f(4)f(4)+f(5)f(3)+f(6)f(2)=14+5+4+5+14=42$.

5. Note que a cada triângulo adicionado aumenta em $3$ o total de palitos e na $n$-ésima vez que adicionamos triângulos, colocamos $n$ triângulos. Dessa forma, sendo $a_n$ o total de palitos após a $n$-ésima adição de palitos podemos defini-lo por:

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

Fazendo uma soma telescópica, como já fizemos na seção de recorrências de primeira ordem chegamos em $a_n=a_1+3(2+3+4+...+n)=\dfrac{3n(n+1)}{2}$. Assim, como queremos que

$a_n=135\Rightarrow\dfrac{3n(n+1)}{2}=135\Rightarrow n(n+1)=90\rightarrow n=9$

Assim $n=9$ e na nona adição de triângulos o triângulo maior tem lado $9$. $\blacksquare$

6. Sendo $P_n$ o perímetro quando temos $n$ triângulos, temos que $P_1=3$. Após colocarmos o $2$o triângulos o perímetro da figura aumenta em $\dfrac{1}{2}$. Quando colocamos o terceiro triângulo o perímetro aumenta em $\dfrac{1}{2^2}$ e assim por diante. Dessa forma definimos $P_n=P_{n-1}+\dfrac{1}{2^{n-1}}$. Resolvendo a recorrência com uma soma telescópica chegamos que $P_n=P_1+\dfrac{2^{n-1}-1}{2^{n-1}}$. Assim $P_6=3+\dfrac{31}{32}=\dfrac{127}{32}$. $\blacksquare$

Referências

Site da OBMEP: http://www.obmep.org.br/provas.htm

Material do POTI de recorrências

Material PROFMAT de recorrências