Problemas Teoremas

Junho 25, 2011

Republicação da demonstração combinatória (ou combinatorial) da convolução de Vandermonde e de outra soma binomial

Filed under: Combinatória,Demonstração,Identidade matemática,Matemática,Matemática Discreta,Teorema,Teorema / Teoria — Américo Tavares @ 1:05 pm
Tags: , ,

(Inicialmente publicada nesta entrada.)

Proposição: É válida a seguinte identidade combinatória

\dbinom{n+m}{r}=\displaystyle\sum_{j=0}^{r}\dbinom{n}{j}\dbinom{m}{r-j}

que é a chamada convolução de Vandermonde.

Pondo n=m, obtém-se

\dbinom{2n}{r}=\displaystyle\sum_{j=0}^{r}\dbinom{n}{j}\binom{n}{r-j}

e para r=n, finalmente,

\dbinom{2n}{n}=\displaystyle\sum_{j=0}^{r}\dbinom{n}{j}\dbinom{n}{n-j}=\displaystyle\sum_{j=0}^{n}\dbinom{n}{j}^{2}=\sum_{i=0}^{n}\dbinom{n}{i}^{2}.

\bigskip

Demonstração:

Existe uma demonstração meramente combinatória da convolução de Vandermonde:

Dado o conjunto C = \left\{ c_{1,}c_{2},\ldots,c_{n},c_{n+1},c_{n+2},\ldots ,c_{n+m}\right\}, considerem-se dois subconjuntos de C disjuntos, isto é, sem elementos comuns, um C_{1}=\left\{ c_{1,}c_{2},\ldots ,c_{n}\right\} com n elementos e outro com m, C_{2}=\left\{ c_{n+1,}c_{n+2},\ldots ,c_{n+m}\right\}, tais que C=C_{1}\cup C_{2}.

O segundo membro conta o número de maneiras distintas de escolher r elementos de entre os n+m de C.

Quanto ao primeiro membro, comecemos por reparar que

(a) há \dbinom{n}{j} maneiras distintas de escolher j elementos entre os n de C_{1};

(b) há \dbinom{m}{r-j} maneiras distintas de escolher r-j elementos entre os m de C_{2};

(c) pelo que há \dbinom{n}{j}\dbinom{m}{r-j} maneiras distintas de seleccionar j elementos de C_{1} e simultaneamente r-j de C_{2}.

Ora, se somarmos todas estas parcelas \dbinom{n}{j}\dbinom{m}{r-j} para os possíveis valores que j pode tomar, desde j=0 até j=n, obtemos evidentemente o mesmo número \dbinom{n+m}{r}. Como mostrámos a igualdade dos dois membros da identidade da convolução de Vandermonde, concluímos a justificação. \blacksquare

Os casos particulares referidos obtêm-se imediatamente. A última identidade é também um caso particular de

Proposição: Quaisquer que sejam os inteiros k e n tais que 0\leq k \leq n, tem-se

\displaystyle\sum_{i=k}^{n}\dbinom{n}{i}^{2}\dbinom{i}{k}=\dbinom{n}{k}\dbinom{2n-k}{n}

que foi demonstrada aqui e que repito.

Demonstração:

Comecemos por reparar que poderíamos ter escolhido para limite inferior do somatório 0 , em vez de k, porque para i<k, \binom{i}{k}=0, por convenção usual.

O segundo membro (lado direito) conta o número de maneiras diferentes de escolher k elementos dum conjunto, tal como S=\left\{ s_{1},s_{2},\cdots,s_{n}\right\} com n elementos e, ao mesmo tempo, n elementos doutro conjunto, por exemplo X=\left\{ x_{1},x_{2},\ldots,x_{n},x_{n+1},\ldots,x_{2n-k}\right\} com 2n-k elementos.

