on 07.04.05 10:28, Nicolau C. Saldanha at [EMAIL PROTECTED] 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 =========================================================================