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