Métodos de Contagem
C
e Estatística
E
Cristianaa Poffal e Luvverci Nascimento
1. RELAÇ
ÇÕES DEE RECORR
RÊNCIA
ução 1.1 Introdu
Algumas relaçções matemááticas podem
m ser definid
das por reco
orrência. O o
objetivo desssa aula consiiste em estudar esses tipos de relações. bserve a seguinte situaçãão: Vamos co
ortar fatias d
de um bolo Ob
retangular: uando fazem
mos um cortee, obtemos 2
2 fatias. Quan
ndo fazemoss 2 Qu
cortes, obteemos 4 fatiass. O terceiro corte produ
uz 7 fatias. Co
om o quarto corte, terem
mos 11 fatiass. Com o quin
nto corte, terem
mos quantas fatias? Corte: 1 Fatias: 2 Corte: 2 Fatias: 4 Corte:: 3 Fatias: 7 Co
orte: 4 Faatias: 11 Paara respondeer à perguntta acima pod
demos, realizar mais um
m corte no bo
olo ou observar o que eestá acontecend
do com o número de fatias do bolo aa medida qu
ue aumentamos o númeero de cortes. Dessa form
ma, será possíveel responderr a uma pergunta mais geeral: quantass fatias haverá no bolo, q
quando fizerm
mos n cortees? É possível obsservar que o n‐ésimo co
o
orte cria n n
novas fatias. Logo, o núm
mero total d
de fatias obttido t
o por f (n ) éé dado pela sseguinte relação de recorrrência: com n cortes denotado
f (1) = 2
⎧
⎨
⎩ f (n ) = f (n − 1) + n, n ≥ 2.
ências Definidas por Reco
orrência 1.2 Definiçãão de Sequê
Um
ma seqüênciia é definida por recorrêência quando
o a definição
o da função ttambém se rreferir à próp
pria função. Isto
o é, a partiir de um prrimeiro valo
or dado (ou alguns pou
ucos valores) na seqüên
ncia, podem
m‐se determinar os valores subsequentess. or exemplo, qualquer prrogressão arritmética (a n ) de razão r e com prrimeiro term
mo a1 pode ser Po
definida com
mo an +1 = an + r , n > 1 . 1 Métodos de Contagem e Estatística
Cristiana Poffal e Luverci Nascimento
Para que a definição de uma relação de recorrência não seja circular, ela deve satisfazer às seguintes propriedades: a) Os valores de base não podem se referir à função. b) Cada vez que a função se referir a si própria, o argumento precisa estar próximo a um valor de base. É importante salientar que uma recorrência não define uma seqüência se o primeiro elemento não for definido. Classificação das sequências quanto à ordem f (1) = 2
⎧a n +1 = a n + r , n > 1
⎧
As sequências ⎨
e ⎨
são recorrências de primeira ordem, a1 = a
⎩ f (n ) = f (n − 1) + n, n ≥ 2 ⎩
⎧a n + 2 = 2a n +1 + a n , n > 1
pois cada termo é expresso em função de seu antecessor imediato. A sequência ⎨
é de a 0 = a1 = 1
⎩
segunda ordem, pois cada termo é expresso em função de dois antecessores imediatos. Classificação das sequências quanto à linearidade Uma relação de recorrência pode ser classificada como linear ou não‐linear. A sequência é dita linear se os valores anteriores de que aparecem na definição tenham apenas ⎧a n +1 = a n + r , n > 1 ⎧a n + 2 = 2a n +1 + a n , n > 1
a primeira potência. Por exemplo, as relações ⎨
e ⎨
são lineares, a1 = a
a 0 = a1 = 1
⎩
⎩
⎧a n + 2 = a n +1 + a n2 , n > 1
é dita não‐linear, uma vez que o termo a n está elevado ao quadrado. a
a
1
=
=
0
1
⎩
já ⎨
A forma geral para uma relação de recorrência linear é a n = f1 (n )a n −1 + f 2 (n )a n − 2 + f k (n )a n − k + g n onde os termos f i e g n podem ser expressões envolvendo n . Classificação das sequências quanto à homogeneidade Caso g n seja nulo para todo , a relação é dita homogênea. Caso contrário, é dita não‐
homogênea. Uma relação de recorrência linear de primeira ordem tem a forma . Por exemplo, a função fatorial n! é uma relação de recorrência, pois é definida da forma 1, n = 0
⎧
. n! = ⎨
⎩n ⋅ (n − 1)!, n > 0
2 Métodos de Contagem e Estatística
Cristiana Poffal e Luverci Nascimento
5! = 5 ⋅ 4!
= 5 ⋅ 4 ⋅ 3!
= 5 ⋅ 4 ⋅ 3 ⋅ 2!
Por exemplo, = 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1!
= 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 ⋅ 0!
= 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅1 ⋅1
5! = 120
⎧a n +1 = 2a n , n > 1
Exemplo 1: Considere a sequência definida por ⎨
, determine, justificando sua resposta: a1 = 3
⎩
a) a ordem da sequência; b) se é linear ou não‐linear; c) se é homogênea; d) o valor de a5 ; e) uma expressão para an em função de n . Solução: a) A sequência é de ordem 1, pois cada termo é expresso em função de seu antecessor imediato. b) A sequência é linear, pois todos os termos que aparecem na definição tem apenas a primeira potência. 0. c) A relação é homogênea, pois d) Sabendo que a1 = 3 e que a n +1 = 2 an , então obtemos a seguinte sequência: a1 = 3 a 2 = 2 ⋅ a1 = 2 ⋅ 3 a 3 = 2 ⋅ a 2 = 2 ⋅ (2 ⋅ 3) = 2 2 ⋅ 3 a 4 = 2 ⋅ a 3 = 2 ⋅ [2 ⋅ (2 ⋅ 3)] = 2 3 ⋅ 3 a 5 = 2 ⋅ a 4 = 2 ⋅ {2 ⋅ [2 ⋅ (2 ⋅ 3)]} = 2 4 ⋅ 3 = 48 . Logo, a 5 = 48 . e) Analisando a sequência anterior, é possível perceber que temos uma progressão geométrica de razão 2, assim a fórmula para an pode ser escrita como a n = 3 ⋅ 2 n −1 . 1.3 Solução de Relações de Recorrência No exemplo anterior, a expressão a n = 3 ⋅ 2 n −1 permite determinar cada termo da sequência ⎧a n +1 = 2a n , n > 1
sem a necessidade de conhecer todos os valores menores. Essa equação é chamada de ⎨
a1 = 3
⎩
solução em forma fechada para a relação de recorrência em questão. Quando encontramos uma solução em forma fechada para uma relação de recorrência, podemos afirmar que resolvemos essa relação de recorrência. Resolver uma relação de recorrência consiste em determinar uma fórmula explícita para an em
termos de n .
Exemplo 2: Resolva as relações de recorrência abaixo: 3 Métodos de Contagem e Estatística
Cristiana Poffal e Luverci Nascimento
⎧a = a n + 3 n , n > 1
⎧a = 2 a n + 2 n , n > 1
a) ⎨ n +1
b) ⎨ n +1
a1 = 1
a1 = 1
⎩
⎩
Solução: a) Escrevendo os termos de an +1 = an + 3n até enxergar um padrão: n an +1 = an + 3n 1 a1+1 = a1 + 3 n ⇒ a 2 = 1 + 31 2 a 2 +1 = a 2 + 3 2 ⇒ a 3 = 1 + 31 + 3 2 3 a 3+1 = a 3 + 33 ⇒ a 4 = 1 + 31 + 3 2 + 3 3 4 a 4 +1 = a 4 + 3 4 ⇒ a 5 = 1 + 31 + 3 2 + 33 + 3 4 M n an =
3 −1
2
M n
A expressão para an é obtida através da fórmula da soma de uma progressão geométrica (PG) de n termos. b) Escrevendo os termos de an +1 = 2an + 2 n até enxergar um padrão: n an +1 = 2an + 2 n 1 a1+1 = 2a1 + 21 ⇒ a 2 = 2 + 21 = 2 ⋅ 2 = 2 2 2 a 2 +1 = 2a 2 + 2 2 ⇒ a 3 = 2 2 2 + 2 2 = 3 ⋅ 2 2 3 a 3+1 = 2a 3 + 2 ⇒ a 4
4 a 4 +1 = 2a 4 + 2 4 ⇒ a5
M n a n = (n ) ⋅ 2
3
n −1
( )
= 2[2(2 + 2 ) + 2 ] + 2 = 4 ⋅ 2
= 2{2[2(2 + 2 ) + 2 ] + 2 }+ 2
1
2
1
3
2
3
3
4
= 5 ⋅ 24 M A solução é dada por a n = (n ) ⋅ 2 n −1 . Fórmula generalizada para a solução da relação de recorrência linear de primeira ordem É possível obter uma fórmula generalizada para a solução da relação de recorrência linear de primeira ordem , onde o termo é conhecido? Sim, para isso usamos a relação de recorrência repetidamente, isto é, escrevemos: 4 Métodos de Contagem e Estatística
Cristiana Poffal e Luverci Nascimento
Depois de k expansões, observa‐se que a fórmula geral pode ser . Se o primeiro termo da equação for conhecido, então a expansão termina quando 1, ou seja, , ou, em uma notação mais compacta: ∑
. Para toda e qualquer relação de recorrência na forma , com o termo definido, o processo realizado acima não precisa ser repetido. No exemplo 2, as respostas poderiam ser obtidas através da fórmula obtida acima. Para o ∑ 3 , cujo resultado é obtido item a, temos 1 e 3 , 1, logo 1 ∑ 3
usando a soma de uma progressão geométrica (PG) de n termos. E chega‐se a a n =
3n − 1
. 2
1.4 Recorrências Lineares de Segunda Ordem 1.4.1 Recorrência linear de segunda ordem homogênea com coeficientes constantes Uma recorrência linear de segunda ordem homogênea com coeficientes constantes tem a forma 0, para 0. 0, A cada recorrência desse tipo pode‐se associar uma equação do segundo grau que é chamada de equação característica. O cálculo das raízes dessa equação permite determinar a solução da recorrência dada. Ao efetuar esse cálculo, obtemos as raízes e e podemos chegar a uma das seguintes situações: 1) Duas raízes reais distintas: 2) Duas raízes reais iguais: 1 3) Duas raízes complexas conjugadas: e , onde Situação 1: Duas raízes reais distintas 0 são e , então Teorema 1: Se as raízes da equação característica 0 para quaisquer valores de e . é solução da equação de recorrência Demonstração: 0, precisa‐
A fim de verificar se é solução da recorrência se obter uma identidade ao substituí‐la na relação. Passo 1: Calcular e : 5 Métodos de Contagem e Estatística
Passo 2: Substituir , e Cristiana Poffal e Luverci Nascimento
na relação de recorrência 0: 0 Passo 3: Agrupar os termos de forma conveniente: Colocando e em evidência, obtém‐se: 0. Como e são raízes da equação característica, então 0
0
0 é uma identidade. Exemplo 3: Considere a recorrência 4
5
0, determine: a) Sua ordem; b) Se é homogênea ou não; c) Sua equação característica; d) Sua solução. Solução: a) A recorrência é de segunda ordem, pois há a dependência de dois antecessores. b) É homogênea, pois todos os termos dependem de a. 4
c) A equação característica é 5 0, que é a equação do segundo grau associada à recorrência dada. d) As raízes da equação característica são 1 e 5, então a solução da recorrência é 1
5 , onde e são constantes arbitrárias que poderão ser determinadas quando os forem fornecidos dois valores para a recorrência. 4
5
0
1
Exemplo 4: Determine a solução da recorrência 1
Solução: A equação característica dessa recorrência foi construída no exemplo anterior, bem como foi realizado o cálculo de suas raízes (reais e distintas). Com isso, é necessário apenas substituir os valores de base na recorrência para obter os valores de e através da resolução do sistema de equações resultante. 0 e 1, obtemos A partir de 1
5 , substituindo 1
1
5
1 e 1, o que resulta no sistema e cuja solução é 1
5
5
1
. Logo, a solução da relação de recorrência dada é 1
5 . 0 são distintas, então todas as soluções de Teorema 2: Se as raízes da equação característica 0 são da forma , onde e são constantes. recorrência Situação 2: Duas raízes complexas conjugadas Se as raízes da equação característica forem complexas e , a solução de 0 pode ser escrita de modo a evitar cálculos com números complexos. Escrevem‐se as raízes em sua forma trigonométrica e a solução fica 6 Métodos de Contagem e Estatística
θ
Cristiana Poffal e Luverci Nascimento
θ , onde corresponde ao módulo das raízes | | e θ é o argumento do número complexo . Por que isso acontece? pode ser escrito na forma polar. O número complexo Observe na figura ao lado a representação vetorial de , onde é possível localizar e θ. A forma polar do número complexo é θ
θ e de seu complexo conjugado, θ
θ . Essas representações devem ser substituídas em , isto é, θ
θ θ
θ . As potências de e são calculadas como θ
θ e θ
θ . Assim, θ
θ
θ
θ . Reagrupando os coeficientes de θ e de θ , obtém‐se θ
θ . e , chega‐se a θ
θ . Escrevendo 0. Exemplo 5: Determine a solução da recorrência Solução: 1 0. Passo 1: Escreve‐se a equação característica: . Passo 2: Resolve‐se a equação característica: as raízes são Sendo as raízes, calculam‐se o módulo e o argumento correspondente, isto é, | |
θ
. Passo 3: Escrever a solução da recorrência: . Situação 3: Duas raízes reais iguais 0 são iguais, Teorema: Se as raízes da equação característica soluções de recorrência 0 são da forma constantes. 1, , então todas as , onde e são 7 Métodos de Contagem e Estatística
Cristiana Poffal e Luverci Nascimento
Exemplo 6: Determine a solução da recorrência 8
16
0. Solução: 8
16 0. Passo 1: Escreve‐se a equação característica: 4. Passo 2: Resolve‐se a equação característica: as raízes são 4
4 Passo 3: Escrever a solução da recorrência: 1.4.2 Recorrência linear de segunda ordem não‐homogênea com coeficientes constantes Estudaremos um processo de solução de recorrências não‐homogêneas. , então a substituição de Teorema: Se é uma solução da equação transforma a equação em 0. Esse teorema indica que a solução de uma recorrência não‐homogênea consiste de duas parcelas: a solução homogênea (já sabemos como calcular) e solução não‐homogênea (vamos calcular por tentativas). Isto é, podemos escrever . Demonstração do teorema: Substituindo em , obtemos . Mas, é solução de , logo 0. Exemplo 7: Resolva a recorrência 7
12
2 . Solução: Como essa recorrência é não‐homogênea, sua solução será composta por duas parcelas e será escrita . na forma Etapa 1: Resolve‐se a equação homogênea: 7
12
0 com o intuito de determinar . 7
12 0 1. Escreve‐se a equação característica: 2. Resolve‐se a equação característica: As raízes da equação são 3 e 4. 3. Escreve‐se a solução homogênea : 4
3 . Etapa 2: Determinar a solução não‐homogênea . Essa solução chamada de pode ser obtida por tentativa, porém, precisa‐se levar em conta que, ao ser substituída na recorrência 7
12
2 , deve produzir uma identidade. ⋅2 que corresponde à soma de um polinômio Assim, testa‐se a expressão completo do segundo grau com uma função exponencial de base 2, ou seja, é uma solução cujo formato é 2 . semelhante ao da função ⋅2 na relação de recorrência original 7
12
1. Substitui‐se 2 . 8 Métodos de Contagem e Estatística
Cristiana Poffal e Luverci Nascimento
e : Calculam‐se os termos 2
2
⋅2 , 1
Faz‐se a substituição de cada termo na recorrência e obtém‐se: 2
⋅2 7
1
2
⋅2
2 12
1
⋅2
1
⋅2
2. Expandem‐se os produtos notáveis, realizam‐se as multiplicações, agrupam‐se os termos semelhantes: 6
6
10
3
5
6
2 ⋅2
2 3. Comparam‐se os termos semelhantes nos dois membros da equação e se chega ao sistema: 6
1
6
10
0
3
5
6
0
2
1
,
, e . 4. Resolve‐se o sistema por substituição e obtém‐se 5. Substituem‐se os valores encontrados na expressão de ⋅2 : 1
5
17 1
⋅2 6
18
54 2
Essa é a solução não‐homogênea. Etapa 3: Escrever a solução geral da recorrência: , isto é: 1
5
17 1
⋅2 4
3 6
18
54 2
Para mostrar que o resultado encontrado é solução da relação de recorrência dada, basta substituí‐lo 7
12
2 . em 4
3
2 . Exemplo 8: Resolva a relação de recorrência Solução: Como essa recorrência é não‐homogênea, sua solução será composta por duas parcelas e será escrita . na forma 4
3
0 com o intuito de determinar . Etapa 1: Resolve‐se a equação homogênea: 1. Escreve‐se a equação característica: 4
3 0 2. Resolve‐se a equação característica: As raízes da equação são 1 e 3. 3. Escreve‐se a solução homogênea : 1
3 , isto é, 3 Etapa 2: Determinar a solução não‐homogênea . 9 Métodos de Contagem e Estatística
Cristiana Poffal e Luverci Nascimento
Essa solução chamada de pode ser obtida por tentativa, porém, precisa‐se levar em conta que, ao 4
3
2 , deve produzir uma identidade. ser substituída na recorrência Assim, testa‐se ⋅2 que corresponde à soma de um polinômio completo do primeiro grau com uma função exponencial de base 2, ou seja, é uma solução cujo formato é semelhante ao da função 2 . ⋅2 na relação de recorrência original 4
3
2 . 4. Substitui‐se e : Calculam‐se ⋅2 , 1
⋅2 2
Faz‐se a substituição de cada termo na recorrência e obtém‐se: 3
2 2
⋅2
4
1
⋅2
⋅2
5. Expandem‐se os produtos notáveis, realizam‐se as multiplicações, agrupam‐se os termos semelhantes: ⋅2
2 2
6. Comparam‐se os termos semelhantes nos dois membros da equação e se observa que essa igualdade é impossível. Logo, a recorrência não admite solução da forma ⋅2 . 7. Observando a solução homogênea, é possível perceber que a constante já faz parte da solução, então pode‐se fazer uma nova tentativa, aumentando o grau do termo , ou seja, tenta‐se ⋅2 . a. Calculam‐se os termos da recorrência a partir da solução escolhida, ou seja, 2
2
⋅2 , 1
1
⋅2 . b. Substituindo cada termo na relação de recorrência e agrupando os termos semelhantes, chega‐se a ⋅2
2 4
2
c. Obtém‐se o sistema 4
1
2
0 1
, 0 e 1. d. Determinam‐se os valores 8. Substituem‐se os valores encontrados na expressão de 2 . Essa é a solução não‐homogênea. Etapa 3: Escrever a solução geral da recorrência: , isto é: 1
2 3 4
10 Métodos de Contagem e Estatística
Cristiana Poffal e Luverci Nascimento
Para mostrar que o resultado encontrado é solução da recorrência dada, basta substituí‐lo em 4
3
2 . Observação: Nesse exemplo, nossa primeira tentativa de obtenção da solução não‐homogênea não funcionou, porque não se analisou a solução homogênea antes de escrever a solução não‐homogênea. As soluções devem ser distintas, por isso, quando houver repetição deve‐se aumentar o grau do bloco onde essa repetição ocorre multiplicando por . 11