[obm-l] somas binomiais [era: soma de termos]

[Lu�s Lopes <qed_texte@xxxxxxxxxxx>]

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" <claudio.buffara@terra.com.br>
>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
=========================================================================