Problemas Teoremas

Abril 18, 2012

Desigualdade de Cauchy-Schwarz e Identidade de Lagrange

Filed under: Demonstração,Desigualdades matemáticas,Identidade matemática,Matemática,Matemática Discreta,Matemáticas Gerais,Teorema,Teorema / Teoria — Américo Tavares @ 10:21 am
Tags: , ,

Para comodidade dos leitores reuno aqui as demonstrações da desigualdade de Cauchy-Schwarz e da identidade de Lagrange.

Desigualdade de Cauchy-Schwarz

A desigualdade de Cauchy-Schwarz corresponde ao seguinte

Teorema: Para todo o vector \mathbf{x}=\left( x_{1},...,x_{n}\right) \in\mathbb{R}^{n} e todo o vector \mathbf{y}=\left( y_{1},\ldots ,y_{n}\right) \in\mathbb{R}^{n}, tem-se:

\left\vert \displaystyle\sum_{k=1}^{n}x_{k}y_{k}\right\vert \leq \left( \displaystyle\sum_{k=1}^{n}x_{k}^{2}\right) ^{1/2}\left( \displaystyle\sum_{k=1}^{n}y_{k}^{2}\right) ^{1/2}

ou

\left( \displaystyle\sum_{k=1}^{n}x_{k}y_{k}\right) ^2\leq\left( \displaystyle\sum_{k=1}^{n}x_{k}^2\right)\left( \displaystyle\sum_{k=1}^{n}y_{k}^2\right)

Demonstração

Qualquer que seja o real \lambda , tomo o vector \mathbf{x}-\lambda\mathbf{y}, e vou achar

\displaystyle\sum_{k=1}^{n}\left( x_{k}-\lambda y_{k}\right) ^{2}=\displaystyle\sum_{k=1}^{n}x_{k}^{2}-2\lambda \displaystyle\sum_{k=1}^{n}x_{k}y_{k}+\lambda ^{2}\displaystyle\sum_{k=1}^{n}y_{k}^{2}.

Seja qual for o \lambda , o trinómio do lado direito, em \lambda , não muda de sinal, é sempre positivo ou igual a zero, porque o número \displaystyle\sum_{k=1}^{n}\left( x_{k}-\lambda y_{k}\right) ^{2} é não negativo:

\displaystyle\sum_{k=1}^{n}x_{k}^{2}-2\lambda \displaystyle\sum_{k=1}^{n}x_{k}y_{k}+\lambda ^{2}\displaystyle\sum_{k=1}^{n}y_{k}^{2}\geq 0,

o que implica que o seu discriminante seja menor ou igual a zero

\Delta =\left( 2\displaystyle\sum_{k=1}^{n}x_{k}y_{k}\right) ^{2}-4\left( \displaystyle\sum_{k=1}^{n}y_{k}^{2}\right) \left( \displaystyle\sum_{k=1}^{n}x_{k}^{2}\right) \leq 0,

significando que

\left( \displaystyle\sum_{k=1}^{n}x_{k}y_{k}\right) ^{2}\leq \left( \displaystyle\sum_{k=1}^{n}y_{k}^{2}\right) \left( \displaystyle\sum_{k=1}^{n}x_{k}^{2}\right) .

Daqui pode ainda concluir-se que

\left\vert \displaystyle\sum_{k=1}^{n}x_{x}y_{k}\right\vert \leq \left( \displaystyle\sum_{k=1}^{n}x_{k}^{2}\right) ^{1/2}\left( \displaystyle\sum_{k=1}^{n}y_{k}^{2}\right) ^{1/2}.

Se algum dos vectores \mathbf{x,y} for nulo, esta relação é evidentemente verificada.

\square

O significado geométrico em \mathbb{R}^{3}desta desigualdade é o de que o produto interno de dois vectores é menor ou igual ao produto dos módulos (das normas) desses vectores.

Identidade de Lagrange

A identidade de Lagrange generaliza a desigualdade anterior.

Teorema: Identidade de Lagrange. Para os reais a_{k} e b_{k} (com 1\leq k\leq n) verifica-se

