How to solve the recurrence $T(n) = T(n − 2) + 1/\lg n$

Question

while solving this question, I use the iteration method, which comes to $$ T(n) = T(1) + \frac{1}{\lg n} + \frac{1}{\lg (n-2)} + \ldots + \frac{1}{\lg \left(n - 2^{k-1}\right)}. $$ I really have no idea to get the summation of those lg.

here is the summation

Can anyone give me some hint?

Answer 1

Assuming $n=2m$, you have $$ \begin{split} T(n) &= T(n-2) + \frac{1}{\lg n}\\ &= T(n-4) + \frac{1}{\lg n} + \frac{1}{\lg (n-2)} \\ &\ldots\\ &= T(0) + \sum_{k=1}^m \frac{1}{\lg (2k)}. \end{split} $$

If $n$ is odd, the last condition uses $T(1)$ and a slightly different summation...

I don't think there is a nice closed form for the sum, because $$ \int \frac{dx}{\lg(2x)} = \frac{\ln(2)}{2} \textrm{li}(2x) + C, $$ where $\textrm{li}(x)$ denotes the logarithmic integral function...