A.1 – Fórmulas e propriedades de somatórios

Vou postar antes os exercícios e problemas do apêndice A, que trata especificamente de somatórios. Terminei o capítulo 4 já faz um bom tempo (cerca de um mês atrás), porém tive dificuldade em vários exercícios dele que envolviam somatórios, e por isso demorei muito tempo para conseguir terminá-lo. Devido a essa dificuldade, resolvi seguir a dica do autor e ir para o apêndice que trata sobre somatórios para reforçar minha base matemática nesse assunto. Então fica a dica de que é melhor olhar o apêndice A antes de tentar resolver os exercícios e problemas dos capítulos 3 e 4.

Essa seção traz uma compilação de fórmulas e propriedades dos somatórios, que é extremamente útil para resolver os exercícios e problemas encontrados nesse livro. Alguns exercícios dessa seção são de certa forma difíceis, pois nem todo conteúdo necessário para resolvê-los está presente no livro, fazendo com que tenhamos que pesquisar em outras referências.

Exercícios:

A.1.1) Determine uma fórmula simples para $\sum_{k=1}^{n} (2k - 1)$

$\sum\limits_{k=1}^{n} (2k-1) \\ \sum\limits_{k=1}^{n} 2k - \sum\limits_{k=1}^{n} 1 \\ 2\sum\limits_{k=1}^{n} k - n \\ 2 \times \dfrac{n(n+1)}{2} - n = n^2 + n - n = n^2$

A.1.2) Mostre que $\sum_{k=1}^{n} 1/(2k-1) = ln(\sqrt{n}) + O(1)$ , manipulando a série harmônica.

Seja Fn a série representada pelo somatório acima, temos que:

$F_n = 1 + \frac{1}{3} + \frac{1}{5} + \dotsb + \frac{1}{2n - 1}$

E seja Gn, e G’n respectivamente:

$G_n = \sum_{k=1}^{2n} \frac{1}{k} \\ G_n = 1 + \frac{1}{2} + \frac{1}{3} + \dotsb + \frac{1}{2n} \\ G'_n = \sum_{k=1}^{n} \frac{1}{2n} \\ G'_n = \frac{1}{2} + \frac{1}{4} + \dotsb + \frac{1}{2n}$

Podemos representar a série Fn subtraindo a série Gn pela série G’n:

$F_n = G_n - G'_n = \bigg( 1 + \frac{1}{2} + \frac{1}{3} + \dotsb + \frac{1}{2n} \bigg) - \bigg(\frac{1}{2} + \frac{1}{4} + \frac{1}{6} + \dotsb + \frac{1}{2n} \bigg) \\ F_n = G_n - G'_n = \bigg( 1 + \frac{1}{2} + \frac{1}{3} + \dotsb + \frac{1}{2n} \bigg) - \frac{1}{2}\bigg(1 + \frac{1}{2} + \frac{1}{3} + \dotsb + \frac{1}{n} \bigg)$

Podemos perceber que temos a série harmônica sendo subtraída, e podemos chegar no resultado final da seguinte maneira:

$\sum\limits_{k=1}^{2n} \frac{1}{k} - \frac{1}{2}\sum\limits_{k=1}^{n} \frac{1}{k} \\ ln(2n) + O(1) - \dfrac{ln(n) + O(1)}{2} \\ \dfrac{ln(n)}{2} + O(1) = ln(\sqrt{n}) + O(1)$

A.1.3) Mostre que $\sum_{k=0}^{\infty} k^2x^k = x(1+x)/(1-x)^3$ para $|x| < 1$ .

Tiramos um x pra fora do somatório e diferenciamos o somatório:

$\sum\limits_{k=0}^{\infty} k^2x^k \\ x \times \sum\limits_{k=0}^{\infty} k^2x^{k-1} \\\ x \times \dfrac{d}{dx}\bigg( \sum\limits_{k=0}^{\infty} k^2x^{k-1} \bigg) \\\ x \times \dfrac{d}{dx}\bigg( \dfrac{x}{(1-x)^2} \bigg) quad [A.8] \\\ x \times - \bigg( \dfrac{x+1}{(x-1)^3} \bigg) \\\ \dfrac{-x(x+1)}{(x-1)^3} = \dfrac{x(x+1)}{(1-x)^3}$

Para esse exercício tive ajuda da referência [2].

A.1.4) Mostre que $\sum_{k=0}^{\infty} (k-1)/2^k = 0$ .

$\sum\limits_{k=0}^{\infty} \dfrac{k-1}{2^k} \\\ \sum\limits_{k=0}^{\infty} \dfrac{k}{2^k} - \sum\limits_{k=0}^{\infty} \dfrac{1}{2^k} \\\ \sum\limits_{k=0}^{\infty} k\bigg(\dfrac{1}{2}\bigg)^k - \sum\limits_{k=0}^{\infty} \bigg(\dfrac{1}{2}\bigg)^k \\\ \dfrac{x}{(1-x)^2} - \dfrac{1}{1-x} \\\ \dfrac{2x-1}{(1-x)^2} = 0 to 2x - 1 = 0 to x = \frac{1}{2}$

Para esse exercício tive ajuda da referência [3].

