Re: [obm-l] Subconjuntos, Somas e Produtos

["Eduardo Casagrande Stabel" <dudasta@xxxxxxxxxxxx>]

Oi Cláudio!

Usando a notação [n] = {1,2,3,...,n}.

Queremos calcular

S(n) = SOMA{ 1 / F(X), X contido em [n]} =
SOMA{ 1 / F(X U {n}), X contido em [n-1]} + SOMA{ 1 / F(X), X contido em
[n-1]} + 1/n =
SOMA{ 1/n * 1 / F(X), X contido em [n-1]} + SOMA{ 1 / F(X), X contido em
[n-1]} + 1/n =
(1/n + 1) SOMA{ 1 / F(X), X contido em [n-1] } + 1/n =
S(n-1) * (n + 1)/n + 1/n = [ (n + 1) * S(n-1) ] / n + 1/n

Posso colocar S(n-1) em termos de S(n-2) e depois em termos de S(n-3), e ir
até S(1). Vou encontrar uma soma telescópica, e depois de soma-la, chegarei
a n. Uma outra maneira de demonstrar esse resultado é usando indução nesta
fórmula de recorrência.

S(n) = (n + 1)(n - 1)/n + 1/n = (n^2 - 1 + 1)/n = n

supondo S(n-1) = (n-1).

A soma vale n, portanto.

Duda.



From: "Claudio Buffara" <claudio.buffara@terra.com.br>
> Aqui vai um bonitinho:
>
> Seja A = conjunto dos subconjuntos de {1, 2, 3, ..., n}.
>
> Seja F: A --> N definida por:
> F(vazio) = 1
> F(X) = produto dos elementos de X
>
> Calcule o valor de SOMA(X em A) 1/F(X).
>
>
> Um abraco,
> Claudio,


=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================