Sauda,c~oes,
Oi Claudio,
O que você disse é verdade, inclusive no CRUX teve alguém fazendo o mesmo comentário. Só que a referência é o livro A=B do Doron Zeilberger e outros, publicado por A K Peters. Há um programa que resolve tais problemas, inclusive pedi e fui atendido pelo Doron na busca (de algumas) pela recorrência que estas somas satisfazem.
O problema que você menciona é realmente difícil. Ele é o problema 52 no livro que vou lançar lá pelo dia 15/05, envolvendo 121 somas combinatórias. O das colunas é o 12.
Resolvo algebricamente (combinação de resultados) SOMA(k=0...n) Binom(p+k,m)*Binom(n-k,m) = Binom(n+p+1,2m+1) (m>=p>=0).
Imagino que no IME a solução apresentada foi combinatória. Estas soluções combinatórias não fazem parte do livro. Já começo a pensar numa próxima edição com elas. Indo a SP como já lhe disse, poderemos falar a respeito.
A soma parecida SOMA(k>=0) Binom(m,k)*Binom(n+k,m) foi tirada do Winning Solutions do Rousseau. Não tem forma fechada conhecida mas mostra-se algebricamente (é o problema 88) que vale SOMA(k>=0) Binom(m,k)*Binom(n,k) 2^k (m,n>=0).
O prof. Doron me mandou a recorrência satisfeita pela soma S_n(m):
(n+2)S_{n+2}(m) - (2m+1)S_{n+1}(m) - (n+1)S_n(m)=0.Logo, S_0(m)=1, S_1(m)=2m+1 e com a recorrência, S_2(m)=2m^2+2m+1, S_3(m)=(2m+1)(2m^2+2m+3)/3 ...
[]'s Luís
From: "claudio.buffara" <[EMAIL PROTECTED]> Reply-To: obm-l@mat.puc-rio.br To: "obm-l" <obm-l@mat.puc-rio.br> Subject: Re: [obm-l] soma de termos Date: Wed, 6 Apr 2005 15:58:30 -0300
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.
========================================================================= 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 =========================================================================
