Sauda,c~oes,
Essas demonstra��es combinat�rias do Claudio s�o realmente interessantes e elegantes.
Entretanto, as mais mec�nicas e r�pidas s�o (seriam) aquelas usando antidiferen�as.
Assim, seja a soma S_n(m) = \sum_{k=m}^n Binom(k,m) (m>=0).Ent�o Binom(k,m+1) � uma antidiferen�a de Binom(k,m) e S_n(m)=Binom(n+1,m+1) - Binom(m,m+1) = Binom(n+1,m+1)
Fazendo m=k o resultado segue.
Um exerc�cio que acho interessante � tentar dar uma demonstra��o do tipo acima para cada propriedade do tri�ngulo de Pascal.
Concordo. Mas isso (dar interpreta��es combinat�rias) muitas vezes � muito dif�cil. Como exemplo, considere a soma
S_N(n) := \sum_{k>=n} Binom(N,2k) Binom(k,n) (n,N inteiros, n>=0, N>=1, N >=2n).
As solu��es combinat�rias aparecem em The Mathematical Gazette 79 (484, 486),
1995.
Eu iria por m�todos mais gerais, se bem que nesse caso tamb�m n�o � muito f�cil. Com algumas manipula��es chegamos a
S_N(n) = \sum_{k>=0} Binom(N,N-2n-2k) Binom(n+k,n).Isso � uma soma hipergeom�trica e usando as t�cnicas mostradas no livro (resultado de Gauss) Matem�tica Concreta obtemos S_N(n) = [N / (N-n)] Binom(N-n,n) 2^(N-2n-1).
[]'s Lu�s
From: "claudio.buffara" <[EMAIL PROTECTED]> Reply-To: [email protected] To: "obm-l" <[email protected]> Subject: Re: [obm-l] soma de termos Date: Wed, 6 Apr 2005 09:01:29 -0300
Oi, Bernardo:
Eu falei mal da indu��o porque acho que ela produz demonstra��es feias e sem-gra�a, apesar de em muitos casos, ser a �nica forma (conhecida) de se demonstrar algum resultado.
Mas n�o � o caso da lei das colunas: C(k,k) + C(k+1,k) + C(k+2,k) + ... + C(n,k) = C(n+1,k+1).
Imagine que voc� quer formar subconjuntos de {1, 2, 3, ..., n, n+1} com k+1 elementos.
Obviamente isso pode ser feito de C(n+1,k+1) maneiras diferentes.
Mas quantos destes subconjuntos tem o inteiro positivo p
(k+1 <= p <= n+1) como maior elemento?
Bem, uma vez escolhido p, e dado que p � o maior elemento, os demais k elementos s� podem ser escolhidos dentre {1, 2, ..., p-1} e de C(p-1,k) maneiras distintas.
Somando de p = k+1 at� p = n+1, obtemos o n�mero desejado:
C(k,k) + C(k+1,k) + ... + C(n,k)
Com todo o respeito � sua demonstra��o, acho esta mais elegante. Al�m disso, ela d� uma interpreta��o "concreta" para a lei das colunas.
***
Um exerc�cio que acho interessante � tentar dar uma demonstra��o do tipo acima para cada propriedade do tri�ngulo de Pascal.
[]s, Claudio.
========================================================================= Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================
