Muito obrigado Ralph...vocês da lista tem um altruísmo comovente. Já pensou?? Demonstrar tudo isso. Valeu rapaz....há esperança para a raça humana....Abraço. Ruy
Em 9 de maio de 2012 00:12, Ralph Teixeira <[email protected]> escreveu: > 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 p<0 ou p>n) > > 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 p<>0 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 <[email protected]>: > > 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 > ========================================================================= >
