Processing math: 43%

Qual das funções a seguir cresce mais rápido? Justifique sua resposta.
$f(n) = (\log n) (\log\log\log n)$
$g(n) = (\log\log n) (\log\log n)$

Solução: A função $f(n)$ cresce mais rápido. Há várias formas de ver isto, algumas delas listadas a seguir:

Substituir $n = 10^m$ . Daí fica uma comparação entre $m \log\log m$ e $\log^2 m$ , e sabemos que qualquer polinômio ganha de qualquer potência de $\log$ .
Aplicar $\log$ nas duas funções. Daí os produtos viram somas e fica uma comparação entre $\log\log n + \log\log\log\log n$ e $2\log\log\log n$ , onde fica claro que o duplo $\log$ ganha do triplo $\log$ .
Despreze o fator $\log\log\log n$ de $f(n)$ e considere o limite para $n \to \infty$ do quociente $g(n)/(\log n)$ . Calculando-o pela regra de L'Hospital, temos: $\lim_{n\to\infty} \dfrac{(\log\log n)^2}{\log n} = \lim_{n\to\infty} \dfrac{2 (\log\log n) \left(\frac{1}{\log n}\frac{1}{n}\right)} {\frac{1}{n}} = \lim_{n\to\infty} \dfrac{2 \log\log n}{\log n} = 0,$

$\log n$

$\log\log\log n$

$f(n)$

$g(n)$

Calcule o resultado da seguinte soma infinita:
$\sum_{i=1}^{\infty}\dfrac{i}{3^i} = \dfrac{1}{3} + \dfrac{2}{9} + \dfrac{3}{27} + \dfrac{4}{81} + \ldots$

Solução: O resultado é $3/4 = 0.75$ . Há várias formas de ver isto, algumas delas listadas a seguir:
- Pela dica dada em sala: $\begin{eqnarray*}\sum_{i=1}^{\infty}\dfrac{i}{3^i} &=& \dfrac{1}{3} + \dfrac{1}{9} + \dfrac{1}{27} + \dfrac{1}{81} + \ldots\\ &+& \dfrac{1}{9} + \dfrac{1}{27} + \dfrac{1}{81} + \ldots\\ &+& \dfrac{1}{27} + \dfrac{1}{81} + \ldots\\ &+& \dfrac{1}{81} + \ldots \end{eqnarray*}$ Cada linha dá uma PG, que pode ser somada facilmente. A primeira linha dá $1/2$ . Além disso, os resultados de cada linha formam também uma PG, já que cada linha é a anterior multiplicada por $1/3$ . Então temos: $\sum_{i=1}^{\infty}\dfrac{i}{3^i} = \sum_{i=0}^{\infty} \dfrac{1}{2}\left(\dfrac{1}{3}\right)^i = \dfrac{1}{2} \dfrac{3}{2} = \dfrac{3}{4}.$
- O exercício 3 da página 290 do Milne pede para descobrir $f(s)$ tal que $\Delta f(s) = sx^s$ . Uma resposta é $f(s) = \dfrac{1}{x-1}sx^s - \dfrac{1}{(x-1)^2}x^{s+1}.$ Note que nossa somatória se encaixa neste exercício, com $x = 1/3$ . Então temos $\sum_{s=1}^{\infty}\dfrac{s}{3^s} = f(\infty) - f(1) = -f(1),$ pois $f(\infty) = 0$ . Calculando $f(1)$ para $x=1/3$ obtemos $f(1) = \dfrac{1}{\frac{1}{3}-1}1 \left(\frac{1}{3}\right)^1 - \dfrac{1}{(\frac{1}{3}-1)^2}\left(\frac{1}{3}\right)^{1+1} = -\dfrac{1}{2}-\dfrac{1}{4} = -\dfrac{3}{4}.$ Logo, a soma dá $-f(1) = 3/4$ .