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: | [EMAIL PROTECTED] |
| Para: | [email protected] |
| 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
>
