[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] soma de termos



 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 -----
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...