Re: [obm-l] soma de termos

[Marcio Cohen]

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 To: obm-l 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...