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

Re: [obm-l] soma de termos



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" <claudio.buffara@terra.com.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: "obm-l" <obm-l@mat.puc-rio.br>
>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
=========================================================================