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,$$

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