PAA - Somatórios (Créditos: Prof Wallace Rodrigues)

Prévia do material em texto

Projeto e Análise de Algoritmos
Somatórios
Prof. Walace de Almeida Rodrigues
Instituto Federal de Minas Gerais - Campus Formiga
21 de novembro de 2015
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 1 / 29
Sumário
1 Notações
2 Propriedades
3 Métodos
Recombinação
Perturbação
Operador diferença
Soma das derivadas
Aproximação por integral
Combinação de métodos
4 Fórmulas notáveis
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 2 / 29
1. Notações
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 3 / 29
1.1. Notação básica
n∑
i=1
i = 1+2+·· ·+n
Exemplos:
n∑
i=1
i = 1+2+ . . .+n=
n−1∑
i=0
(i +1)
n∑
i=1
i = 1+n+
n−1∑
i=2
i
300∑
i=1
3i = 3+6+·· ·+300
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 4 / 29
1.2. Notação de Iverson
∑
i
[p(i)] f (i)= c1+·· ·+cn
p(i) denota uma expressão lógica
[p(i)]=
{
1, se p(i) for verdadeiro
0, caso contrário
os valores c1, · · · ,cn são resultado da expressão ([p(i)]∗ f (i))
calculada no domínio de i
essa notação foi popularizada por Donald Knuth
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 5 / 29
1.2. Notação de Iverson
Exemplos:
300∑
i=1
[3|i] i = 3+6+·· ·+300
300∑
[3|i] i=1
i = 3+6+·· ·+300
∑
[3|i] 1≤i≤300
i = 3+6+·· ·+300
∑
1≤i≤300
[3|i] i = 3+6+·· ·+300
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 6 / 29
1.3. Notação combinada
m∑
i=1
n∑
j=1
xiyj = (x1y1+·· ·+x1yn)+·· ·+ (xmy1+·· ·+xmyn)
Exemplos:
3∑
i=1
2∑
j=1
M[i , j]= a+b+c+d +e+ f
2∑
j=1
3∑
i=1
M[i , j]= a+c+e+b+d + f
∑
1≤i≤3
1≤j≤2
M[i , j]=∑
i ,j
[1≤ i ≤ 3][1≤ j ≤ 2] M[i , j]
M =
 a bc d
e f

walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 7 / 29
2. Propriedades
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 8 / 29
2.1. Propriedade: multiplicação (por constante)
b∑
i=a
K ∗ f (i) =K ∗
b∑
i=a
f (i) sendo K uma constante
Demonstração:
b∑
i=a
K ∗ f (i) = [K ∗ f (a)]+ [K ∗ f (a+1)]+·· ·+ [K ∗ f (b)]
=K ∗ [f (a)+ f (a+1)+·· ·+ f (b)]
=K ∗
b∑
i=a
f (i)
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 9 / 29
2.2. Propriedade: soma (ou subtração)
b∑
i=a
f (i)±g(i) =
b∑
i=a
f (i) ±
b∑
i=a
g(i)
Demonstração:
b∑
i=a
f (i)±g(i) = [f (a)±g(a)] + [f (a+1)±g(a+1)] +·· ·+ [f (b)±g(b)]
= [f (a)± f (a+1)±·· ·± f (b)] + [g(a)±g(a+1)±·· ·±g(b)]
=
b∑
i=a
f (i) ±
b∑
i=a
g(i)
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 10 / 29
2.3. Propriedade: diferença telescópica
b∑
i=a
f (i +1)− f (i) = f (b+1)− f (a)
Demonstração:
b∑
i=a
f (i +1)− f (i) = [f (a+1)− f (a)]+ [f (a+2)− f (a+1)]+·· ·+ [f (b+1)− f (b)]
= [����f (a+1)− f (a)]+ [����f (a+2)−����f (a+1)]+·· ·+ [f (b+1)−��f (b)]
= f (b+1)− f (a)
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 11 / 29
2.4. Propriedade: soma de produtos
n∑
i=m
b∑
j=a
f (i)∗g(j) =
n∑
i=m
f (i) ∗
b∑
j=a
g(j)
Demonstração:
n∑
i=m
b∑
j=a
f (i)∗g(j)= [f (m)∗g(a)+·· ·+ f (m)∗g(b)]+·· ·+
[f (n)∗g(a)+·· ·+ f (n)∗g(b)]
= f (m)∗ [g(a)+·· ·+g(b)]+·· ·+ f (n)∗ [g(a)+·· ·+g(b)]
=
n∑
i=m
f (i) ∗
b∑
j=a
g(j)
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 12 / 29
3. Métodos
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 13 / 29
3.1. Recombinação
Vantagem: simples de usar
Modo de usar: reescreva a soma de modo conveniente
n∑
i=1
i = ?
n∑
i=1
i = 1+2+·· ·+ (n−1)+n
= 1〈1〉+2〈2〉+·· ·+ (n−1)〈2〉+n〈1〉 associando pares
= (n+1)〈1〉+ (n+1)〈2〉+·· ·+ (n+1)〈n/2〉 formados n/2 pares
=
n/2∑
i=1
(n+1)= (n+1)∗
n/2∑
i=1
1
= (n+1)∗ n
2
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 14 / 29
3.2. Perturbação
Vantagem: método poderoso, resolve muitos somatórios
Modo de usar: acrescente mais um termo e reescreva a soma
Desvantagem: pode ser difícil saber o que perturbar
n∑
i=1
i 2 = ? Dica: perturbe a soma dos cubos
n+1∑
i=1
i 3 =
n∑
i=1
i 3+ (n+1)3 =
n∑
i=0
(i +1)3 = 1+
n∑
i=1
(i +1)3
= 1+
n∑
i=1
(i 3+3i 2+3i +1)= 1+
n∑
i=1
i 3+3
n∑
i=1
i 2+3
n∑
i=1
i +
n∑
i=1
1
= 1+
n∑
i=1
i 3+3
n∑
i=1
i 2+3(n/2)(n+1)+n
= agora continue daqui
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 15 / 29
3.2. Perturbação
Exercícios:
1 Examine o processo de perturbação da soma dos quadrados
n+1∑
i=1
i 2 = ?
2 Dica: perturbe i!
n∑
i=1
i ∗ i!= ?
3 Se vire com esse
n∑
i=1
i ∗2 i = ?
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 16 / 29
3.3. Operador diferença
Vantagem: método poderoso, inspirado na propriedade telescópica
Modo de usar: encontre uma função que, aplicado o operador nela,
o resultado seja a função no somatório
Desvantagem: pode ser difícil encontrar essa função
Definição do operador ∆
∆f (x)= f (x +1)− f (x)
n∑
i=1
∆f (i) = [f (2)− f (1)]+·· ·+ [f (n+1)− f (n)]
= f (n+1)− f (1)
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 17 / 29
3.3. Operador diferença
n∑
i=1
i ∗ i! = ? Dica: use a função f (x)= x!
Escolhida a função f(x) = x! temos:
∆f (x)= f (x +1)− f (x)
= (x +1)!−x!= (x +1)x!−x!
= xx!
Assim:
n∑
i=1
i ∗ i!=
n∑
i=1
∆f (i)= f (n+1)− f (1)= (n+1)!−1
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 18 / 29
3.3. Operador diferença
Exercício:
1 Resolva usando o operador diferença
n∑
i=1
i ∗2 i = ?
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 19 / 29
3.4. Soma das derivadas
Vantagem: método que resolve muitos somatórios
Modo de usar: aplica-se quando a função no somatório
é derivada de outra que sabemos somar
Requisitos: conhecimento de derivação e que a função seja contínua
Soma de derivadas
f ′+g′ = (f +g)′
Derivada da divisão
(u/v)′ = (u′v −uv ′)/(v 2)
Aplicadas ao somatório
n∑
i=1
u′ =
(
n∑
i=1
u
)′
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 20 / 29
3.4. Soma das derivadas
n∑
i=1
i ∗x i = ?
A função lembra a derivada de um monômio e isso pode ser explorado:
n∑
i=1
i ∗x i = x ∗
n∑
i=1
i ∗x i−1 = x ∗
(
n∑
i=1
x i
)′
Note: no somatório x é constante e i variável, mas na derivada é o contrário:(
n∑
i=1
x i
)′
=
(
xn+1−x
x −1
)′
esse somatório é uma P.G.
Agora continue daqui, aplicando a regra para derivada da divisão.
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 21 / 29
3.4. Soma das derivadas
Exemplo completo:
n∑
i=1
i ∗x i = x ∗
n∑
i=1
i ∗x i−1 = x ∗
(
n∑
i=1
x i
)′
= x ∗
(
xn+1−x
x −1
)′
= x ∗
(
((n+1)xn−1)(x −1)− (xn+1−x)(1)
(x −1)2
)
= x ∗
(
((n+1)xn+1− (n+1)xn−x +1)− (xn+1−x)
(x −1)2
)
= nx
n+2− (n+1)xn+1+x
(x −1)2
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 22 / 29
3.5. Aproximação por integral
Vantagem: ajuda encontrar limites para o somatório (teto ou piso)
Requisitos: a função deve ser contínua e monotônicaPara função monotônica crescente:∫ n
m−1
f (x)dx ≤
n∑
i=m
f (i) ≤
∫ n+1
m
f (x)dx
Para função monotônica decrescente:∫ n+1
m−1
f (x)dx ≤
n∑
i=m
f (i) ≤
∫ n
m−1
f (x)dx
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 23 / 29
3.5. Aproximação por integral
∫ n
m−1
f (x)dx ≤
n∑
i=m
f (i) ≤
∫ n+1
m
f (x)dx
■ Piso
■ Somatório
■ Teto
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 24 / 29
3.5. Aproximação por integral
n∑
i=1
1
i
= ?
O piso e o teto para o somatório são dados por:∫ n+1
1
1
x
dx ≤
n∑
i=2
1
i
≤
∫ n
1
1
x
dx
ln(n+1) ≤
n∑
i=2
1
i
≤ ln(n)
Assim:
ln(n+1)+1≤
n∑
i=1
1
i
≤ ln(n)+1
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 25 / 29
3.6. Combinação de métodos
n∑
i=1
x i =? sendo x constante
Recombinando os termos, colocando uma parte em evidência, temos:
n∑
i=1
x i = x1+x2+·· ·+xn−1+xn
= x(1+x1+x2+·· ·+xn−1)
Perturbando a série, para ressurgir o somatório do lado direito:
n∑
i=1
x i +xn+1 = x(1+x1+x2+·· ·+xn−1+xn)
= x
(
1+
n∑
i=1
x i
)
agora continue daqui
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 26 / 29
4. Fórmulas notáveis
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 27 / 29
Grupos de somatórios
Polinômios
1
∑n
i=1 i =
n(n+1)
2 ⇐PA
2
∑n
i=1 i
2 = n(n+1)(2n+1)6
3
∑n
i=1 i
3 = (∑ni=1 i)2
Coeficientes binomiais
4
∑n
i=0
(n
i
) = 2n
5
∑n
i=0
( i
x
) = (n+1x+1)
Exponenciais
6
∑n
i=1x
i = x(xn− 1)
(x−1) ⇐PG
7
∑b
i=ax
i = x(xb− xa−1)
(x−1)
8
∑n
i=0 i ∗x i =
nxn+2−(n+1)xn−1+x
(x−1)2
Outros
9
∑n
i=1 1/i = ln(n)+O(1)
10
∑n
i=1 i ∗ i! = (n+1)!−1
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 28 / 29
Referências
“Algoritmos: teoria e prática”, Thomas Cormen
Apêndice A
“Somatórios”, Filipe Rodrigues Moreira
www.rumoaoita.com/site/attachments/045_somatorios.pdf
walace.rodrigues@ifmg.edu.br (IFMG) Projeto e Análise de Algoritmos 21 de novembro de 2015 29 / 29
	Notações
	Propriedades
	Métodos
	Recombinação
	Perturbação
	Operador diferença
	Soma das derivadas
	Aproximação por integral
	Combinação de métodos
	Fórmulas notáveis