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

Re: [obm-l] soma de termos



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