Polos Olímpicos de Treinamento

Curso de Álgebra - Nível 2 Aula 5

Prof. Marcelo Mendes

Recorrências - Parte II

Na aula 3, falamos de uma sequência famosa, a Sequência de Fibonacci, cuja definição é

a seguinte: F1 = F2 = 1 e, para n ≥ 3, Fn = Fn−1 + Fn−2 . Essa fórmula é uma recorrência
linear de ordem 2. Um de nossos objetivos neste 5o texto é mostrar que a fórmula explı́cita
para seus termos é
√ !n √ !n
1 1+ 5 1 1− 5
Fn = √ −√ .
5 2 5 2

Surpreendente, não é mesmo? Imaginar que, substituindo n por 1, 2, 3, √ 4, 5, 6, ... na

fórmula acima, acharemos exatamente os termos 1, 1, 2, 3, 5, 8, ..., e nenhum 5 sobra, é
realmente muito belo.

Em geral, nesta aula, trataremos equações de recorrência lineares que dependem so-
mente dos dois termos anteriores. Inicialmente, vamos estudar o caso em que as raı́zes da
equação caracterı́stica (que definiremos no texto) são distintas.

1 Um Exemplo para Organizar as Ideias

Vamos resolver a recorrência a1 = 1, a2 = 3 e, para n ≥ 3,

an = 3an−1 − 2an−2 .
Podemos escrever an − an−1 = 2 (an−1 − an−2 ) e, em seguida, multiplicar telescopica-
mente várias delas

an − an−1 = 2 (an−1 − an−2 )

an−1 − an−2 = 2 (an−2 − an−3 )
:
a3 − a2 = 2 (a2 − a1 )
POT 2012 - Álgebra - Nı́vel 2 - Aula 5 - Prof. Marcelo Mendes

obtendo an − an−1 = 2n−2 (a2 − a1 ) = 2n−1 .

Agora, somamos telescopicamente várias dessa última equação

an − an−1 = 2n−1
an−1 − an−2 = 2n−2
:
a2 − a1 = 2
e chegamos a an − a1 = 2 + ... + 2n−2 + 2n−1 , ou seja, an = 2n − 1.

Observe que, na primeira passagem, para transformar an = 3an−1 − 2an−2 em an −

an−1 = 2 (an−1 − an−2 ), ’pedimos emprestado’ an−1 para o membro esquerdo. Essa operação
gerou proporção entre os coeficientes dos termos dos dois membros (antes e depois da igual-
dade), permitiu colocar o fator de proporção 2 em evidência e a diferença que surgiu entre
parênteses no membro direito ficou com o mesmo padrão da diferença no membro esquerdo,
mas com ı́ndices reduzidos. Essa será nossa ideia para encontrar o termo geral da

2 Sequência de Fibonacci
Como já definimos anteriormente, seus termos são dados por F1 = F2 = 1 e, para
n ≥ 3, Fn = Fn−1 + Fn−2 . Na verdade, os cálculos ficam mais interessantes escrevendo
Fn+1 = Fn +Fn−1 . Seria difı́cil ’pedir emprestado’ uma quantidade inteira desta vez pois há
somente Fn no membro direito. Assim, vamos chamar de λ a quantidade que será passada
para o membro esquerdo, ou seja,

Fn+1 − λFn = (1 − λ)Fn + Fn−1 .

Para repetirmos a ideia bem sucedida do primeiro exemplo, o valor de λ deve cumprir
a relação de proporção

1 1−λ
= ,
−λ 1
ou seja,

λ2 − λ − 1 = 0,
a qual chamaremos de equação caracterı́stica da sequência de Fibonacci. Observe desde
já que os coeficientes dessa equação são os mesmos da recorrência que define a sequência.
Sendo λ1 e λ2 as raı́zes, aqui será mais relevante saber que λ1 + λ2 = 1 e λ1 · λ2 = −1 (mas
veja que ambas são reais e distintas) do que escrever seus valores pela fórmula de Baskara.

Agora, substituindo λ por λ1 , obtemos

Fn+1 − λ1 Fn = (1 − λ1 )Fn + Fn−1 ,

2
POT 2012 - Álgebra - Nı́vel 2 - Aula 5 - Prof. Marcelo Mendes

ou seja,
Fn+1 − λ1 Fn = λ2 (Fn − λ1 Fn−1 ) .
Assim, deixamos a equação pronta para escrevê-la várias vezes e fazer o produto te-
lescópico

Fn+1 − λ1 Fn = λ2 (Fn − λ1 Fn−1 )

Fn − λ1 Fn−1 = λ2 (Fn−1 − λ1 Fn−2 )
:
F3 − λ1 F2 = λ2 (F2 − λ1 F1 ) ,
cujo resultado será

