Oi, Ruy.
Para mim, o argumento combinatorio (separando em duas classes, etc.)
eh o mais elegante, e (para mim) mais do que serve como demonstracao.
Se voce realmente quiser fazer por inducao... bom, vamos supor que
C(n,p) seja definido indutivamente do jeito que a gente monta o
Triangulo de Pascal, isto eh:
C(0,0)=1 e C(0,p)=0 se p inteiro nao-nulo
C(n,p)=C(n-1,p)+C(n-1,p-1) para n=1,2,3,... e p inteiro qualquer.
(Consequencia mais ou menos imediata, que pode ser mostrada por
inducao se desejado: C(n,p)=0 se p0 ou pn)
Entao vamos provar o seu negocio por inducao em N=m+n onde m,n sao
inteiros nao-negativos.
a) Se N=0, entao tem de ser m=n=0. Entao fica C(0,p)=SOMA
C(0,k).C(0,p-k). Esta soma vai ser sempre nula, EXCETO quando p=0 e
entao temos um termo C(0,0).C(0,0) quando k=0. Ou seja, se p=0 a soma
dah 1=C(0,0), e se p0 dah 0=C(0,p). Funcionou.
b) Agora suponha que a propriedade eh valida para todos os pares (a,b)
com a+b=N, isto eh:
C(N,p)=C(a+b,p) = SOMA (C(a,k) x C(b, p-k)) (onde o somatorio eh em k).
Entao, se tivermos um par m+n=N+1, vem:
C(N+1,p)=C(N,p)+C(N,p-1)=C(m+n-1,p)+C(m+n-1,p-1)= (usando a hipotese
de inducao com a=m e b=n-1)
=SOMA(C(m,k).C(n-1,p-k) + SOMA(C(m,k).C(n-1,p-1-k)) =
= SOMA (C(m,k).(C(n-1,p-k)+C(n-1,p-1-k)))=
=SOMA(C(m,k).C(n,p-k))
mostrando que a propriedade eh valida para todos os pares (m,n) com m+n=N+1.
Por inducao em N, acabou.
(Note que, para mim, o indice k do somatorio vai de -Inf a +Inf, ou de
0 a p, em todos os somatorios -- sempre que ele sair das combinacoes
usuais, minha definicao diz que a combinacao correspondente eh 0,
nao afetando os somatorios. Alias, isto tem que ser pensado assim para
enunciar a propriedade do jeito que voce colocou -- se voce insistir
que C(a,-1) e C(a,a+1) nao existem e nao podem ser escritas, entao a
propriedade deveria ser:
C(m+n,p) = somatório(max(0,p-n)=k=min(p,m)) (C(m,k) . C(n, p-k))
o que, convenhamos, eh um porre. :) )
Abraco,
Ralph
2012/5/8 ruy de oliveira souza ruymat...@ig.com.br:
Faz muitos anos que não uso indução, estou apanhando para demonstrar que
C(m+n,p) = somatório(0=k=p)C(m,k) x C(n, p-k). O argumento de separarmos
em duas classes m e n para para combinarmos todos os agrupamentos com 0
elemtos da classe com m e p elemtos da classe com n ou agruparmos de todas
as maneiras 1 elemento da classe com m e p -1 elementos da classe com n
ou...ou p elemtos da classe com m e nenhum elemento da classe com n,
fazendo uso do princípio fundamental da contagem é válido como demonstração?
Alguém consegue por indução??? Agradeço antecipadamente a quem por ventura
responder. Abraço.
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=
