Somatorios

Pontif´ ıcia Universidade Cat´lica de Minas Gerais o Bacharelado em Sistemas de Informa¸˜o ca Algoritmos e Estrutura de Dados
Prof. Marcelo Souza Nery

Somat´rios o Somat´rios Comuns o Os seguintes somat´rios ser˜o utilizados com bastante freq¨ˆncia ao longo do curso: o a ue b

1=b−a+1 i=a n

1=n i=1 n

1=n+1 i=0 n

i= i=1 n

n(n + 1)
2

i2 =

n3 n2 n
+
+
3
2
6

i3 =

n2 (n + 1)2
4

ai =

an+1 − 1 a−1 i=1 n i=1 n i=0 n i=1

1
= ln(n) i M´todo para Solu¸˜o Geral e ca
A seguinte expans˜o de somat´rios pode ser utilizada para resolver qualquer somat´rio (exceto s´ries a o o e harmˆnicas): o n n

f (i) → i=1 f (i) − f (i − 1) = f (n) − f (0) i=1 onde f (i) ´ a fun¸ao que se quer determinar a f´rmula fechada do somat´rio. e c˜ o o

Caso Particular
No caso de somat´rios em que a fun¸˜o f (i) for uma fun¸˜o polinomial, tomar o cuidado em definir tal fun¸˜o o ca ca ca como o polinˆmio de grau imediatamente superior. o n

i. Deve-se definir f (i) = i2 para resolvˆ-lo, utilizando a expans˜o e a

Exemplo: Seja o seguinte somat´rio o i=0

dada anteriormente. Vejamos o que ocorrer´ se fizermos f (i) = i, e n˜o i2 como proposto. a a

n

n

f (i) →

f (i) − f (i − 1) = f (n) − f (0) i=1 n

i=1

i − (i − 1) = n − 0 i=1 n

i−i+1 =n i=1 n

1=n i=1 Certo! Sabemos que o somat´rio de 1 ´ n, quando i varia de 1 a n. Mas n˜o era isto que est´vamos procurando! o e a a
Est´vamos procurando o somat´rio de i. Para que seja poss´ utilizar a f´rmula geral indicada, devemos ent˜o a o ıvel o a definir a fun¸˜o f (i) = i2 . Vejamos agora esta resolu¸˜o: ca ca

n

n

f (i) → i=1 f (i) − f (i − 1) = f (n) − f (0) i=1 n

i2 − (i − 1)2 = n2 − 0 i=1 n

i2 − (i2 − 2i + 1) = n2 i=1 n

i2 − i2 + 2i − 1 = n2 i=1 n

2i − 1 = n2 i=1 n

n

1 = n2

2i − i=1 n

i=1

i − n = n2

2 i=1 n

i = n2 + n

2
i=1