Periodic functions summation order

36 Views Asked by At

It can be shown, if I am not mistaken, that for $g(n) \geq n,\; n \in \mathbb{N}$ holds: \begin{equation} F(n,g(n)) = \sum_{d=1}^{n}\sum_{k=1}^{g(n)} f(k,d) \sim \sum_{d=1}^{n} \frac{g(n)}{d}\sum_{k=1}^{d} f(k,d) \end{equation} where $ f(k, d) \geq 0 $ is any nonnegative periodic function of the argument $k$ and period $d$, for example: $k \bmod d$; $|\sin(\frac{d k}{\pi})|$. Similarity sign means the functions are in the same order.

Question: Does the next expression follow directly?: \begin{equation}\label{eq2} F(n,g(n)+1) - F(n,g(n)) \sim \sum_{d=1}^{n} \frac{1}{d}\sum_{k=1}^{d} f(k,d) \end{equation} If not, how can prove or disprove it?

1

There are 1 best solutions below

2
On BEST ANSWER

No, this does not follow from the previous expression, because in general, $f _1 \sim g_1$ and $f_2 \sim g_2$ does not imply $f_2 - f_1 \sim g_2 - g_1$. The $\sim$ relation can hide differences that can have quite large variance, for instance:

$$ n^2 \sim n^2, \qquad n^2 + n \sim n^2 + 1,$$ but $ n \not \sim 1$.

In your specific case, the LHS admits a trivial simplification:

$$F(n,g(n)+1) - F(n,g(n)) = \sum_{d=1}^n f(g(n)+1, d).$$

Whether this is of the same order as the sum of the first $d$ average values of $f(\cdot,d)$ depends somewhat on your quantifiers (can the constants depend on $f$ and $g$ or are they uniform in one or both?). But it does not seem true in a strict sense as one can choose $f, g$ so that LHS is exactly 0 for all $n$ but the RHS is non-zero for any non-trivial $f$.