patternMinor
Not able to simplify a sum over reciprocals of $\log i$
Viewed 0 times
logsimplifyreciprocalssumnotoverable
Problem
Every time I solve these questions, I get stuck at the end where I need to find a closed form for the summation.
Here in this case, I have reached until this point:
$$
\begin{align}
T(n) &= T(n-2) + 1/\lg n \\
&= T(n-4)+ 1/\lg(n-2) + 1/\lg n \\
&= T(n-6) + 1/\lg(n-4) + 1/\lg(n-2) + 1/\lg n. \qquad (1)
\end{align}
$$
Assuming $T(1) = 1$, I put $n - 6 = 1$ and substituted into (1):
$$ T(6) = T(1) + 1/\lg3+ 1/\lg 5+ 1/\lg7.$$
Now at this point I am not able to find out $\sum_{i=1}^n 1/\lg(2i-1)$.
On similar grounds , I become blank for another recurrence relation $T(n) = T(n-1)+1/\lg n$,
and my solution drills down up to here:
$$T(n) = T(1)+ 1/\lg2 + 1/\lg3 + 1/\lg4 + \cdots.$$
How do I evaluate such sums?
Here in this case, I have reached until this point:
$$
\begin{align}
T(n) &= T(n-2) + 1/\lg n \\
&= T(n-4)+ 1/\lg(n-2) + 1/\lg n \\
&= T(n-6) + 1/\lg(n-4) + 1/\lg(n-2) + 1/\lg n. \qquad (1)
\end{align}
$$
Assuming $T(1) = 1$, I put $n - 6 = 1$ and substituted into (1):
$$ T(6) = T(1) + 1/\lg3+ 1/\lg 5+ 1/\lg7.$$
Now at this point I am not able to find out $\sum_{i=1}^n 1/\lg(2i-1)$.
On similar grounds , I become blank for another recurrence relation $T(n) = T(n-1)+1/\lg n$,
and my solution drills down up to here:
$$T(n) = T(1)+ 1/\lg2 + 1/\lg3 + 1/\lg4 + \cdots.$$
How do I evaluate such sums?
Solution
The trick to evaluate these sums is integration. We have the following very useful inequality for a non-decreasing $f(i)$:
$$ \int_0^n f(x) dx \leq \sum_{i=1}^n f(i) \leq \int_1^{n+1} f(x) dx. $$
In your case, $f(i)$ is in fact non-increasing, and in that case we have
$$ \int_1^{n+1} f(x) dx \leq \sum_{i=1}^n f(i) \leq \int_0^n f(x) dx. $$
For example, we can estimate
$$ \int_2^{n+1} \frac{dx}{\log x} \leq \sum_{i=2}^n f(i) \leq \int_1^n \frac{dx}{\log x}. $$
Unfortunately, the antiderivative of $1/\log x$ is not an elementary function, but is known as the logarithmic integral $li(x)$. Asymptotically, $li(x) \sim x/\log x$, and so we deduce
$$ \sum_{i=2}^n \frac{1}{\lg i} = \Theta\left(\frac{n}{\log n}\right). $$
In this particular case, we can obtain these bounds directly. Since $1/\lg i \geq 1/\lg n$, we obtain a lower bound of $(n-1)/\lg n$. Conversely, for $i \geq \sqrt{n}$ we have $1/\lg i \leq 1/\lg \sqrt{n} = 2/\lg n$, and so
$$ \sum_{i=2}^n \frac{1}{\lg i} \leq \sqrt{n} \lg 2 + n \frac{2}{\lg n} = O\left(\frac{n}{\lg n}\right). $$
If you want to obtain better estimates on such sums, the way to go is Euler–Maclaurin summation, which can be used to obtain an asymptotic series for $\log n!$, for example.
$$ \int_0^n f(x) dx \leq \sum_{i=1}^n f(i) \leq \int_1^{n+1} f(x) dx. $$
In your case, $f(i)$ is in fact non-increasing, and in that case we have
$$ \int_1^{n+1} f(x) dx \leq \sum_{i=1}^n f(i) \leq \int_0^n f(x) dx. $$
For example, we can estimate
$$ \int_2^{n+1} \frac{dx}{\log x} \leq \sum_{i=2}^n f(i) \leq \int_1^n \frac{dx}{\log x}. $$
Unfortunately, the antiderivative of $1/\log x$ is not an elementary function, but is known as the logarithmic integral $li(x)$. Asymptotically, $li(x) \sim x/\log x$, and so we deduce
$$ \sum_{i=2}^n \frac{1}{\lg i} = \Theta\left(\frac{n}{\log n}\right). $$
In this particular case, we can obtain these bounds directly. Since $1/\lg i \geq 1/\lg n$, we obtain a lower bound of $(n-1)/\lg n$. Conversely, for $i \geq \sqrt{n}$ we have $1/\lg i \leq 1/\lg \sqrt{n} = 2/\lg n$, and so
$$ \sum_{i=2}^n \frac{1}{\lg i} \leq \sqrt{n} \lg 2 + n \frac{2}{\lg n} = O\left(\frac{n}{\lg n}\right). $$
If you want to obtain better estimates on such sums, the way to go is Euler–Maclaurin summation, which can be used to obtain an asymptotic series for $\log n!$, for example.
Context
StackExchange Computer Science Q#24067, answer score: 6
Revisions (0)
No revisions yet.