Re: [obm-l] soma de termos
On Wed, Apr 06, 2005 at 03:58:30PM -0300, claudio.buffara wrote: Por exemplo, é possível dar uma demonstração combinatória da identidade abaixo, que foi uma questão da famosa e difícil prova do IME de 1980/81. SOMA(k=0...n) Binom(k,m)*Binom(n-k,m) = Binom(n+1,2m+1). Agora, quero ver alguém provar isso algebricamente... O fato (que não é difícil) que você deve conhecer para fazer isto algebricamente é que f_m(x) = x^m/(1-x)^(m+1) = soma_k binom(k,m) x^k. Assim o lado direito A é o coeficiente de x^n em (f_m(x))^2 = x^(2m)/(1-x)^(2m+2) = (1/x) f_(2m+1)(x). Portanto A é o coeficiente de x^(n+1) de f_(2m+1), ou seja, A = binom(n+1,2m+1). Mas eu concordo com o Claudio, prefiro a demonstração combinatoria. Alias, foi a que eu usei na prova (este foi o meu ano, e eu prestei o vestibular do IME, mas acabei não entrando lá). []s, N. = 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 =
[obm-l] Re: [obm-l] soma de termos e círculo tangente
Sauda,c~oes, E qual é a solução no arquivo acho que do Sérgio de provas do IME? Ele poderia acrescentar a dessa msg e a por indução. Essa solução do Nicolau deve mesmo ser a melhor algebricamente. Mas será que alguém a conhecia para fazer a prova? Imagino que os autores da questão pensavam na solução combinatória ou indução. A que eu apresento no livro faz manipulações no somando, como o Claudio andou sugerindo, mas é muito enrolada. Não estou conseguindo resolver o seguinte problema de cg: são dados um ângulo (imagine de 50 graus) e uma transversal cortando os dois lados do ângulo formando um triângulo de tamanho conveniente. Trace um círculo tangente aos lados do ângulo e determinando na transversal uma corda de comprimento igual ao raio do círculo. []'s Luís From: Nicolau C. Saldanha [EMAIL PROTECTED] Reply-To: obm-l@mat.puc-rio.br To: obm-l@mat.puc-rio.br Subject: Re: [obm-l] soma de termos Date: Thu, 7 Apr 2005 10:28:04 -0300 On Wed, Apr 06, 2005 at 03:58:30PM -0300, claudio.buffara wrote: Por exemplo, é possível dar uma demonstração combinatória da identidade abaixo, que foi uma questão da famosa e difícil prova do IME de 1980/81. SOMA(k=0...n) Binom(k,m)*Binom(n-k,m) = Binom(n+1,2m+1). Agora, quero ver alguém provar isso algebricamente... O fato (que não é difícil) que você deve conhecer para fazer isto algebricamente é que f_m(x) = x^m/(1-x)^(m+1) = soma_k binom(k,m) x^k. Assim o lado direito A é o coeficiente de x^n em (f_m(x))^2 = x^(2m)/(1-x)^(2m+2) = (1/x) f_(2m+1)(x). Portanto A é o coeficiente de x^(n+1) de f_(2m+1), ou seja, A = binom(n+1,2m+1). Mas eu concordo com o Claudio, prefiro a demonstração combinatoria. Alias, foi a que eu usei na prova (este foi o meu ano, e eu prestei o vestibular do IME, mas acabei não entrando lá). []s, N. = 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 =
Re: [obm-l] soma de termos
on 07.04.05 10:28, Nicolau C. Saldanha at [EMAIL PROTECTED] wrote: On Wed, Apr 06, 2005 at 03:58:30PM -0300, claudio.buffara wrote: Por exemplo, é possível dar uma demonstração combinatória da identidade abaixo, que foi uma questão da famosa e difícil prova do IME de 1980/81. SOMA(k=0...n) Binom(k,m)*Binom(n-k,m) = Binom(n+1,2m+1). Agora, quero ver alguém provar isso algebricamente... O fato (que não é difícil) que você deve conhecer para fazer isto algebricamente é que f_m(x) = x^m/(1-x)^(m+1) = soma_k binom(k,m) x^k. Eu nao conhecia essa identidade e, francamente, creio que nenhum vestibulando normal teria a ideia de usa-la na hora da prova, a menos que jah a tivesse visto antes. Enfim, como voce disse, nao eh dificil demonstrar (alias, acho que o lado esquerdo deveria ser (-x)^m/(1-x)^(m+1)). Eh soh derivar m vezes cada membro de: 1/(1-x) = SOMA(k=0) x^k (o que vale apenas quando |x| 1) obtendo: m!*(-1)^m/(1-x)^(m+1) = SOMA(k=m) (k!/(k-m)!)*x^(k-m) Multiplicando cada membro por x^m/m!, ficamos com: (-x)^m/(1-x)^(m+1) = SOMA(k=m) Binom(k,m)*x^k. Assim o lado direito A é o coeficiente de x^n em (f_m(x))^2 = x^(2m)/(1-x)^(2m+2) = (1/x) f_(2m+1)(x). Portanto A é o coeficiente de x^(n+1) de f_(2m+1), ou seja, A = binom(n+1,2m+1). Alias, pensando melhor, acho que somente alguem familiarizado com funcoes geratrizes e series formais usaria isso naquela questao. Certamente, nao era o meu caso na epoca em que prestei IME (um ano depois do seu) mas, por sorte, a prova de MAT1 de 1981/82 foi muito mais facil... Mas eu concordo com o Claudio, prefiro a demonstração combinatoria. Alias, foi a que eu usei na prova (este foi o meu ano, e eu prestei o vestibular do IME, mas acabei não entrando lá). Uma clarificacao: acabou nao entrando lah porque nao quis, pois, pra quem nao sabe, o Nicolau foi 1o. colocado no vestibular do IME daquele ano. []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 =
Re: [obm-l] soma de termos
Na verdade, a formula original do Nicolau tava certa: A m-esima derivada de 1/(1-x) eh mesmo m!/(1-x)^(m+1). O - do x cancela o - do expoente em cada derivada sucessiva de (1-x)^(-k). Nossa! Nao estou conseguindo nem derivar uma funcao boba dessas...acho que tah na hora de tirar umas ferias... []s, Claudio. on 07.04.05 19:48, Claudio Buffara at [EMAIL PROTECTED] wrote: on 07.04.05 10:28, Nicolau C. Saldanha at [EMAIL PROTECTED] wrote: On Wed, Apr 06, 2005 at 03:58:30PM -0300, claudio.buffara wrote: Por exemplo, é possível dar uma demonstração combinatória da identidade abaixo, que foi uma questão da famosa e difícil prova do IME de 1980/81. SOMA(k=0...n) Binom(k,m)*Binom(n-k,m) = Binom(n+1,2m+1). Agora, quero ver alguém provar isso algebricamente... O fato (que não é difícil) que você deve conhecer para fazer isto algebricamente é que f_m(x) = x^m/(1-x)^(m+1) = soma_k binom(k,m) x^k. Eu nao conhecia essa identidade e, francamente, creio que nenhum vestibulando normal teria a ideia de usa-la na hora da prova, a menos que jah a tivesse visto antes. Enfim, como voce disse, nao eh dificil demonstrar (alias, acho que o lado esquerdo deveria ser (-x)^m/(1-x)^(m+1)). Eh soh derivar m vezes cada membro de: 1/(1-x) = SOMA(k=0) x^k (o que vale apenas quando |x| 1) obtendo: m!*(-1)^m/(1-x)^(m+1) = SOMA(k=m) (k!/(k-m)!)*x^(k-m) Multiplicando cada membro por x^m/m!, ficamos com: (-x)^m/(1-x)^(m+1) = SOMA(k=m) Binom(k,m)*x^k. Assim o lado direito A é o coeficiente de x^n em (f_m(x))^2 = x^(2m)/(1-x)^(2m+2) = (1/x) f_(2m+1)(x). Portanto A é o coeficiente de x^(n+1) de f_(2m+1), ou seja, A = binom(n+1,2m+1). Alias, pensando melhor, acho que somente alguem familiarizado com funcoes geratrizes e series formais usaria isso naquela questao. Certamente, nao era o meu caso na epoca em que prestei IME (um ano depois do seu) mas, por sorte, a prova de MAT1 de 1981/82 foi muito mais facil... Mas eu concordo com o Claudio, prefiro a demonstração combinatoria. Alias, foi a que eu usei na prova (este foi o meu ano, e eu prestei o vestibular do IME, mas acabei não entrando lá). Uma clarificacao: acabou nao entrando lah porque nao quis, pois, pra quem nao sabe, o Nicolau foi 1o. colocado no vestibular do IME daquele ano. []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 = = 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 =
RE: [obm-l] soma de termos
usa a formula da soma dos cubos, 1=1^3 2=(1+1)^3 faz isso ate n depois soma tudo, note que os termos ao cubo se cancelam. um abraço, saulo. From: Brunno [EMAIL PROTECTED] Reply-To: obm-l@mat.puc-rio.br To: obm-l@mat.puc-rio.br Subject: [obm-l] soma de termos Date: Mon, 4 Apr 2005 13:07:44 -0300 Boa tarde pessoal da lista dentro de uma exercício, cheguei a soma de soma de = 1^2 + 2^2 + 3^2 ...n^2 e vi que tinha uma formula especifica n^3/3 + n^2/2 +n/6 mas como se chega a esta formula??? Um abraco _ Chegou o que faltava: MSN Acesso Grátis. Instale Já! http://www.msn.com.br/discador = 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 =
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
On Apr 4, 2005 5:01 PM, Brunno [EMAIL PROTECTED] wrote:
Unico engano é nessa passagem
Mas então temos SOMA 2*C(m, 2) + C(m,1) = 2*C(n+1, 3) + C(n, 2) (pelo
C(n, 2)
deveria ser C(n+1,2+1)
muito obrigado pela forca
se puder me ajuda com a demonstracao da soma de colunas
Um abraco
Do amigo brunno
- Original Message -
From: Bernardo Freitas Paulo da Costa [EMAIL PROTECTED]
To: obm-l@mat.puc-rio.br
Sent: Monday, April 04, 2005 1:38 PM
Subject: Re: [obm-l] soma de termos
Isto tem uma resposta muito legal com números binomiais:
Repare que m^2 = m(m-1) +m = 2*C(m, 2) + C(m, 1) (este C(a, b) é o
número de combinações de a, escolhendo b, que é equivalente a
a!
b! (a-b)!
Ora, o que você quer é somar tudo, de m=1 até n.
Mas então temos SOMA 2*C(m, 2) + C(m,1) = 2*C(n+1, 3) + C(n, 2) (pelo
teorema de soma de colunas! - Demonstre que SOMA C(m,k) = C(n+1, k+1)
usando a propriedade de que C(a, b) + C(a, b+1) = C(a+1, b+1) ). Agora
é só expandir.
Abraços,
--
Bernardo Freitas Paulo da Costa
On Apr 4, 2005 1:07 PM, Brunno [EMAIL PROTECTED] wrote:
Boa tarde pessoal da lista
dentro de uma exercício, cheguei a soma de
soma de = 1^2 + 2^2 + 3^2 ...n^2
e vi que tinha uma formula especifica
n^3/3 + n^2/2 +n/6
mas como se chega a esta formula???
Um abraco
=
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
=
=
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
=
=
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
=
Re: [obm-l] soma de termos
Oi, Bernardo:
Eu falei mal da indução porque acho queela 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 positivop
(k+1 = p = n+1) como maior elemento?
Bem, uma vez escolhido p, e dado que p é o maior elemento, os demais kelementos só podem ser escolhidos dentre {1, 2, ..., p-1} e deC(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:
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
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 [EMAIL PROTECTED]
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
=
Re: [obm-l] soma de termos
Oi, Luís:
A impressão que eu tenho é que, depois do "Generatingfunctionology", todos estes problemas podem ser resolvidos pela aplicação de algum algoritmo geral.
Mesmo, assim, acho que é um bom treino tentar achar demonstrações combinatórias pra recorrências e identidades envolvendo números binomiais.
Por exemplo, é possível dar uma demonstração combinatória da identidade abaixo, que foi uma questão da famosa e difícil prova do IME de 1980/81.
SOMA(k=0...n) Binom(k,m)*Binom(n-k,m) = Binom(n+1,2m+1).
Agora, quero ver alguémprovar isso algebricamente...
[]s,
Claudio.
De:
[EMAIL PROTECTED]
Para:
obm-l@mat.puc-rio.br
Cópia:
Data:
Wed, 06 Apr 2005 14:48:26 +
Assunto:
Re: [obm-l] soma de termos
Sauda,c~oes,
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" <[EMAIL PROTECTED]>
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
=
Re: [obm-l] soma de termos
Oi Cláudio.. Realmente é muito mais legal uma demonstração combinatória: Considere o conjunto dos números 0,1,2,3,...,n. Você quer escolher umsequencia a1 a2 ... a(2m+1) de 2m+1 elementos, o que pode ser feito de "lado direito modos".Por outro lado, para cada k=0...n, voce pode escolher o elemento k como sendo o termo do meio dessa sequencia, e então precisa escolher binomial(k,m) termos menores e binomial(n-k,m) termos maiores que k. Somando em k, vemos que a resposta é o lado esquerdo e está provado. Mas não é tão feio fazer algebricamente..Vamos generalizar e provar que Soma(k=0..n) Binomial(k,a)*Binomial(n-k,b) = Binomial (n+1,a+b+1) Por inducao em n. Para n=0 eh facil. Supondo valido para n fixo e a,b quaisquer, temos: Soma(k=0..n+1) Binomial(k,a)*binomial (n+1-k,b) = Soma(k=0..n) Binomial(k,a)*[Binomial(n-k,b)+Binomial(n-k,b-1)] + Binom(n+1,a)*Binom(0,b) Usando a hipotese indutiva, isso da: Binomial(n+1,a+b+1) + Binomial(n+1, a+b) = Binomial (n+2, a+b+1) Em particular, fazendo a=b=m voce tem a solucao do problema pedido ;) (tá, confesso que tentei fazer a indução direto antes e não consegui :) E demorei bem menos pra dar a solução combinatória do que por indução.. mas não resisti ao "quero ver alguém ..." :) Abraços, Marcio - Original Message - From: claudio.buffara To: obm-l Sent: Wednesday, April 06, 2005 3:58 PM Subject: Re: [obm-l] soma de termos Por exemplo, é possível dar uma demonstração combinatória da identidade abaixo, que foi uma questão da famosa e difícil prova do IME de 1980/81. SOMA(k=0...n) Binom(k,m)*Binom(n-k,m) = Binom(n+1,2m+1). Agora, quero ver alguémprovar isso algebricamente...
Re: [obm-l] soma de termos
Title: Re: [obm-l] soma de termos Oi, Marcio: O que eu tinha em mente, quando falei em solucao algebrica, era abrir os numeros binomais e tentar simplificar o emaranhado de fatoriais resultante. Mas como nao fui totalmente explicito, tenho que aceitar esta solucao indutiva. Talvez seja a vinganca da inducao pelo que eu andei falando a respeito dela :-) []s, Claudio. on 06.04.05 18:29, Marcio Cohen at [EMAIL PROTECTED] wrote: Oi Cláudio.. Realmente é muito mais legal uma demonstração combinatória: Considere o conjunto dos números 0,1,2,3,...,n. Você quer escolher um sequencia a1 a2 ... a(2m+1) de 2m+1 elementos, o que pode ser feito de lado direito modos. Por outro lado, para cada k=0...n, voce pode escolher o elemento k como sendo o termo do meio dessa sequencia, e então precisa escolher binomial(k,m) termos menores e binomial(n-k,m) termos maiores que k. Somando em k, vemos que a resposta é o lado esquerdo e está provado. Mas não é tão feio fazer algebricamente..Vamos generalizar e provar que Soma(k=0..n) Binomial(k,a)*Binomial(n-k,b) = Binomial (n+1,a+b+1) Por inducao em n. Para n=0 eh facil. Supondo valido para n fixo e a,b quaisquer, temos: Soma(k=0..n+1) Binomial(k,a)*binomial (n+1-k,b) = Soma(k=0..n) Binomial(k,a)*[Binomial(n-k,b)+Binomial(n-k,b-1)] + Binom(n+1,a)*Binom(0,b) Usando a hipotese indutiva, isso da: Binomial(n+1,a+b+1) + Binomial(n+1, a+b) = Binomial (n+2, a+b+1) Em particular, fazendo a=b=m voce tem a solucao do problema pedido ;) (tá, confesso que tentei fazer a indução direto antes e não consegui :) E demorei bem menos pra dar a solução combinatória do que por indução.. mas não resisti ao quero ver alguém ... :) Abraços, Marcio - Original Message - From: claudio.buffara mailto:[EMAIL PROTECTED] To: obm-l mailto:obm-l@mat.puc-rio.br Sent: Wednesday, April 06, 2005 3:58 PM Subject: Re: [obm-l] soma de termos Por exemplo, é possível dar uma demonstração combinatória da identidade abaixo, que foi uma questão da famosa e difícil prova do IME de 1980/81. SOMA(k=0...n) Binom(k,m)*Binom(n-k,m) = Binom(n+1,2m+1). Agora, quero ver alguém provar isso algebricamente...
Re: [obm-l] soma de termos
claudio.buffara wrote: Oi, Luís: A impressão que eu tenho é que, depois do Generatingfunctionology, todos estes problemas podem ser resolvidos pela aplicação de algum algoritmo geral. Mesmo, assim, acho que é um bom treino tentar achar demonstrações combinatórias pra recorrências e identidades envolvendo números binomiais. Por exemplo, é possível dar uma demonstração combinatória da identidade abaixo, que foi uma questão da famosa e difícil prova do IME de 1980/81. SOMA(k=0...n) Binom(k,m)*Binom(n-k,m) = Binom(n+1,2m+1). O algoritmo WZ consegue provar identidades entre termos hipergeométricos (como é o caso deste) sem problema algum, mas ele não obtém a expressão pra você, ela deve vir de alguma conjectura, por exemplo. O Wilf apresenta no livro dele o Snake Oil Method para resolução de algumas somas, mas não é um método que tem garantia de funcionar, ele simplesmente funciona razoavelmente bem. Alguém sabe dizer qual é o estado da arte em relação ao maquinário computacional que *determina* fórmulas fechadas para somatórios envolvendo termos hipergeométricos? [ ]'s = 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 =
Re: [obm-l] soma de termos
Isto tem uma resposta muito legal com números binomiais: Repare que m^2 = m(m-1) +m = 2*C(m, 2) + C(m, 1) (este C(a, b) é o número de combinações de a, escolhendo b, que é equivalente a a! b! (a-b)! Ora, o que você quer é somar tudo, de m=1 até n. Mas então temos SOMA 2*C(m, 2) + C(m,1) = 2*C(n+1, 3) + C(n, 2) (pelo teorema de soma de colunas! - Demonstre que SOMA C(m,k) = C(n+1, k+1) usando a propriedade de que C(a, b) + C(a, b+1) = C(a+1, b+1) ). Agora é só expandir. Abraços, -- Bernardo Freitas Paulo da Costa On Apr 4, 2005 1:07 PM, Brunno [EMAIL PROTECTED] wrote: Boa tarde pessoal da lista dentro de uma exercício, cheguei a soma de soma de = 1^2 + 2^2 + 3^2 ...n^2 e vi que tinha uma formula especifica n^3/3 + n^2/2 +n/6 mas como se chega a esta formula??? Um abraco = 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 =
Re: [obm-l] soma de termos
eu sei demonstrar assim: (1+0)^3 = 1 + 3(0) + 3(0)^2 + (0)^3 = 1 (1+1)^3 = 1 + 3(1) + 3(1)^2 + (1)^3 = 2^3 (1+2)^3 = 1 + 3(2) + 3(2)^2 + (2)^3 = 3^3 (1+3)^3 = 1 + 3(3) + 3(3)^2 + (3)^3 = 4^3 ... (1+n-1)^3 = 1+ 3(n-1) + 3(n-1)^2 + (n-1)^3 = n^3 (1+n)^3 = 1+ 3(n) + 3(n)^2 + (n)^3 = (n+1)^3 fazendo a soma e cancelando os termos ao cubo vc chega no somatorio desejado abraços MuriloRFL - Original Message - From: Brunno To: obm-l@mat.puc-rio.br Sent: Monday, April 04, 2005 1:07 PM Subject: [obm-l] soma de termos Boa tarde pessoal da lista dentro de uma exercício, cheguei a soma de soma de = 1^2 + 2^2 + 3^2 ...n^2 e vi que tinha uma formula especifica n^3/3 + n^2/2 +n/6 mas como se chega a esta formula??? Um abraco
Re: [obm-l] soma de termos
Bernardo agora não condigo comprovar o teorema da soma das colunas, poderia comprovar isto? Um abraco - Original Message - From: Bernardo Freitas Paulo da Costa [EMAIL PROTECTED] To: obm-l@mat.puc-rio.br Sent: Monday, April 04, 2005 1:38 PM Subject: Re: [obm-l] soma de termos Isto tem uma resposta muito legal com números binomiais: Repare que m^2 = m(m-1) +m = 2*C(m, 2) + C(m, 1) (este C(a, b) é o número de combinações de a, escolhendo b, que é equivalente a a! b! (a-b)! Ora, o que você quer é somar tudo, de m=1 até n. Mas então temos SOMA 2*C(m, 2) + C(m,1) = 2*C(n+1, 3) + C(n, 2) (pelo teorema de soma de colunas! - Demonstre que SOMA C(m,k) = C(n+1, k+1) usando a propriedade de que C(a, b) + C(a, b+1) = C(a+1, b+1) ). Agora é só expandir. Abraços, -- Bernardo Freitas Paulo da Costa On Apr 4, 2005 1:07 PM, Brunno [EMAIL PROTECTED] wrote: Boa tarde pessoal da lista dentro de uma exercício, cheguei a soma de soma de = 1^2 + 2^2 + 3^2 ...n^2 e vi que tinha uma formula especifica n^3/3 + n^2/2 +n/6 mas como se chega a esta formula??? Um abraco = 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 = = 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 =
Re: [obm-l] soma de termos
Unico engano é nessa passagem Mas então temos SOMA 2*C(m, 2) + C(m,1) = 2*C(n+1, 3) + C(n, 2) (pelo C(n, 2) deveria ser C(n+1,2+1) muito obrigado pela forca se puder me ajuda com a demonstracao da soma de colunas Um abraco Do amigo brunno - Original Message - From: Bernardo Freitas Paulo da Costa [EMAIL PROTECTED] To: obm-l@mat.puc-rio.br Sent: Monday, April 04, 2005 1:38 PM Subject: Re: [obm-l] soma de termos Isto tem uma resposta muito legal com números binomiais: Repare que m^2 = m(m-1) +m = 2*C(m, 2) + C(m, 1) (este C(a, b) é o número de combinações de a, escolhendo b, que é equivalente a a! b! (a-b)! Ora, o que você quer é somar tudo, de m=1 até n. Mas então temos SOMA 2*C(m, 2) + C(m,1) = 2*C(n+1, 3) + C(n, 2) (pelo teorema de soma de colunas! - Demonstre que SOMA C(m,k) = C(n+1, k+1) usando a propriedade de que C(a, b) + C(a, b+1) = C(a+1, b+1) ). Agora é só expandir. Abraços, -- Bernardo Freitas Paulo da Costa On Apr 4, 2005 1:07 PM, Brunno [EMAIL PROTECTED] wrote: Boa tarde pessoal da lista dentro de uma exercício, cheguei a soma de soma de = 1^2 + 2^2 + 3^2 ...n^2 e vi que tinha uma formula especifica n^3/3 + n^2/2 +n/6 mas como se chega a esta formula??? Um abraco = 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 = = 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 =
