[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] soma de termos

Oi, Luís:
 
A impressão que eu tenho é que, depois do "Generatingfunctionology", todos estes problemas podem ser resolvidos pela aplicação de algum algoritmo geral.
 
Mesmo, assim, acho que é um bom treino tentar achar demonstrações combinatórias pra recorrências e identidades envolvendo números binomiais.
 
Por exemplo, é possível dar uma demonstração combinatória da identidade abaixo, que foi uma questão da famosa e difícil prova do IME de 1980/81.
 
SOMA(k=0...n) Binom(k,m)*Binom(n-k,m) = Binom(n+1,2m+1).
 
Agora, quero ver alguém provar isso algebricamente...
 
[]s,
Claudio.
 
De: owner-obm-l@mat.puc-rio.br
Para: obm-l@mat.puc-rio.br
Cópia:
Data: Wed, 06 Apr 2005 14:48:26 +0000
Assunto: Re: [obm-l] soma de termos
> Sauda,c~oes,
>
>
> >Um exercício que acho interessante é tentar dar uma demonstração do tipo
> >acima para cada propriedade do triângulo de Pascal.
>
> Concordo. Mas isso (dar interpretações combinatórias) muitas vezes é
> muito difícil. Como exemplo, considere a soma
>
> S_N(n) := \sum_{k>=n} Binom(N,2k) Binom(k,n) (n,N inteiros, n>=0, N>=1, N
> >=2n).
>
> As soluções combinatórias aparecem em The Mathematical Gazette 79 (484,
> 486),
> 1995.
>
> Eu iria por métodos mais gerais, se bem que nesse caso também não
> é muito fácil. Com algumas manipulações chegamos a
>
> S_N(n) = \sum_{k>=0} Binom(N,N-2n-2k) Binom(n+k,n).
>
> Isso é uma soma hipergeométrica e usando as técnicas mostradas
> no livro (resultado de Gauss) Matemática Concreta obtemos
> S_N(n) = [N / (N-n)] Binom(N-n,n) 2^(N-2n-1).
>
> []'s
> Luís
>
>
> >From: "claudio.buffara"
> >Reply-To: obm-l@mat.puc-rio.br
> >To: "obm-l"
> >Subject: Re: [obm-l] soma de termos
> >Date: Wed, 6 Apr 2005 09:01:29 -0300
> >
> >Oi, Bernardo:
> >
> >Eu falei mal da indução porque acho que ela produz demonstrações feias e
> >sem-graça, apesar de em muitos casos, ser a única forma (conhecida) de se
> >demonstrar algum resultado.
> >
> >Mas não é o caso da lei das colunas:
> >C(k,k) + C(k+1,k) + C(k+2,k) + ... + C(n,k) = C(n+1,k+1).
> >
> >Imagine que você quer formar subconjuntos de {1, 2, 3, ..., n, n+1} com k+1
> >elementos.
> >
> >Obviamente isso pode ser feito de C(n+1,k+1) maneiras diferentes.
> >
> >Mas quantos destes subconjuntos tem o inteiro positivo p
> >(k+1 <= p <= n+1) como maior elemento?
> >Bem, uma vez escolhido p, e dado que p é o maior elemento, os demais k
> >elementos só podem ser escolhidos dentre {1, 2, ..., p-1} e de C(p-1,k)
> >maneiras distintas.
> >Somando de p = k+1 até p = n+1, obtemos o número desejado:
> >C(k,k) + C(k+1,k) + ... + C(n,k)
> >
> >Com todo o respeito à sua demonstração, acho esta mais elegante. Além
> >disso, ela dá uma interpretação "concreta" para a lei das colunas.
> >
> >***
> >
> >Um exercício que acho interessante é tentar dar uma demonstração do tipo
> >acima para cada propriedade do triângulo de Pascal.
> >
> >
> >[]s,
> >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
> =========================================================================
>