Fn+1 − λ1 Fn = λ2n−1 (F2 − λ1 F1 ) = λ2n−1 (1 − λ1 ) = λn2 .

Analogamente, substituindo λ por λ2 , temos

Fn+1 − λ2 Fn = λn1 .
A diferença entre esses 2 últimos resultados gera

(λ1 − λ2 ) Fn = λn1 − λn2

e, portanto,

λn1 − λn2
Fn =
λ1 − λ2
lembrando que λ1 6= λ2 . Substituindo os valores de λ1 e λ2 , chegamos ao resultado desejado
√ !n √ !n
1 1+ 5 1 1− 5
Fn = √ −√ .
5 2 5 2

Mas há um pequeno problema. Esse método é bastante trabalhoso. A boa notı́cia é que
podemos deixá-lo como uma quase demonstração e realizar, na prática, os seguintes passos:

1o passo: Escreva a equação caracterı́stica.

Basta copiar os mesmos coeficientes da equação de recorrência. Em seguida, calcule as

raı́zes dessa equação.

2o passo: Escreva o termo geral da recorrência.

O termo geral é dado por Fn = Aλn1 + Bλn1 (essa fórmula pode ser encontrada refazendo
os cálculos para a recorrência mais geralmente, ou seja, com a equação xn = axn−1 +bxn−2 ).

3
POT 2012 - Álgebra - Nı́vel 2 - Aula 5 - Prof. Marcelo Mendes

As constantes A e B são dadas pelos valores dos termos iniciais. É interessante, para re-
duzir as contas, calcular o termo de ordem ’0’, que, no caso da sequência de Fibonacci, é
F0 = 0.

Vejamos como seria, então, a resolução na prática para encontrar o termo geral da
sequência de Fibonacci.

Passo 1. Equação caracterı́stica.

√ √
1+ 5 1− 5
De Fn −Fn−1 −Fn−2 = 0, obtemos λ2 −λ−1 = 0, cujas raı́zes são λ1 = 2 e λ2 = 2 .

Passo 2. Termos geral.

Fn = Aλn1 + Bλn1 . Com os valores 0 e 1 para n, obtemos

0=A+B
1 = Aλ1 + Bλ2
cuja solução é A = −B = √1 .
5

Portanto,
√ !n √ !n
1 1+ 5 1 1− 5
Fn = √ −√ .
5 2 5 2

Problema 1. Um garoto tem n reais. Todo dia, ele realiza exatamente uma das seguintes
compras: um bolo que custa R$ 1, 00, um sorvete que custa R$ 2, 00 ou um pastel que
também custa R$ 2, 00. De quantas maneiras o menino pode gastar seu dinheiro?

Solução. Seja an o número de maneiras de ele gastar os n reais.

Assim, para gastar os últimos reais, ou ele gasta n − 1 reais primeiramente e compra
um bolo no final, ou ele gasta n − 2 reais inicialmente e, em seguida, compra um sorvete
ou um pastel. Portanto, podemos escrever

an = an−1 + 2an−2 ,
com a1 = 1 (só dá pra comprar 1 bolo) e a2 = 3 (comprando 2 bolos ou 1 sorvete ou 1
pastel).

Agora, vamos resolver.

i) Equação caracterı́stica: λ2 − λ − 2 = 0, cujas raı́zes são 2 e −1.

4
POT 2012 - Álgebra - Nı́vel 2 - Aula 5 - Prof. Marcelo Mendes

ii) Termos geral: an = A · 2n + B · (−1)n . Podemos calcular a0 , que não faz sentido para
o gasto do dinheiro, mas existe na sequência associada: a2 = a1 + 2a0 ⇒ a0 = 1. Agora,
para n = 0 e n = 1

A+B =1
2A − B = 1,
2
cuja solução é A = 3 e B = 13 . Assim

2n+1 + (−1)n
an = .
3
Problema 2. Determine o termo geral da sequência definida pela recorrência a1 = 1, a2 = 4
e an = 4an−1 − 3an−1 para n ≥ 3.

Problema 3. Determine o termo

√ geral da sequência definida recorrentemente por a0 = 0,
a1 = 3 e, para n ≥ 3, an = 5an−1 + an−1 .

Problema 4. Considere um retângulo 1 × n, que deve ser preenchido por dois tipos de
retângulos menores 1 × 1 e 1 × 2. De quantas maneiras se pode fazer isso?

Problema 5. (OPM) Uma escada tem n degraus. Para subi-la, em cada passo, pode-se
subir um ou dois degraus de cada vez. De quantos modos diferentes pode-se subir a escada?

