Seqüências
George Darmiton da Cunha Cavalcanti
CIn - UFPE
Introdução
• Uma seqüência é uma estrutura discreta usada para
representar listas ordenadas.
• Definição 1
– Uma seqüência é uma função de um subconjunto do
conjunto dos inteiros (usualmente {0, 1, 2, 3, ...} ou {1,
2, 3, ...}) em um conjunto S.
– Usa-se a notação an para denotar a imagem do inteiro n.
– Chama-se an um termo da seqüência.
Exemplo
• Considere a seqüência {an}, sabendo que
– an = 1/n
– A lista dos termos dessa seqüência, começando
com a1, são rotulados como
• a1, a2, a3, a4, ...
– E possui os seguintes termos
• 1, ½, 1/3, ¼, ...
Exemplos
• Algumas seqüência
an = 6n
an = 2n + 1
an = 10n
an = 5
• Seqüência
1, 5, 25, 125, 625, ...
• Seqüência
1, -1, 1, -1, 1, -1, ....
Progressão aritmética
• Definição
– Uma progressão aritmética é uma seqüência da
seguinte forma
– a, a+d, a+2d, a+3d, ..., a+nd
– Sabendo que o termo inicial a e a diferença d
são números reais
Exemplo
• As seqüências
{sn} com sn = –1+4n
{tn} com tn = 7 – 3n
• São ambas progressões aritméticas com
a= –1 e d=4
a=7 e d= –3
• Assim, a lista de termos das seqüências são
–1, 3, 7, 11, ....
7, 4, 1, –2, ....
Progressão Geométrica
• Definição
– Uma progressão geométrica é uma seqüência da
seguinte forma
– a, ar, ar2, ar3, ..., arn
– Sabendo que o termo inicial a e a razão r são
números reais
A progressão geométrica é uma estrutura discreta.
Função exponencial f(x) = arx.
Exemplo
• As seqüências
{bn} com bn = (–1)n
{cn} com cn = 2×5n
{dn} com dn = 6×(1/3)n
• São ambas progressões geométricas com
a= –1
a=10
a=2
e r= –1
e r=5
e r=1/3
• Assim, a lista de termos das seqüências são
–1, 1, –1, 1, ....
10, 50, 250, 1250, ...
2,2/3, 2/9, 2/27, ....
• Seqüências finitas a1, a2, ..., an são
freqüentemente usadas em computação
• As cadeias (strings) são seqüências finitas também
denotadas por a1a2a3...an.
– Exemplo: cadeias de bits.
– O seu tamanho, ou o número de termos da seqüência,
ou da cadeia, é n.
• A cadeia vazia não possui termos, seu tamanho e
igual a zero.
Seqüências especiais (Inteiros)
• Como definir uma fórmula ou regra geral
para construir os termos de uma seqüência?
• Algumas perguntas úteis:
– Os termos são obtidos de termos anteriores pela
soma de algum valor?
– Os termos são obtidos de termos anteriores pela
multiplicação de algum valor?
– Os termos são obtidos pela combinação de
termos anteriores de uma forma particular?
Seqüências especiais (Inteiros)
Exemplo
•
Dada as seqüências abaixo, quais são suas
fórmulas
a) 1, 1/2, 1/4, 1/8, 1/16
b) 1,3,5,7,9
c) 1,-1,1,-1,1
Respostas
a) Os denominadores são potência de 2
an = 1/2n-1 (a=1 e r=1/2)
b) Uma possível resposta é an = 2n-1
c) an = (-1)n+1
Exemplo
• Suponha uma seqüência cujos 10 primeiros
termos são
– 1, 2, 2, 3, 3, 3, 4, 4, 4, 4
O inteiro n aparece exatamente n vezes na
seqüência
Exemplo
• Suponha uma seqüência cujos 10 primeiros
termos são
– 5, 11, 17, 23, 29, 35, 41, 47, 53, 59
an = 5+6(n-1) = 6n-1
Essa progressão aritmética tem a=5 e d=6.
Exemplo
• Suponha uma seqüência cujos 10 primeiros
termos sejam
– 1, 7, 25, 79, 241, 727, 2185, 6559, 19681, 59047
Resposta
an = 3n-2
Somatório
Uma forma de expressar a soma da seqüência
{an}
am , am+1 , ... , an
n
j=m
aj
Representa am + am+1 + ... + an
n
j=m
aj =
n
i=m
ai =
n
k=m
ak
Exemplo
• Expresse a soma dos 100 primeiros termos
da seqüência {an}, tal que an = 1/n para
n=1,2,3,...
100
1
j =1 j
Exemplo
• Qual é o valor do
5
j2 ?
j =1
5
j =1
j 2 = 12 + 22 + 32 + 42 + 52
= 1 + 4 + 9 + 16 + 25
= 55
Exemplo
5
j 2 Mudar os índices de 1 a 5 para 0 a 4.
j =1
k=j–1
5
j =1
j2 =
4
j=k+1
( k + 1) 2
k =0
= 1+4+9+16+25 = 55
Séries Geométricas
• Teorema
– Se a e r são números reais e r≠0, então
Séries Geométricas (prova)
Exemplo
• Somatórios duplos
4
3
i =1 j =1
ij
Exemplo
100
k2 = ?
k = 50
100
49
k2 =
k2 +
100
k =1
k =1
k = 50
100
100
49
k = 50
k2 =
k2 −
k =1
k2
k2
k =1
100 ⋅101 ⋅ 201 49 ⋅ 50 ⋅ 99
−
=
6
6
k = 50
338.350 − 40.425 = 297.925
100
k2 =
Alguns somatórios
Cardinalidade
• Definição
– Os conjuntos A e B possuem a mesma
cardinalidade se e somente se existe uma bijeção
(one-to-one correspondence) de A para B
Conjunto enumerável
• Definição
– Conjunto enumerável (ou contável)
– Um conjunto que é finito ou que possui a
mesma cardinalidade dos números naturais e
chamado de enumerável (ou contável).
– Caso contrário ele é dito não enumerável.
Exemplo
• Mostrar que o conjunto dos inteiros ímpares é um
conjunto contável.
É necessário encontrar uma função bijetora.
Considerando a função:
f(n) = 2n-1
Injetora
Supondo que f(n) = f(m). Assim, 2n-1=2m-1, então n=m.
Sobrejetora
Supondo que t é um inteiro ímpar
Então t é igual a 1 menos um inteiro par 2k (k é um número natural).
Assim, t = 2k-1 = f(k)
Exemplo
Bijeção entre os inteiros positivos e o conjunto de
inteiros ímpares positivos
Exemplo
• Mostrar que o conjunto dos racionais positivos é um
conjunto contável.
Todo número racional é da forma p/q (dois inteiros)
É possível organizar os números racional
listando todos os que tem quociente igual a 1 na primeira linha
listando todos os que tem quociente igual a 2 na segunda linha
E assim por diante
A chave é listar a seqüência de forma que
p+q=2
p+q=3
E assim por diante
Eliminando repetições
Exemplo
Os números racionais positivos formam um conjunto contável.
Exemplo
• Mostrar que o conjunto dos números reais é um conjunto
não enumerável.
Argumento de diagonalização de Cantor
Será analisado um subconjunto dos números reais [0,1].
Prova por contradição:
•
•
•
Assume-se que o intervalo [0,1] é infinito enumerável.
Então é possível enumerar todos os números deste intervalo
como uma seqüência ( r1, r2, r3, ... )
Sabe-se que cada um desses números pode ser representado
como uma expansão decimal
Exemplo
r1 = 0 , 5 1 0 5 1 1 0 ...
r2 = 0 , 4 1 3 2 0 4 3 ...
r3 = 0 , 8 2 4 5 0 2 6 ...
r4 = 0 , 2 3 3 0 1 2 6 ...
r5 = 0 , 4 1 0 7 2 4 6 ...
r6 = 0 , 9 9 3 7 8 3 8 ...
r7 = 0 , 0 1 0 5 1 3 5 ...
...
r1 = 0 , 5 1 0 5 1 1 0 ...
r2 = 0 , 4 1 3 2 0 4 3 ...
r3 = 0 , 8 2 4 5 0 2 6 ...
r4 = 0 , 2 3 3 0 1 2 6 ...
r5 = 0 , 4 1 0 7 2 4 6 ...
r6 = 0 , 9 9 3 7 8 3 8 ...
r7 = 0 , 0 1 0 5 1 3 5 ...
...
x = 0 , 4 4 5 4 4 4 4 ...
Exemplo
• O número x é um número real dentro do intervalo [0,1]
• Por isso, rn = x para algum n
• No entanto, por causa da maneira como foi escolhido os
dígitos 4 e 5 , x difere na n-ésima posição de rn, então x
não está na seqüência (r1, r2, r3, ... )
• Essa seqüência portanto não é uma enumeração do
conjunto de todos os reais no intervalor [0,1]. Isto é uma
contradição
• Logo, a hipótese de que o intervalo [0,1] é contável deve
ser falsa