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

Re: [obm-l] soma de termos

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.
 
De: owner-obm-l@mat.puc-rio.br
Para: obm-l@mat.puc-rio.br
Cópia:
Data: Wed, 6 Apr 2005 08:21:31 -0300
Assunto: Re: [obm-l] soma de termos
> Oi, Brunno. Eu estava respondendo ontem quando acabou a luz, e aí
> acabei perdendo a linha. Acho que agora estará tudo certo:
>
> Primeiro, como você falou, está errado no local da soma, mas é C(n+1,
> 1+1), pois esta é a soma do último.
>
> Agora, vamos para a demonstração da lei das colunas (por indução,
> apesar de o Cláudio ter falado mal dela!)
> Teorema: SOMA {desde m=1até m=n} C(m, k) = C(n+1, k+1)
> Caso Base: n=1 (podia ser n=0)
> Temos duas possibilidades: k = 1 e k > 1
> Se k = 1, esta igualdade é 1 = C(1, 1) = C(1+1, 1+1) = C(2, 2) = 1, OK!
> Se k > 1, é 0 = C(1, k) = C(2, k+1) = 0 pois (k+1) > 2
>
> Agora, só falta o passo de indução:
> SOMA {desde m=1até m=(n+1)} C(m, k) = SOMA {desde m=1até m=n} C(m, k)
> + C(n+1, k), separando o último termo da soma,
> = C(n+1, k+1) + C(n+1, k) pela hipótese de indução
> = C( (n+1) + 1, k + 1), pela fórmula C(a, b+1) + C(a, b) = C(a+1, b+1)
> (Demonstre ela: é só expandir!)
>
> Eu acho que vale também para k negativo ou zero, mas isso eu deixo
> para você pensar (ah, e também tem o velho problema de definir quanto
> vale C(n, -32), mas isso é zero, eu acho) Para k=0, o teorema na
> verdade é uma coisa bem "trivial"!
>
> Abraços,
> --
> Bernardo Freitas Paulo da Costa
>