Problema 6. Uma sequência de números ak é definida por a0 = 0 e ak+1 = 3ak + 1, k ≥ 0.

Prove que a155 é divisı́vel por 11.

Solução. Inicialmente, veja que essa recorrência não depende dos dois termos anteriores.
A parcela 1 no membro da direita, na verdade, não é bem-vinda. Assim, de

ak+1 = 3ak + 1
ak = 3ak−1 + 1
3n − 1
obtemos ak+1 − 4ak + 3ak−1 = 0. O termo geral dessa recorrência é an = (a de-
2
monstração deixamos para o leitor).

3155 − 1
Logo, a155 = . Para finalizar, deixo como sugestão que 35 − 1 = 242 = 11 × 22.
2

21 3
Problema 7. Seja {an } uma sequência tal que a1 = e 2an − 3an−1 = n+1 , n ≥ 2.
16 2
Encontre o valor de a2 e a lei de recorrência de cada termo em função dos dois termos
imediatamente anteriores.

5
POT 2012 - Álgebra - Nı́vel 2 - Aula 5 - Prof. Marcelo Mendes

3 Recorrências e Equações do 2o Grau

Como exemplo para organizar as ideias, vamos supor que α seja uma raiz da equação
x2 + x − 1 = 0. Assim

α2 = −α + 1.
Daı́,

α3 = −α2 + α = 2α − 1
α4 = 2α2 − α = −3α + 2
α5 = −3α2 + 2α = 5α − 3.
Será que existe um padrão entre os coeficientes que aparecem no lado direito de cada
potência de α? Sim, existe! Na próxima aula, que será sobre indução finita, estaremos
aptos a provar que

αn = (−1)n−1 Fn α + (−1)n Fn−1 ,

sendo {Fn } a sequência de Fibonacci.

Problema 8. Se α e β são as raı́zes da equação ax2 + bx + c = 0 e Sn = αn + β n , n ∈ N,

então mostre que aSn+1 + bSn + cSn−1 = 0.

Solução. Como α e β são as raı́zes de ax2 + bx + c = 0, então

aα2 + bα + c = 0
aβ 2 + bβ + c = 0.
Daı́, multiplicando por αn−1 e β n−1 , respectivamente, temos

aαn+1 + bαn + cαn−1 = 0

aβ n+1 + bβ n + cβ n−1 = 0.
Somando, obtemos

a αn+1 + β n+1 + b (αn + β n ) + c αn−1 + β n−1 = 0

ou seja,

aSn+1 + bSn + cSn−1 = 0.

Problema 9. Seja α a maior raiz de x2 + x − 1 = 0. Determine o valor de α5 − 5α.

6
POT 2012 - Álgebra - Nı́vel 2 - Aula 5 - Prof. Marcelo Mendes

αn − β n
Problema 10. Sejam α e β as raı́zes de x2 + x − 1 = 0. Sendo an = , n = 1, 2, 3, ....
α−β
Determine os dois primeiros termos a1 e a2 dessa sequência e a lei de recorrência de cada
termo em função dos dois termos imediatamente anteriores.

7
POT 2012 - Álgebra - Nı́vel 2 - Aula 5 - Prof. Marcelo Mendes

Dicas

2. Use a equação caracterı́stica e encontre o termo geral seguindo o exemplo e a questão

1.

3. Use a equação caracterı́stica e encontre o termo geral seguindo o exemplo e a questão

1.

4. Para finalizar, ou ele completa com um quadradinho 1 × 1 o retângulo 1 × (n − 1),

que pode ser preenchido de an−1 maneiras, ou ele completa com um retângulo 1 × 2
o retângulo 1 × (n − 2), que pode ser preenchido de an−2 maneiras.

5. Para finalizar, ou ele sobe um degrau a partir do degrau n − 1, que pode ser alcançado
de an−1 maneiras, ou ele sobe dois degraus a partir do degrau n − 2, que pode ser
alcançado de an−2 maneiras.
3
7. Multiplique a equação de recorrência por 2 e subtraia de 2an−1 − 3an−2 = n , que é
2
a equação dada substituindo n por n − 1.

10. Se a equação caracterı́stica é x2 + x − 1 = 0, então a equação de recorrência é

an = −an−1 + an−2 .

Respostas

3n − 1
2. an =
2
√ !n √ !n
5+3 5−3
3. an = −
2 2

4. Sendo an o número de maneiras, a1 = 1, a2 = 2, an = an−1 + an−2

5. Sendo an o número de maneiras, a1 = 1, a2 = 2, an = an−1 + an−2

69
7. a2 = 32 e 4an − 8an−1 + 3an−2

9. −3

10. a1 = 1 e a2 = −1; an = −an−1 + an−2