Quanto ao primeiro membro, considerem-se dois subconjuntos de X disjuntos (sem elementos comuns), um X_{1}=\left\{x_{1},x_{2},\ldots,x_{n}\right\} com n elementos, e outro X_{2}=\left\{x_{n+1},\ldots,x_{2n-k}\right\} com 2n-k elementos, tais que X_{1}\cup X_{2}=X.

Escolhamos agora n elementos de X pertencendo i deles a X_{1} e n-i a X_{2}, com 0\leq i\leq n.

(a) Há \dbinom{n}{i} maneiras diferentes de escolher i elementos entre os n de X_{1};

(b) há \dbinom{n-k}{n-i}=\dbinom{n-k}{i-k} maneiras diferentes de escolher n-i elementos entre os n-k de X_{2};

(c) daqui decorre que, para um dado i, há \dbinom{n}{i}\dbinom{n-k}{i-k} maneiras distintas de seleccionar esses n elementos de X. Assim, cada parcela, \dbinom{n}{i}\dbinom{n-k}{i-k}\dbinom{n}{k} conta o número de maneiras diferentes de escolher n elementos de X (dos quais i\in X_{1} ) e, simultaneamente, k de S. Somando, para todos os possíveis valores de i , estas parcelas, obtemos o número total

\displaystyle\sum_{i=0}^{n}\dbinom{n}{i}\dbinom{n-k}{i-k}\dbinom{n}{k}=\displaystyle\sum_{i=0}^{n}\dbinom{n}{i}^{2}\dbinom{i}{k}=\sum_{i=k}^{n}\dbinom{n}{i}^{2}\dbinom{i}{k}

A primeira igualdade é justificada por

\dbinom{n}{k}\dbinom{n-k}{i-k}=\dbinom{n}{i}\dbinom{i}{k}

e a segunda pela observação inicial.

É claro que as duas contagens, a directa representada pelo produto do segundo membro e a indirecta, pela soma do primeiro (lado esquerdo) hão-de ser iguais, o que mostra

\displaystyle\sum_{i=k}^{n}\dbinom{n}{i}^{2}\dbinom{i}{k}=\dbinom{n}{k}\dbinom{2n-k}{n},

como pretendíamos. \blacksquare

Nota: o leitor poderá ver várias demonstrações algébricas e analíticas no blogue Fatos Matemáticos do Prof. Paulo Sérgio, na entrada   Algumas Demonstrações da Convolução de Vandermonde-Euler.

Outubro 16, 2010

Problema do mês :: Problem of the month #7

Filed under: Combinatória,Combinatorics,Matemática,Matemática Discreta,Math,Problem,Problem Of The Month,Problema do mês,Problemas — Américo Tavares @ 6:11 pm
Tags: ,

pdmpom20101017


Mostre que :: Show that

\displaystyle\sum_{n=k+1}^{N}\dfrac{(-1)^{n+k}n}{\displaystyle\binom{n}{k}\displaystyle\binom{n+k}{k}}-\displaystyle\sum_{n=k+1}^{N}\dfrac{(-1)^{n+k}n}{\displaystyle\binom{n-1}{k}\displaystyle\binom{n-1+k}{k}}

=\dfrac{k}{\displaystyle\binom{2k}{k}}+\dfrac{(-1)^{N+k-1}k}{\displaystyle\binom{N}{k}\displaystyle\binom{N+k}{k}}

 

Soluções: até 8 Novembro 2010, via acltavares@sapo.pt ou caixa de comentários.

Solutions: until November 8, 2010, via acltavares@sapo.pt or comment box.

Março 20, 2010

Relação de recorrência, recursiva ou equação às diferenças associada ao logaritmo de dois (ln 2)

Filed under: Combinatória,Demonstração,Identidade matemática,Matemática,Matemática Discreta,Recorrência,Sucessões,Teorema / Teoria,Teoria dos Números — Américo Tavares @ 4:31 pm
Tags: , , ,

As relações de recorrência associadas a \ln 2 são:

\left( n+1\right) b_{n+1}-3\left( 2n+1\right) b_{n}+nb_{n-1}=0\qquad n\geq 1\qquad \left( 1\right)

