Re: [obm-l] soma de termos

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 07.04.05 10:28, Nicolau C. Saldanha at nicolau@mat.puc-rio.br wrote:

> On Wed, Apr 06, 2005 at 03:58:30PM -0300, claudio.buffara wrote:
>> 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...
> 
> O fato (que não é difícil) que você deve conhecer para fazer isto
> algebricamente é que f_m(x) = x^m/(1-x)^(m+1) = soma_k binom(k,m) x^k.
>
Eu nao conhecia essa identidade e, francamente, creio que nenhum
vestibulando normal teria a ideia de usa-la na hora da prova, a menos que
jah a tivesse visto antes. Enfim, como voce disse, nao eh dificil demonstrar
(alias, acho que o lado esquerdo deveria ser (-x)^m/(1-x)^(m+1)).

Eh soh derivar m vezes cada membro de:
1/(1-x) = SOMA(k>=0) x^k  (o que vale apenas quando |x| < 1)
obtendo:
m!*(-1)^m/(1-x)^(m+1) = SOMA(k>=m) (k!/(k-m)!)*x^(k-m)

Multiplicando cada membro por x^m/m!, ficamos com:
(-x)^m/(1-x)^(m+1) = SOMA(k>=m) Binom(k,m)*x^k.

> Assim o lado direito A é o coeficiente de x^n em
> (f_m(x))^2 = x^(2m)/(1-x)^(2m+2) = (1/x) f_(2m+1)(x).
> Portanto A é o coeficiente de x^(n+1) de f_(2m+1),
> ou seja, A = binom(n+1,2m+1).
>
Alias, pensando melhor, acho que somente alguem familiarizado com funcoes
geratrizes e series formais usaria isso naquela questao. Certamente, nao era
o meu caso na epoca em que prestei IME (um ano depois do seu) mas, por
sorte, a prova de MAT1 de 1981/82 foi muito mais facil...

> Mas eu concordo com o Claudio, prefiro a demonstração combinatoria.
> Alias, foi a que eu usei na prova (este foi o meu ano, e eu prestei
> o vestibular do IME, mas acabei não entrando lá).
>
Uma clarificacao: acabou nao entrando lah porque nao quis, pois, pra quem
nao sabe, o Nicolau foi 1o. colocado no vestibular do IME daquele ano.

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