Re: [obm-l] soma de termos

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Re: [obm-l] soma de termos

> Oi, Marcio:
>
> O que eu tinha em mente, quando falei em solucao algebrica, era abrir os numeros binomais e tentar simplificar o emaranhado de fatoriais resultante.
> Mas como nao fui totalmente explicito, tenho que aceitar esta solucao indutiva. Talvez seja a vinganca da inducao pelo que eu andei falando a respeito dela :-)
>
> []s,
> Claudio.

on 06.04.05 18:29, Marcio Cohen at marciocohen@superig.com.br wrote:

>  Oi Cláudio.. Realmente é muito mais legal uma demonstração combinatória:  Considere o conjunto dos números 0,1,2,3,...,n. Você quer escolher um sequencia a1 < a2 < ... < a(2m+1) de 2m+1 elementos, o que pode ser feito de "lado direito modos". Por outro lado, para cada k=0...n, voce pode escolher o elemento k como sendo o termo do meio dessa sequencia, e então precisa escolher binomial(k,m) termos menores e binomial(n-k,m) termos maiores que k. Somando em k, vemos que a resposta é o lado esquerdo e está provado.
>    
>    Mas não é tão feio fazer algebricamente..Vamos generalizar e provar que Soma(k=0..n) Binomial(k,a)*Binomial(n-k,b) = Binomial (n+1,a+b+1)
>  
>    Por inducao em n. Para n=0 eh facil. Supondo valido para n fixo e a,b quaisquer, temos:
> Soma(k=0..n+1) Binomial(k,a)*binomial (n+1-k,b) = Soma(k=0..n) Binomial(k,a)*[Binomial(n-k,b)+Binomial(n-k,b-1)] + Binom(n+1,a)*Binom(0,b)
> Usando a hipotese indutiva, isso da: Binomial(n+1,a+b+1) + Binomial(n+1, a+b) = Binomial (n+2, a+b+1)
>     Em particular, fazendo a=b=m voce tem a solucao do problema pedido ;) (tá, confesso que tentei fazer a indução direto antes e não consegui :) E demorei bem menos pra dar a solução combinatória do que por indução.. mas não resisti ao "quero ver alguém ..." :) 
>
>
>     Abraços,
>     Marcio
>  
> > ----- Original Message ----- 
> > From: claudio.buffara <mailto:claudio.buffara@terra.com.br>  
> > To: obm-l <mailto:obm-l@mat.puc-rio.br>  
> > Sent: Wednesday, April 06, 2005 3:58 PM
> > Subject: Re: [obm-l] soma de termos
> >
> > 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...
> >