e

\left( n+1\right) a_{n+1}-3\left( 2n+1\right) a_{n}+na_{n-1}=0\qquad n\geq 1\qquad \left( 2\right)

em que, a_{0}=1,a_{1}=3 e b_{0}=0,b_{1}=2, podendo demonstrar-se  [1, secção 3] que

\dfrac{b_{n}}{a_{n}}\rightarrow \ln 2\qquad \left( 3\right) .

A fórmula explícita da sucessão \left( a_{n}\right) , — de inteiros — é, como demonstraremos, dada por:

a_{n}=\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}\dbinom{n+k}{k}\qquad \left( 4\right)

pelo que

a_{n+1}=\dbinom{2n+2}{n+1}+\displaystyle\sum_{k=0}^{n}\dbinom{n+1}{k}\dbinom{n+1+k}{k}

e

a_{n-1}=\displaystyle\sum_{k=0}^{n}\dbinom{n-1}{k}\dbinom{n-1+k}{k}

Vamos mostrar que \left( 4\right) verifica \left( 2\right) .

Escrevendo

B_{n,k}=-\left( 4n+2\right) \dbinom{n}{k}\dbinom{n+k}{k}

será

B_{n,k-1}=-\left( 4n+2\right) \dbinom{n}{k-1}\dbinom{n+k-1}{k-1}

Assim

B_{n,k}-B_{n,k-1}=

 

=-\left( 4n+2\right) \dbinom{n}{k}\dbinom{n+k}{k}+\left( 4n+2\right) \dbinom{n}{k-1}\dbinom{n+k-1}{k-1}

 

Substituindo agora a_{n+1},a_{n} e a_{n-1} na relação de recorrência, vem

\left( n+1\right) \left[ \dbinom{2n+2}{n+1}+\displaystyle\sum_{k=0}^{n}\dbinom{n+1}{k}\dbinom{n+1+k}{k}\right]

 

-3\left( 2n+1\right) \displaystyle\sum_{k=0}^{n}\dbinom{n}{k}\dbinom{n+k}{k}+n\displaystyle\sum_{k=0}^{n}\dbinom{n-1}{k}\dbinom{n-1+k}{k}=0

donde

-\left( n+1\right) \dbinom{2n+2}{n+1}=

 

=\displaystyle\sum_{k=0}^{n}\left[ \left( n+1\right) \dbinom{n+1}{k}\dbinom{n+1+k}{k}-3\left( 2n+1\right) \dbinom{n}{k}\dbinom{n+k}{k}\right] +\displaystyle\sum_{k=0}^{n}\left[n\dbinom{n-1}{k}\dbinom{n-1+k}{k}\right]

 

=\displaystyle\sum_{k=0}^{n}\left[ -\left( 4n+2\right) \dbinom{n}{k}\dbinom{n+k}{k}+\left( 4n+2\right) \dbinom{n}{k-1}\dbinom{n+k-1}{k-1}\right]

 

=\displaystyle\sum_{k=0}^{n}B_{n,k}-B_{n,k-1}

que é uma soma telescópica em k. Prosseguindo, tem-se

-\left( n+1\right) \dbinom{2n+2}{n+1}=B_{n,n}-B_{n,-1}=B_{n,n}

porque B_{n,-1}=0. Mas

B_{n,n}=-\left( 4n+2\right) \dbinom{2n}{n}

pelo que basta verificar que

\left( n+1\right) \dbinom{2n+2}{n+1}=\left( 4n+2\right) \dbinom{2n}{n}

é  uma identidade, o que deixo ao cuidado dos meus leitores.

__________

[1] Eric Reyssat, Irrationalité de \zeta (3) selon Apéry, Séminaire Delange-Pisot-Poitou (Théorie des nombres) 20e année, 1978/79, nº 6, 6 p.

P.S: retirei uma igualdade desnecessária para esta demonstração e acrescentei [1].