A.1.5) Avalie a soma $\sum_{k=1}^{\infty} (2k+1)x^{2k}$ para $|x| < 1$ .

$\sum\limits_{k=1}^{\infty} (2k + 1)x^{2k} \\\ \dfrac{d}{dx}\bigg( \sum\limits_{k=1}^{\infty} x^{2k+1} \bigg) \\\ \dfrac{d}{dx}\bigg( x \times \sum\limits_{k=1}^{\infty} x^{2k} \bigg) \\\ \dfrac{d}{dx}\bigg( x \times \dfrac{x^2}{1 - x^2} \bigg) \\\ \dfrac{d}{dx}\bigg( \dfrac{x^3}{1 - x^2} \bigg) \\\ - \dfrac{x^2(x^2 - 3)}{(x^2 - 1)^2}$

Expandindo o somatório, podemos rapidamente perceber a expansão de f’(x) da seguinte maneira:

$f'(x) = x(x^2 + (x^2)^2 + (x^2)^4 + \dotsb )$

Que é claramente uma progressão geométrica decrescente infinita, já que |x| < 1.

A.1.6) Prove que $\sum_{k=1}^{n} O(f_k(i)) = O(\sum_{k=1}^{n} f_k(i))$ usando a propriedades de linearidade de somatórios.

Não consegui resolver esse exercício, mas fiz uns rascunhos onde tentei provar através de um modo fraco, usando o maior termo da série como constante c para provar o limite assintótico na inequação.

A.1.7) Avalie o \produto $\prod_{k=1}^{n} 2 \cdot 4^k$ .

Expandindo o \produtório:

$\prod\limits_{k=1}^{n} 2 \cdot 4^k \\\ underbrace{2 \cdot 2 \cdot ... \cdot 2}_text{n vezes} \times 4^1 \cdot 4^2 \cdot ... \cdot 4^n \\\ 2^n \times 4^{1 + 2 + \dotsb + n} \\\ 2^n \times 4^{\sum_{k=1}^{n}k} \\\ 2^n \times 4^{n(n+1)/2} \\\ 2^n \times 2^{2 \cdot n(n+1)/2} \\\ 2^n \times 2^{n^2 + n} \\\ 2^{n^2 + 2n} = 2^{n(n+2)}$

Usando log para transformar o \produtório em somatório:

$\prod\limits_{k=1}^{n} 2 \cdot 4^k \\\ 2^n \times \prod\limits_{k=1}^{n} 4^k \\\ lg\bigg( 2^n \times \prod\limits_{k=1}^{n} 4^k \bigg) \\\ lg(2^n) + lg\bigg( \prod\limits_{k=1}^{n} 4^k \bigg) \\\ n + \sum\limits_{k=1}^{n} lg(4^k) \\\ n + 2 \cdot \sum\limits_{k=1}^{n}k \\\ n + 2 \cdot \dfrac{n(n+1)}{2} \\\ n + n^2 + n = n^2 + 2n = n(n+2)$

Tirando o log: $2^{n(n+2)}$

A.1.8) Avalie o \produto $\prod_{k=2}^{n} (1 - 1/k^2)$ .

Acredito que o segredo dessa questão seja expandir o \produtório.

Sabemos que:

$1 - \dfrac{1}{k^2} = \bigg( 1 - \dfrac{1}{k} \bigg) \cdot \bigg( 1 + \dfrac{1}{k} \bigg) = \bigg( \dfrac{k-1}{k} \bigg) \cdot \bigg( \dfrac{k+1}{k} \bigg)$

O quê nos dá a seguinte expansão:

$\bigg( \dfrac{1}{2} \cdot \dfrac{3}{2} \bigg) \times \bigg( \dfrac{2}{3} \cdot \dfrac{4}{3} \bigg) \times \bigg( \dfrac{3}{4} \cdot \dfrac{5}{4} \bigg) \times \dotsb \times \bigg( \dfrac{n-1}{n} \cdot \dfrac{n+1}{n} \bigg)$

Onde fica visível que os termos intermediários são cancelados, sobrando apenas o primeiro e o último, resultando em:

$\prod\limits_{k=2}^{n} \bigg( \dfrac{k-1}{k} \bigg) \cdot \bigg( \dfrac{k+1}{k} \bigg) = \dfrac{1}{2} \cdot \dfrac{n+1}{n} = \dfrac{n+1}{2n}$

Gostaria de agradecer o pessoal do math.stackexchange por me ajudar na resolução dos exercícios A.1.3 e A.1.4. Logo abaixo estão os links de onde retirei a base para minha solução.

Referências:

[1] CORMEN, T.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Introdução à Algoritmos (Terceira Edição). MIT Press and McGraw-Hill. 2009.

[2] Respostas dos usuários science e Math-fun, que podem ser encontradas aqui: http://math.stackexchange.com/questions/1139819/show-that-\sum-k-0-\infty-k-1-2k-0

[3] Respostas dos usuários Mathmo123 e Abhishek Bakshi, que podem ser encontradas aqui: http://math.stackexchange.com/questions/847415/show-that-\sum-k-0-\inftyk2xk-fracx1x1-x3-for-0-x-1

mv.treviso

NLP, ML e etc.