1.6. Relações de Recorrência
Programa
1
Matemática Discreta
Parte 1 - Conjuntos e Aplicações
1
2
3
2008/09
4
5
6
Vı́tor Hugo Fernandes
Departamento de Matemática
2
Parte 2 - Grafos e Aplicações
1
FCT/UNL
2
3
4
5
6
Departamento de Matemática (FCT/UNL)
MD 2008-2009
1 / 16
1.6. Relações de Recorrência
Conjuntos
Relações Binárias
Aplicações
Indução Matemática e Divisibilidade
Congruências lineares
Relações de Recorrência
Generalidades
Conexidade
Árvores
Grafos Eulerianos
Grafos Hamiltonianos
Matrizes e Grafos
Departamento de Matemática (FCT/UNL)
MD 2008-2009
2 / 16
1.6. Relações de Recorrência
1.6. Relações de Recorrência
2. Seja (an )n≥1 a sucessão definida pela relação de recorrência
Uma relação de recorrência para uma sucessão (an )n≥0 é uma expressão
que relaciona cada termo an (a partir de certa ordem p) com alguns dos
seus predecessores a0 , a1 , . . . , an−1 . As condições iniciais são valores que
são explicitamente dados para um número finito (p − 1) de termos da
sucessão.
“Resolver” uma relação de recorrência, sujeita a certas condições iniciais, é
determinar uma “expressão explı́cita” para o termo geral da sucessão.
Exemplos
2,
Departamento de Matemática (FCT/UNL)
3,
5,
8,
13,
MD 2008-2009
21,
= an−2 + 2 · 3
= an−3 + 3 · 3
..
.
= a1 + (n − 1) · 3
= 2 + 3(n − 1),
f1 = 1 & f2 = 2
1,
com a condição inicial a1 = 2.
Ora,
an = an−1 + 3
= (an−2 + 3) + 3
= (an−3 + 3) + 2 · 3
..
.
n ≥ 2,
= (an−k + 3) + (k − 1) · 3 = an−k + k · 3
..
.
1. A sucessão de Fibonacci (fn )n≥1 é definida pelas condições iniciais
e pela relação de recorrência fn = fn−1 + fn−2
an = an−1 + 3,
(n ≥ 3) :
34,
i.e. an = 2 + 3(n − 1), para n ≥ 1.
(Prove formalmente esta igualdade, usando o Princı́pio de Indução.)
...
3 / 16
Departamento de Matemática (FCT/UNL)
MD 2008-2009
4 / 16
1.6. Relações de Recorrência
1.6. Relações de Recorrência
3. Vamos resolver a relação de recorrência
Exemplos
1. A expressão
an = 2an−1
fn = fn−1 + fn−2
sujeita à condição inicial a0 = 1. Temos
(utilizada na definição da sucessão de Fibonacci) é uma relação de
recorrência linear homogénea de grau 2 com coeficientes constantes.
an = 2an−1 = 2 · 2an−2 = 22 an−2 = 22 · 2an−3
= 23 an−3 = · · · = 2k an−k = · · · = 2n a0
= 2n ,
2. A expressão
an = 2an−1
i.e. an = 2n , para n ≥ 0.
(Prove formalmente esta igualdade, usando o Princı́pio de Indução.)
é uma relação de recorrência linear homogénea de grau 1 com coeficientes
constantes.
Uma relação de recorrência linear homogénea de grau k (k ≥ 1) com
coeficientes constantes é uma expressão da forma
3. A relação de recorrência an = 3an−1 an−2 não é linear.
4. A relação de recorrência an = an−1 + 3 não é homogénea.
an = c1 an−1 + c2 an−2 + · · · + ck an−k ,
5. A relação de recorrência an = 3nan−1 não tem coeficientes constantes.
com c1 , . . . , ck constantes (reais) e ck 6= 0.
Departamento de Matemática (FCT/UNL)
MD 2008-2009
5 / 16
1.6. Relações de Recorrência
Departamento de Matemática (FCT/UNL)
MD 2008-2009
Observação
Uma relação de recorrência linear homogénea de grau 1 com coeficientes
constantes é uma expressão (genericamente) da forma an = can−1 , com c
uma constante (real) não nula.
É fácil concluir que podemos resolver esta relação de recorrência sujeita à
condição inicial a0 = a (constante), obtendo-se an = ac n , n ≥ 0
(Exercı́cio).
Lema
Seja an = c1 an−1 + c2 an−2 (c1 , c2 ∈ R) uma relação de recorrência linear
homogénea de grau 2 com coeficientes constantes. Sejam S e T duas
sucessões que satisfazem a relação de recorrência e sejam b e d duas
constantes (reais). Então a sucessão
Lema
Seja
an = c1 an−1 + c2 an−2
(c1 , c2 ∈ R) uma relação de recorrência linear homogénea de grau 2 com
coeficientes constantes. Seja r uma raiz da equação
x 2 − c1 x − c2 = 0.
Então, a sucessão (r n )n∈N0 satisfaz a relação de recorrência.
Demonstração. Por hipótese, r é raiz de x 2 − c1 x − c2 = 0, pelo que
r 2 − c1 r − c2 = 0, ou seja, r 2 = c1 r + c2 . Então
c1 r n−1 + c2 r n−2
U = bS + dT
MD 2008-2009
= r n−2 (c1 r + c2 )
= r n−2 r 2 = r n ,
como pretendido. também satisfaz a relação de recorrência.
Departamento de Matemática (FCT/UNL)
6 / 16
1.6. Relações de Recorrência
7 / 16
Departamento de Matemática (FCT/UNL)
MD 2008-2009
8 / 16
1.6. Relações de Recorrência
1.6. Relações de Recorrência
Demonstração. Pelo lema anterior, as sucessões S = (r1n )n≥0 e T = (r2n )n≥0
Teorema
Seja
satisfazem ambas a relação de recorrência. Assim, pelo penúltimo lema, para
quaisquer constantes b e d, a sucessão
an = c1 an−1 + c2 an−2
bS + dT = U = (un )n≥0
(c1 , c2 ∈ R) uma relação de recorrência linear homogénea de grau 2 com
coeficientes constantes tal que a equação
satisfaz a relação de recorrência. Resta-nos pois determinar constantes b e d por
forma que U também satisfaça as condições iniciais, ou seja, tais que
u0 = C0
x 2 − c1 x − c2 = 0
admite duas raı́zes distintas r1 e r2 . Seja (an )n≥0 a sucessão definida pela
relação de recorrência sujeita às condições iniciais
a0 = C0
&
a1 = C1 .
Departamento de Matemática (FCT/UNL)
+
dr2n ,
u1 = C1 .
para n ≥ 0, pelo que (considerando
u0 = b + d
u1 = br1 + dr2 .
b + d = C0
Assim, falta-nos resolver o sistema de equações lineares
br
1 + dr2 = C1 ,
1 1
.
nas incógnitas b e d, cuja matriz simples é M =
r1 r2
Como det M = r2 − r1 6= 0, então o sistema é possı́vel e determinado. Portanto,
provámos a existência de constantes b e d tais que a sucessão U também satisfaz
as condições iniciais. n ≥ 0.
MD 2008-2009
Ora, a partir de (∗), temos un =
n = 0 e n = 1),
e
br1n
Então, existem constantes (reais) b e d tais que
an = b r1n + d r2n ,
(∗)
9 / 16
1.6. Relações de Recorrência
Departamento de Matemática (FCT/UNL)
MD 2008-2009
10 / 16
1.6. Relações de Recorrência
Exemplos
1. Vamos resolver a relação de recorrência
2. Consideremos agora a relação de recorrência
an = 5an−1 − 6an−2
bn = 3bn−1 − 2bn−2
sujeita às condições iniciais a0 = 7 & a1 = 16.
Comecemos por considerar a equação x 2 − 5x + 6 = 0, cujas raı́zes são
x = 2 e x = 3.
Atendendo ao teorema anterior, temos
an = b 2n + d 3n ,
sujeita às condições iniciais b0 = 200 & b1 = 220. Comecemos por analisar
a equação
x 2 − 3x + 2 = 0,
cujas raı́zes (distintas) são x = 1 e x = 2. Pelo teorema anterior, temos
bn = b + d 2n , para n ≥ 0, para certas constantes b e d tais que
b + d = b0 = 200
b = 180
ou seja,
b + 2d = b1 = 220,
d = 20.
n ≥ 0,
para certas constantes b e d tais que
b + d = a0 = 7
2b + 3d = a1 = 16,
Logo, bn = 180 + 20 · 2n , para n ≥ 0.
ou seja (resolvendo o sistema), b = 5 e d = 2.
Logo, an = 5 · 2n + 2 · 3n , para n ≥ 0.
Departamento de Matemática (FCT/UNL)
MD 2008-2009
11 / 16
Departamento de Matemática (FCT/UNL)
MD 2008-2009
12 / 16
1.6. Relações de Recorrência
1.6. Relações de Recorrência
Teorema
Seja
Demonstração. Comecemos por observar que a sucessão S = (r n )n≥0 ,
atendendo ao lema anterior, satisfaz a relação de recorrência. Por outro lado,
sendo r uma raiz dupla da equação x 2 − c1 x − c2 = 0, então
an = c1 an−1 + c2 an−2
(c1 , c2 ∈ R) uma relação de recorrência linear homogénea de grau 2 com
coeficientes constantes tal que a equação
(x − r )2 = x 2 − c1 x − c2 ,
i.e.
x 2 − 2rx + r 2 = x 2 − c1 x − c2 ,
x 2 − c1 x − c2 = 0
admite uma raiz dupla r . Seja (an )n≥0 a sucessão definida pela relação de
recorrência sujeita às condições iniciais
a0 = C0
&
a1 = C1 .
Então, existem constantes (reais) b e d tais que
an = b r n + d n r n ,
pelo que
c1 = 2r
e
c2 = −r 2 .
Observemos que, por hipótese, c2 6= 0 (pois a relação de recorrência é do grau 2),
donde r 6= 0. Tendo em conta os valores obtidos para c1 e c2 , é fácil verificar que,
também a sucessão T = (n r n )n≥0 satisfaz a relação de recorrência (Exercı́cio).
Assim, pelo penúltimo lema, a sucessão
bS + dT = U = (un )n≥0
n ≥ 0.
ainda satisfaz a relação de recorrência, para quaisquer constantes b e d.
Departamento de Matemática (FCT/UNL)
MD 2008-2009
13 / 16
1.6. Relações de Recorrência
MD 2008-2009
14 / 16
1.6. Relações de Recorrência
Tal como na prova do teorema anterior, resta-nos determinar constantes b e d
por forma que U também satisfaça as condições iniciais, ou seja, tais que
u0 = C0
e
Exemplo
Vamos resolver a relação de recorrência
u1 = C1 .
Ora, a partir de (∗), temos un = br n + dnr n , para n ≥ 0, pelo que (considerando
n = 0 e n = 1),
u0 = b
u1 = br + dr .
Assim, temos de resolver o sistema de equações lineares
b = C0
br + dr = C1 ,
sujeita às condições iniciais c0 = 1 & c1 = 1.
Comecemos por considerar a equação x 2 − 4x + 4 = 0, a qual possui
x = 2 como raiz dupla.
Atendendo ao teorema anterior, temos
n ≥ 0,
para certas constantes b e d tais que
b = c0 = 1
2b + 2d = c1 = 1,

 d = C1 − rC0 ,
r
ou seja (resolvendo o sistema), b = 1 e d = − 21 .
Logo, an = 2n − 12 n 2n = 2n − n2n−1 , para n ≥ 0.
portanto, possı́vel e determinado. MD 2008-2009
cn = 4cn−1 − 4cn−2
cn = b 2n + d n 2n ,
nas incógnitas b e d, o qual é equivalente a


 b = C0
Departamento de Matemática (FCT/UNL)
Departamento de Matemática (FCT/UNL)
15 / 16
Departamento de Matemática (FCT/UNL)
MD 2008-2009
16 / 16
Download
Matemática Discreta