Março 15, 2009

Princípio de indução matemática aplicado a uma relação combinatória

Filed under: Combinatória,Indução matemática,Matemática,Problemas,Teoria dos Números — Américo Tavares @ 10:20 pm
Tags: ,

Prove que existe apenas um número natural  que verifica a relação

^{n\!}C_{n-2}=2^{n-2}-1

Sugestão: utilize o princípio de indução para provar que a relação não é satisfeita por nenhum natural superior a seis.

Esta ideia é devida a Vishal Lama (neste comentário em inglês).

Fevereiro 28, 2009

Exercícios algébricos simples de Combinatória

Filed under: Combinatória,Exercícios Matemáticos,Matemática,Matemática-Secundário,Problemas — Américo Tavares @ 10:59 pm
Tags: , , ,

1. Diga se existe algum número natural menor que 10 tal que:

^{n\!}C_{n-2}=2^{n-2}-1.

Justifique.

2. Prove que

 ^{n\!}C_{k}=\dfrac{n-k+1}{k}\times ^{n\!}C_{k-1}

3. Determine n de modo a que se tenha

 ^{n+3\!}C_{n}-^{n+2\!}C_{n-1}=15(n+1)

4. Determine n de modo a que se tenha

 ^{n\!}C_{2}=136

Resolução

A fórmula das combinações  ^{n\!}C_{k} é  ^{n\!}C_{k}=\dfrac{n!}{k!(n-k)!}

1. Neste caso tem-se

^{n\!}C_{n-2}=\dfrac{n!}{(n-2)!(n-(n-2))!}=\dfrac{n(n-1)}{2}

Então

  \dfrac{n(n-1)}{2}=2^{n-2}-1

é  equivalente a

 n(n-1)=2^{n-1}-2\Leftrightarrow n^{2}-n=2^{n-1}-2\Leftrightarrow n^{2}=2^{n-1}-2+n

Por tentativas chegamos à solução inteira n=6 (por sinal a  única). Os primeiros casos, começando em n=9 e continuando no sentido descendente são:

9^{2}=81 e 2^{9-1}-2+9=263

8^{2}=64 e 2^{8-1}-2+8=134

7^{2}=49 e 2^{7-1}-2+7=69

que são valores diferentes. Mas

6^{2}=36 e 2^{6-1}-2+6=36

6^{2}=2^{6-1}-2+6=36

 

Verificação:

^{n\!}C_{n-2}=2^{n-2}-1

^{6\!}C_{6-2}=\dfrac{6(6-1)}{2}=15

2^{6-2}-1=15

Os restantes, também diferentes, são

5^{2}=25 e 2^{5-1}-2+5=19

4^{2}=16 e 2^{4-1}-2+4=10

3^{2}=9 e 2^{3-1}-2+3=5

2^{2}=4 e 2^{2-1}-2+2=2

1^{2}=1 e 2^{1-1}-2+1=0