\left( \displaystyle\sum_{k=1}^{n}a_{k}b_{k}\right) ^{2}=\left( \displaystyle\sum_{k=1}^{n}a_{k}^{2}\right) \left( \displaystyle\sum_{k=1}^{n}b_{k}^{2}\right) -\displaystyle\sum_{i=1}^{n-1}\displaystyle\sum_{j=i+1}^{n}\left( a_{i}b_{j}-a_{j}b_{i}\right) ^{2}

Demonstração: O produto de duas somas com n termos cada é uma soma com n^{2} termos:

\left( \displaystyle\sum_{i=1}^{n}x_{i}\right) \left( \displaystyle\sum_{j=1}^{n}y_{j}\right) =\displaystyle\sum_{i=1}^{n}\displaystyle\sum_{j=1}^{n}x_{i}y_{j}

Os índices i e j de cada termo genérico x_{i}y_{j} podem ser iguais (i=j) ou o primeiro menor do que o segundo (i<j) ou maior (j<i). Separando estes três grupos de parcelas, vem

\displaystyle\sum_{i=1}^{n}\displaystyle\sum_{j=1}^{n}x_{i}y_{j}=\displaystyle\sum_{i=1}^{n}x_{i}y_{i}+\displaystyle\sum_{1\leq i<j\leq n}x_{i}y_{j}+\displaystyle\sum_{1\leq j<i\leq n}x_{i}y_{j}

=\displaystyle\sum_{i=1}^{n}x_{i}y_{i}+\displaystyle\sum_{i=1}^{n-1}\displaystyle\sum_{j=i+1}^{n}x_{i}y_{j}+\displaystyle\sum_{j=1}^{n-1}\displaystyle\sum_{i=j+1}^{n}x_{i}y_{j}

donde

\left( \displaystyle\sum_{i=1}^{n}x_{i}\right) \left( \displaystyle\sum_{j=1}^{n}y_{j}\right) =\displaystyle\sum_{i=1}^{n}x_{i}y_{i}+\displaystyle\sum_{i=1}^{n-1}\displaystyle\sum_{j=i+1}^{n}x_{i}y_{i}+\displaystyle\sum_{j=1}^{n-1}\displaystyle\sum_{i=j+1}^{n}x_{i}y_{i}

Particularizando, para x_{i}=a_{i}^{2} e y_{j}=b_{j}^{2} obtém-se

\left( \displaystyle\sum_{i=1}^{n}a_{i}^{2}\right) \left( \displaystyle\sum_{j=1}^{n}b_{j}^{2}\right) =\displaystyle\sum_{i=1}^{n}a_{i}^{2}b_{i}^{2}+\displaystyle\sum_{i=1}^{n-1}\displaystyle\sum_{j=i+1}^{n}a_{i}^{2}b_{j}^{2}+\displaystyle\sum_{j=1}^{n-1}\displaystyle\sum_{i=j+1}^{n}a_{i}^{2}b_{j}^{2}

e para x_{i}=y_{i}=a_{i}b_{i}

\left( \displaystyle\sum_{i=1}^{n}a_{i}b_{i}\right) ^{2}=\left( \displaystyle\sum_{i=1}^{n}a_{i}b_{i}\right) \left( \displaystyle\sum_{i=1}^{n}a_{i}b_{i}\right)

=\displaystyle\sum_{i=1}^{n}a_{i}^{2}b_{i}^{2}+\displaystyle\sum_{i=1}^{n-1}\displaystyle\sum_{j=i+1}^{n}a_{i}b_{i}a_{j}b_{j}+\displaystyle\sum_{j=1}^{n-1}\displaystyle\sum_{i=j+1}^{n}a_{i}b_{i}a_{j}b_{j}

Ora

\displaystyle\sum_{i=1}^{n-1}\displaystyle\sum_{j=i+1}^{n}a_{i}b_{i}a_{j}b_{j}=\displaystyle\sum_{j=1}^{n-1}\displaystyle\sum_{i=j+1}^{n}a_{i}b_{i}a_{j}b_{j}

pelo que

\left( \displaystyle\sum_{i=1}^{n}a_{i}b_{i}\right) ^{2}=\displaystyle\sum_{i=1}^{n}a_{i}^{2}b_{i}^{2}+2\displaystyle\sum_{i=1}^{n-1}\displaystyle\sum_{j=i+1}^{n}a_{i}b_{i}a_{j}b_{j}

