3-5f

[wojtask]

No description provided.

[wojtask]

There are several ambiguities that prevent me from providing a solution to this subproblem. I've sent them to the Authors, along with other bugs I've spotted in Chapter 3, currently awaiting their response.

1. Without the assumption that both sums converge to positive numbers, the equation does not hold. For example, consider the function $f(k)$ over naturals, such that $f(0)=-2$ and $f(k)=1/k^2$ for $k>0$. Then, if $S=\mathbb{N}$, we have
   $$\sum_{k\in S}f(k)=-2+\sum_{k=1}^\infty1/k^2=-2+\pi^2/6<0.$$
   Then the set $\Theta(\sum_{k\in S}f(k))$ is empty.
2. Even with this assumption, I'm not sure how to interpret this equation in light of information provided in Section 3.2, particularly in the subsection "Proper abuses of asymptotic notation". The $\Theta$-notation on the left-hand side applies to the variable $k$, but what is the variable that the right-hand side applies to? Is it the size of the set $S$? But then, we can let $S$ be an infinite set, in which case I don't see what variable does that introduce on the right-hand side.
3. If $S$ is infinite, then the assumption says that there exist positive limits of both sums, say $L$ for the left-hand side sum and $R$ for the right-hand side sum. The choice of the set $S$ and a function $g(k)=\Theta(f(k))$ on the left-hand side determines $L$ and $R$, so they are constants, as they don't depend on $k$ or on the size of $S$. Then, the equation degrades to $L=\Theta(R)$, which trivially holds.
4. Some of those remarks probably apply to part (g) as well, but I haven't started thinking about that one, before fully understanding part (f).

[wojtask]

My research has led to a serious change---the parts (f) and (g) have been declared as flawed by the Authors, and they will be removed in the 4th printing! See the errata of the book.