2. Como

 ^{n\!}C_{k}=\dfrac{n!}{k!(n-k)!}

 e

 ^{n\!}C_{k-1}=\dfrac{n!}{(k-1)!(n-(k-1)!}=\dfrac{n!}{(k-1)!(n-k+1)!}

vem

 \dfrac{^{n\!}C_{k}}{^{n\!}C_{k-1}}=\dfrac{\dfrac{n!}{k!(n-k)!}}{\dfrac{n!}{(k-1)!(n-k+1)!}}

=\dfrac{(k-1)!(n-k+1)(n-k)!}{k(k-1)!(n-k)!}=\dfrac{n-k+1}{k}

Logo

 ^{n\!}C_{k}=\dfrac{n-k+1}{k}\times ^{n\!}C_{k-1}

3. Como

 ^{n+3\!}C_{n}=\dfrac{(n+3)!}{n!(n+2-n)!}

=\dfrac{(n+3)(n+2)(n+1)}{2!}=\dfrac{(n+3)(n+2)(n+1)}{2}

e

^{n+2\!}C_{n-1}=\dfrac{(n+2)!}{(n-1)!(n+2-(n-1))!}=\dfrac{(n+2)(n+1)n}{6}

a igualdade indicada é  equivalente, sucessivamente, a

\dfrac{(n+3)(n+2)(n+1)}{2}-\dfrac{(n+2)(n+1)n}{6}=15(n+1)

3(n+3)(n+2)-(n+2)n=90

2n^{2}+13n-72=0

As duas soluções  são:

\dfrac{-13+\sqrt{745}}{4},\dfrac{-13-\sqrt{745}}{4}

Como nenhuma é  inteira, não  tem solução  nos naturais, pelo que não  há  nenhum valor de n que verifique a condição indicada.

4.  Como

^{n\!}C_{2}=\dfrac{n!}{2!(n-2)!}=\dfrac{n(n-1)(n-2)!}{2\times 1\times (n-2)!}=\dfrac{n(n-1)}{2}

e

 \dfrac{n(n-1)}{2}=136

\Leftrightarrow n(n-1)=2\times 136\Leftrightarrow n(n-1)=272\Leftrightarrow n^{2}-n-272=0

A solução  positiva é

n=\dfrac{1+\sqrt{1+4\times 272}}{2}=17

A negativa exclui-se por esse facto.

Verificação:

^{17\!}C_{2}=\dfrac{17\times 16}{2}=136.

Observação de 1-3-2009: comentário suprimido.

Nota de 15-3-2008: nesta entrada pode ver um problema de nível um pouco mais avançado que prolonga o exercício 1 a todos os naturais, aproveitando o 1º. comentário.

Julho 23, 2008

Probabilidades do Euromilhões

Filed under: Combinatória,Exercícios Matemáticos,Matemática,Matemática-Secundário,Probabilidades,Problemas — Américo Tavares @ 8:26 am
Tags: , , ,

 

O blogue A MATEMÁTICA ANDA POR AÍ publicou uma tabela onde se pode ler que as probabilidades de obter o 1º (5 números e 2 estrelas), 2º (5 números e 1 estrela) ou 3º (5 números e 0 estrelas) prémios são, respectivamente

\dfrac{\dbinom{45}{0}\dbinom{5}{5}\dbinom{7}{0}\dbinom{2}{2}}{\dbinom{50}{5}\dbinom{9}{2}},

\dfrac{\dbinom{45}{0}\dbinom{5}{5}\dbinom{7}{1}\dbinom{2}{1}}{\dbinom{50}{5}\dbinom{9}{2}}

e

\dfrac{\dbinom{45}{0}\dbinom{5}{5}\dbinom{7}{2}\dbinom{2}{0}}{\dbinom{50}{5}\dbinom{9}{2}}.

NOTAÇÃO: \dbinom{p}{q} é o chamado coeficiente binomial que é, noutra notação, o mesmo que as combinações de p, q a q: ^{p}C_{q} 

\displaystyle\dbinom{p}{q}=^{p}C_{q}=\frac{p!}{q!\left( p-q\right) !}=\frac{p\left( p-1\right)\left( p-2\right) \cdots \left( p-q+1\right) }{p!}

Verificação

O número total de casos possíveis CP é  dado pelo produto do número de casos possíveis relativamente à extracção dos cinco números (N) pelo número de casos possíveis relativamente à  das duas estrelas (E). Ora, como podem sair cinco números em 50, sem interessar a ordem da extracção, há N=\dbinom{50}{5} possibilidades distintas. Quanto às estrelas escolhem-se duas entre nove, pelo que E=\dbinom{9}{2}.

De

N=\dbinom{50}{5}=\dfrac{50\times 49\times 48\times 47\times 46}{5\times 4\times 3\times 2\times 1}=2118760

e

E=\dbinom{9}{2}=\dfrac{9\times 8}{2\times 1}=36

conclui-se que o número de casos possíveis é

CP=N\times E=\dbinom{50}{5}\times \dbinom{9}{2}=2118760\times 36=76275360

Sobre o de casos favoráveis, vejamos o caso do 1.º prémio. O apostador deve acertar em 5 números e 2 estrelas. Se
separarmos o conjunto dos números 1 a 50 em dois conjuntos, A o dos 5 números que foram extraídos e B o dos 45 restantes, o apostador deverá  ter acertado em todos os números de A e em nenhum de B. Há  apenas uma forma de acertar em todos os números de A, que se pode exprimir por \dbinom{5}{5}=1. E igualmente uma única forma de não  acertar \dbinom{45}{0}=1. O número de casos favoráveis de acertos nos números é então:

CFN=\dbinom{5}{5}\times \dbinom{45}{0}=1\times 1=1

Raciocinando de forma idêntica em relação às estrelas, chegamos ao número de casos favoráveis de acertos nas estrelas

CFE=\dbinom{2}{2}\times \dbinom{7}{0}=1

Assim o número de casos favoráveis de acertos nos números e nas estrelas é  apenas um:

CF=CFN\times CFE=\dbinom{5}{5}\times \dbinom{45}{0}\times \dbinom{2}{2}\times\dbinom{7}{0}=1

A probabilidade respectiva é pois

P=\dfrac{CF}{CP}=\dfrac{\dbinom{5}{5}\times \dbinom{45}{0}\times \dbinom{2}{2}\times \dbinom{7}{0}}{\dbinom{50}{5}\times \dbinom{9}{2}}=\dfrac{1}{76275360}

Em relação  ao 2.º prémio, mantém-se o número de 5 acertos nos números e, em vez de duas, o apostador passa a acertar numa estrela; a outra estrela em que apostou faz parte das sete que não saíram :

CFE=\dbinom{2}{1}\times \dbinom{7}{1}=14

Os casos favoráveis passam a

CF=CFN\times CFE=\dbinom{5}{5}\times \dbinom{45}{0}\times \dbinom{2}{1}\times\dbinom{7}{1}=14

e a probabilidade a

P=\dfrac{CF}{CP}=\dfrac{\dbinom{5}{5}\times \dbinom{45}{0}\times \dbinom{2}{1}\times \dbinom{7}{1}}{\dbinom{50}{5}\times \dbinom{9}{2}}=\dfrac{14}{76275360}

Finalmente, no 3.º prémio o apostador acerta em todos os números, mas em nenhuma estrela, ou seja as duas estrelas em que apostou fazem parte das 7 que não saíram, logo

CFE=\dbinom{2}{0}\times \dbinom{7}{2}=1\times \dfrac{7\times 6}{2\times 1}=21

O número de casos favoráveis passa a ser

CF=CFN\times CFE=\dbinom{5}{5}\times \dbinom{45}{0}\times \dbinom{2}{0}\times \dbinom{7}{2}=21

e a probabilidade

P=\dfrac{CF}{CP}=\dfrac{\dbinom{5}{5}\times \dbinom{45}{0}\times \dbinom{2}{0}\times \dbinom{7}{2}}{\dbinom{50}{5}\times \dbinom{9}{2}}=\dfrac{21}{76275360}.

25-5-2009: corrigido erro no denominador das fórmulas e acrescentada verificação.

16-5-2010: alterado ligeiramente o texto.

Maio 16, 2008

Fórmulas de Apéry

Filed under: Combinatória,Exercícios Matemáticos,Matemática,Matemática Discreta,Problemas,Teoria dos Números — Américo Tavares @ 7:19 am
Tags: , ,

Prove as seguintes fórmulas

  1. \displaystyle\sum_{k=1}^{K}\dfrac{a_{1}a_{2}...a_{k-1}}{(x+a_{1})(x+a_{2})...(x+a_{k})}=\dfrac{1}{x}-\dfrac{a_{1}a_{2}...a_{K}}{x(x+a_{1})(x+a_{2})...(x+a_{K})}\bigskip
  2. Caso particular para x=n^{2} e a_{k}=-k^{2}
    \displaystyle\sum_{k=1}^{n-1}\dfrac{\left( -1\right) ^{k-1}\left( k-1\right) !^{2}}{\left( n^{2}-1^{2}\right) ...\left( n^{2}-k^{2}\right) }=\dfrac{1}{n^{2}}-\frac{\left( -1\right) ^{n-1}\left( n-1\right) !^{2}}{n^{2}\left( n^{2}-1^{2}\right) ...\left[ n^{2}-\left( n-1\right) ^{2}\right] }\bigskip
  3. \displaystyle\sum_{n=1}^{N}\displaystyle\sum_{k=1}^{n-1}(-1)^{k}\left( \varepsilon _{n,k}-\varepsilon_{n-1,k}\right) =2\left( \displaystyle\sum_{n=1}^{N}\dfrac{1}{n^{3}}-\dfrac{2\left( -1\right) ^{n-1}}{n^{3}\dbinom{2n}{n}}\right)
    em que
    \displaystyle\varepsilon _{n,k}=\dfrac{1}{k^{3}\dbinom{n}{k}\dbinom{n+k}{k}}\bigskip
  4. \displaystyle\sum_{n=1}^{N}\displaystyle\sum_{k=1}^{n-1}\left( -1\right) ^{k}\left( \varepsilon_{n,k}-\varepsilon _{n-1,k}\right)=\displaystyle\sum_{k=1}^{N}\displaystyle\sum_{n=k+1}^{N}\left( -1\right) ^{k}\left( \varepsilon _{n,k}-\varepsilon _{n-1,k}\right)= =\displaystyle\sum_{k=1}^{N}\left( -1\right) ^{k}\left( \varepsilon _{N,k}-\varepsilon_{k,k}\right)\bigskip
  5. \displaystyle\sum_{k=1}^{N}\left( -1\right) ^{k}\left( \varepsilon _{N,k}-\varepsilon_{k,k}\right)=\displaystyle\sum_{k=1}^{N}\dfrac{\left( -1\right) ^{k}}{k^{3}\dbinom{N}{k}\dbinom{N+k}{k}}-\displaystyle\sum_{k=1}^{N}\dfrac{\left( -1\right) ^{k}}{k^{3}\dbinom{2k}{k}}\bigskip
  6. \displaystyle\sum_{n=1}^{N}\dfrac{1}{n^{3}}+\displaystyle\sum_{k=1}^{N}\dfrac{\left( -1\right) ^{k-1}}{2k^{3}\dbinom{N}{k}\dbinom{N+k}{k}}= \dfrac{5}{2}\displaystyle\sum_{k=1}^{N}\frac{\left( -1\right) ^{k-1}}{k^{3}\dbinom{2k}{k}}

Resolução: veja a secção 3 deste artigo de Alf van der Poorten

http://www.ift.uni.wroc.pl/~mwolf/Poorten_MI_195_0.pdf,

A proof that Euler Missed … (também disponível  aqui), ou veja estas minhas notas.

Dezembro 14, 2007

Probabilidades com cartas

Filed under: Combinatória,Exercícios Matemáticos,Matemática,Matemática-Secundário,Probabilidades,Problemas — Américo Tavares @ 8:20 am
Tags: ,

De um baralho de 52 cartas, correctamente baralhado, tiram-se cartas à sorte. Calcular a probabilidade de ao extrair:

  1. duas cartas serem ambas de Copas;
  2. duas cartas serem uma Dama e um Valete;
  3. três cartas serem todas de Ouros e entre elas figurar o Ás.

Respostas

  1. 1 / 17

  2. 8 / 663

 Resolução do 3.

Há 13 Ouros no baralho, pelo que a probabilidade de sair um Ouro ao extrair uma carta é 13 / 52. Como ficam 51 cartas, ao extrair a 2ª carta, a probabilidade de ser um Ouro é 12 / 51; e na 3ª extracção 1 / 50, uma vez que só há um Ás de Ouro. Logo, a probabilidade será

\displaystyle\frac{13}{52}\displaystyle\frac{12}{51}\displaystyle\frac{1}{50}=\displaystyle\frac{11}{11050}

No entanto, o Ás poderá ser extraído na 1ª, 2ª ou 3ª tiragem. Por isso a probabilidade pedida é tripla da anterior:

\displaystyle\frac{33}{11050} \qquad\blacktriangleleft

 

NOTA: A extracção de 3 cartas de uma só vez é equivalente a 3 tiragens sucessivas  sem reposição.

 

 

Dezembro 1, 2007

A note on a combinatorial identity related to the Apéry’s constant ζ(3)

Filed under: Caderno,Combinatória,Combinatorics,Demonstração,Matemática,Math,Proof — Américo Tavares @ 10:50 am
Tags: , , ,

pdf: included in Caderno (see “caderno” page)

Abstract. A purely combinatorial proof of an identity (that can be used to justify one step of the Apéry´s sequences formulas) is established. Equivalent formulas for the Apéry’s double sequences are also presented, as well as the numerical values of the first four lines of these sequences.

Novembro 30, 2007

Problemas – sete Exercícios sobre Combinatória e Somas

Filed under: Caderno,Combinatória,Exercícios Matemáticos,Matemática,Matemática Discreta,Problemas — Américo Tavares @ 8:08 am
Tags: , , ,

pdf: ver caderno

No caderno apresentam-se sete exercícios simples e suas resoluções.

Novembro 29, 2007

Anti-diferenças e Método de adição por partes

Filed under: Caderno,Combinatória,Matemática,Matemática Discreta,Matemáticas Gerais,Teorema / Teoria — Américo Tavares @ 8:33 am
Tags: ,

pdf: ver caderno

Resumo: O método de adição por partes traduz-se numa fórmula que pode ajudar a calcular certas somas, recorrendo a outras conhecidas, fazendo uso das chamadas  anti-diferenças. Permite calcular somas de produtos, desde que consigamos obter a anti-diferença de  um dos factores. (A  anti-diferença de a_i é a quantidade A_i tal que a_i = A_{i+1} - A_i).

Esta entrada está na continuação da das somas telescópicas (e respectivo exemplo). Da biografia consultada destaco, em português, o livro Matemática Finita, de Carlos André e Fernando Ferreira, edição da Universidade Aberta, 2000.

Ver descrição do  método no caderno.

Novembro 28, 2007

Somas telescópicas

Filed under: Caderno,Combinatória,Matemática,Teorema / Teoria — Américo Tavares @ 11:07 am
Tags: ,

pdf: ver caderno

Suponhamos que o somando a_{i} é decomponível numa diferença A_{i+1}-A_{i}. Então,

\displaystyle\sum_{i=0}^{n}a_{i}=\sum_{i=0}^{n}A_{i+1}-A_{i}=\sum_{i=0}^{n}A_{i+1}-\sum_{i=0}^{n}A_{i}.

Como

\displaystyle\sum_{i=0}^{n}A_{i+1}=\sum_{i=1}^{n+1}A_{i}=\left(\displaystyle\sum_{i=1}^{n}A_{i}\right) +A_{n+1}=A_{n+1}+\displaystyle\sum_{i=1}^{n}A_{i},

e

\displaystyle\sum_{i=0}^{n}A_{i}=A_{0}+\sum_{i=0}^{n}A_{i}

vem

\displaystyle\sum_{i=0}^{n}a_{i}=A_{n+1}+\sum_{i=1}^{n}A_{i}-A_{0}-\sum_{i=0}^{n}A_{i}=A_{n+1}-A_{0}.

 

leia o resto »

Página Seguinte »

Tema: Rubric. Blog em WordPress.com.