Por outro lado

2a_{i}b_{i}a_{j}b_{j}=a_{i}^{2}b_{j}^{2}+a_{j}^{2}b_{i}^{2}-\left( a_{i}b_{j}-a_{j}b_{i}\right) ^{2}

donde

\left( \displaystyle\sum_{i=1}^{n}a_{i}b_{i}\right) ^{2}=\displaystyle\sum_{i=1}^{n}a_{i}^{2}b_{i}^{2}+\displaystyle\sum_{i=1}^{n-1}\displaystyle\sum_{j=i+1}^{n}a_{i}^{2}b_{j}^{2}+

\displaystyle\sum_{i=1}^{n-1}\displaystyle\sum_{j=i+1}^{n}a_{j}^{2}b_{i}^{2}-\displaystyle\sum_{i=1}^{n-1}\displaystyle\sum_{j=i+1}^{n}\left( a_{i}b_{j}-a_{j}b_{i}\right) ^{2}

=\left( \displaystyle\sum_{i=1}^{n}a_{i}^{2}\right) \left( \displaystyle\sum_{j=1}^{n}b_{j}^{2}\right) -\displaystyle\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\left( a_{i}b_{j}-a_{j}b_{i}\right) ^{2}

visto que, por troca dos índices i e j, se tem

\displaystyle\sum_{i=1}^{n-1}\displaystyle\sum_{j=i+1}^{n}a_{j}^{2}b_{i}^{2}=\displaystyle\sum_{j=1}^{n-1}\displaystyle\sum_{i=j+1}^{n}a_{i}^{2}b_{j}^{2}

provando-se assim a identidade indicada acima.

\square

Ficheiro pdf

Abril 16, 2012

Relação de recorrência linear homogénea de 2.ª ordem com coeficientes constantes

Filed under: Matemática,Matemática Discreta,Mathematics Stack Exchange,Recorrência — Américo Tavares @ 12:25 am
Tags: ,

Numa questão de optimus, no Mathematics Stack Exchange pede-se a determinação da solução de

a_{n}-a_{n-1}-2a_{n-2}=0,\qquad a_0=2,a_1=4

A tradução da minha resposta é esta:

A recorrência/equação com diferenças homogénia de 2.ª ordem com coeficientes constantes

x_{n}+c_{1}x_{n-1}+c_{2}x_{n-2}=0\qquad (1)

tem duas soluções fundamentais (\lambda _{1}^{n})_{n\geq 0} e (\lambda_{2}^{n})_{n\geq 0}, em que \lambda _{1},\lambda _{2} são os zeros do polinómio característico

\lambda ^{2}+c_{1}\lambda +c_{2}\qquad (2)

Confirmemos.

\begin{aligned}\lambda _{1}^{n}+c_{1}\lambda _{1}^{n-1}+c_{2}\lambda _{1}^{n-2}&=\lambda_{1}^{n-2}\left( \lambda _{1}^{2}+c_{1}\lambda _{1}+c_{2}\right) \equiv 0\\ &\\\lambda _{2}^{n}+c_{1}\lambda _{2}^{n-1}+c_{2}\lambda _{2}^{n-2}&=\lambda_{2}^{n-2}\left( \lambda _{2}^{2}+c_{2}\lambda _{2}+c_{2}\right)\equiv 0\end{aligned}

Se \lambda _{1}\neq \lambda _{2} a solução geral de (1) é a combinação linear de \lambda _{1}^{n} e \lambda _{2}^{n}

x_{n}=A\lambda _{1}^{n}+B\lambda _{2}^{n}\qquad (3)

como pode confirmar substituindo (3) em (1). Apliquemos este resultado a equação com diferenças a_{n}-a_{n-1}-2a_{n-2}=0. O polinómio característico \lambda ^{2}-\lambda -2 tem os zeros \lambda_{1}=-1,\lambda _{2}=2.

Logo (3) fica

a_{n}=A(-1)^{n}+B2^{n}

As constantes A and B determinam-se usando as condições iniciais a_{0}=2, a_{1}=4:

