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