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

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 24.08.03 01:18, Eduardo Casagrande Stabel at dudasta@terra.com.br wrote:

> 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,
> 
> 
Oi, Duda:

Seu raciocinio estah perfeito, com um unico detalhe. Voce nao incluiu o
conjunto vazio, que adiciona 1 a soma e faz com que S(n) = n+1.

Por exemplo, se n = 3, teremos:
  X       1/F(X)
vazio      1
{1}        1
{2}        1/2 
{3}        1/3
{1,2}      1/2
{1,3}      1/3
{2,3}      1/6
{1,2,3}    1/6
E a soma desses termos eh 4.

Um outro jeito de provar isso eh observar que, para A = Partes([n]):
SOMA(X em A) 1/F(X) = (1 + 1/1)*(1 + 1/2)*(1 + 1/3)*...*(1 + 1/n) =
= (2/1)*(3/2)*(4/3)*...*((n+1)/n) = n+1.

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
=========================================================================