a_{0}=A(-1)^{0}+B2^{0}=A+B=2\Leftrightarrow B=2-A

Assim

a_{n}=A(-1)^{n}+\left( 2-A\right) 2^{n}

e

a_{1}=A(-1)^{1}+\left( 2-A\right) 2^{1}=-A+4-2A=-3A+4=4\Leftrightarrow A=0.

Uma vez que A=0 e B=2-A=2 a solução é

a_{n}=2\cdot 2^{n}=2^{n+1}\qquad n\geq 2.

Setembro 7, 2011

Soma dos quadrados dos primeiros n números inteiros positivos

Filed under: Demonstração,Matemática,Matemática Discreta,Matemáticas Gerais,Mathematics Stack Exchange — Américo Tavares @ 9:43 am
Tags: , , ,

Em resposta a uma questão  de George Edison, no MSE, apresentei as seguintes duas demonstrações de

\displaystyle\sum_{k=1}^nk^2 = \dfrac{n(n+1)(2n+1)}{6}

Demonstração 1. (Dias Agudo, Cândido da Silva, Matemáticas Gerais III, Exercício 2.5.1). Seja S:=\sum_{k=1}^{n}k^{2}. Considere-se (1+a)^{3}=1+3a+3a^{2}+a^{3} e some-se (1+a)^{3} para a=1,2,\ldots ,n:

\begin{aligned}(1+1)^{3} &=1+3\cdot 1+3\cdot 1^{2}+1^{3} \\(1+2)^{3} &=1+3\cdot 2+3\cdot 2^{2}+2^{3} \\(1+3)^{3} &=1+3\cdot 3+3\cdot 3^{2}+3^{3} \\&\cdots \\(1+n)^{3} &=1+3\cdot n+3\cdot n^{2}+n^{3}\end{aligned}

O termo (1+1)^3 no primeiro membro da primeira soma cancela o termo 2^3 no segundo membro da segunda, (1+2)^3, o 3^3, (1+3)^3, o 4^3, …, o (1+n-1)^3 cancela n^3. Assim

(1+n)^{3}=n+3\left( 1+2+\ldots +n\right) +3S+1

e

S=\dfrac{n(n+1)(2n+1)}{6},

porque

1+2+\ldots +n=\dfrac{n\left( n+1\right) }{2}.

Demonstração 2. (Balakrishnan, Combinatorics, Schaum’s Outline of Combinatorics, Exercício 1.42 ). De

\dbinom{k}{1}+2\dbinom{k}{2}=k+2\dfrac{k\left( k-1\right) }{2}=k^{2},

obtem-se

\begin{aligned}S &:=\displaystyle\sum_{k=1}^{n}k^{2}=\displaystyle\sum_{k=0}^{n}\dbinom{k}{1}+2\dbinom{k}{2}=\displaystyle\sum_{i=1}^{n}\dbinom{k}{1}+2\displaystyle\sum_{k=1}^{n}\dbinom{k}{2} \\&=\dbinom{n+1}{2}+2\dbinom{n+1}{3} \\&=\dfrac{n\left( n+1\right) \left( 2n+1\right) }{6}.\end{aligned}

Julho 8, 2011

Resolução da relação de recorrência T(n) = 3T(n-2) + 9, T(1) = T(2) = 1

Filed under: Exercícios Matemáticos,Matemática,Matemática Discreta,Problemas,Recorrência — Américo Tavares @ 7:15 pm
Tags: , ,

Mais uma vez publico aqui a tradução de uma resposta a uma questão no MSE. Desta vez trata-se da resolução da relação de recorrência

T(n)=3T(n-2)+9,\qquad T(1)=T(2)=1

pedida por Nir nesta questão. Apliquei a ideia fundamental indicada num comentário de Ross Millikan. Inicialmente enganei-me na resolução, fui alertado para o erro por user6312 e refi-la.

Os primeiros termos são:

\begin{aligned}T(1) &=T(2)=U(1)=1 \\T(3)&=T(4)=U(2)=12 \\T(5) &=T(6)=U(3)=45 \\&\cdots\end{aligned}

Generalizando, tem-se

T(2n-1)=T(2n)=U(n),\qquad n\ge 1.\qquad (1)

Dado que

T(2n-1)=3T(2n-3)+9=3T(2n-2)+9,

obtemos

U(1)=1,\qquad U(n)=3U(n-1)+9,\qquad n\ge 2.\qquad (2)

Vamos aplicar rudimentos da teoria das recorrências  (ou equações com diferenças, ver por ex. An introduction to difference equations de Saber Elaydi.) Esta relação de recorrência é não homogénea,  pelo que teremos de determinar uma solução particular da recorrência e resolver a recorrência homogénea, que é linear e tem coeficientes constantes . Assim, a solução explícita é da forma

U(1)=1,\qquad U(n)=AX^{n}+C,\qquad (3)

em que X é a raíz da equação característica X-3=0 associada à equação homogénea U(n)-3U(n-1)=0 e C é uma solução particular (neste caso, constante) de U(n)=3U(n-1)+9. De (2), deverá ser C=3C-9, isto é, C=-9/2. Assim U(n)=3^{n}A-9/2.

Da condição inicial U(1)=1, obtemos 1=3A-9/2, donde A=11/6. Por conseguinte a solução de (2) é

U(n)=\dfrac{11}{6}3^{n}-\dfrac{9}{2},\qquad n\ge 1\qquad (4)

Logo a solução da recorrência dada T(n)=3T(n-2)+9 é

T(2n-1)=T(2n)=U(n)=\dfrac{11}{6}3^{n}-\dfrac{9}{2},\qquad n\ge 1.\qquad (5)

Bibliografia (em português)

ANDRÉ, Carlos e FERREIRA, Fernando, Matemática Finita, Universidade Aberta, nº 203, Lisboa, 2000.

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.

Novembro 21, 2010

Cálculo de um somatório de uma fracção racional do índice

Filed under: LaTeX,Matemática,Matemática Discreta,Mathematics Stack Exchange — Américo Tavares @ 11:59 pm
Tags: , , ,

Mais uma vez trago para aqui a minha resposta (tradução) a uma pergunta (autor Slowsolver) no Mathematics Stack Exchange, sobre o cálculo do seguinte somatório:

\displaystyle\begin{aligned}S_{n}&=\displaystyle\sum_{k=0}^{n}\dfrac{n-k+1}{(n+1)(n+2)(n-k+2)}\\&=\dfrac{1}{(n+1)(n+2)}\displaystyle\sum_{k=0}^{n}\dfrac{n-k+1}{n-k+2}\quad (n+1)(n+2)\text{ independente de }k\\&=\dfrac{1}{(n+1)(n+2)}\displaystyle\sum_{m=2}^{n+2}\dfrac{m-1}{m}\qquad\text{substitui\c{c}\~{a}o }m=n-k+2\\&=\dfrac{1}{(n+1)(n+2)}\displaystyle\sum_{m=2}^{n+2}\left( 1-\dfrac{1}{m}\right)\\&=\dfrac{1}{(n+1)(n+2)}\left(\displaystyle\sum_{m=2}^{n+2}1\right)-\dfrac{1}{(n+1)(n+2)}\displaystyle\sum_{m=2}^{n+2}\dfrac{1}{m}\\&=\dfrac{n+2-2+1}{(n+1)(n+2)}-\dfrac{1}{(n+1)(n+2)}\left( \sum_{i=1}^{n+2}\dfrac{1}{i}\right) +\dfrac{1}{(n+1)(n+2)}\\&=\dfrac{n+1}{(n+1)(n+2)}-\dfrac{H_{n+2}}{(n+1)(n+2)}+\dfrac{1}{(n+1)(n+2)}\\&=\dfrac{n+2-H_{n+2}}{(n+1)(n+2)}\end{aligned}

em que

H_{n+2}=\displaystyle\sum_{i=1}^{n+2}\dfrac{1}{i}.

Notas:

  • H_n é o enésimo  número harmónico.
  • Na formatação utilizei os comandos \begin{aligned} e  \end{aligned} do  \LaTeX, como verá se passar pelas fórmulas com o rato.

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].

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.

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.

Tema: Rubric. Blog em WordPress.com.