I was solving recurrence relation of Introduction to Algorithms by {Cormen, Leiserson, Rivest, Stein}, 3rd. edition. Problem 4-3 (i)
$ T(n) = T(n-2) + \frac{1}{lg \; n} $
I tried few ways, like expending with iteration method. With that i came up with the following equations - For even -
$ T(n) = T(0) + \frac{1}{lg \; n} + \frac{1}{lg \; (n-2)} + \frac{1}{lg \; (n-4)} + ... + \frac{1}{lg \; 6} + \frac{1}{lg \; 4} + \frac{1}{lg \; 2} $
For odd
$ T(n) = T(1) + \frac{1}{lg \; n} + \frac{1}{lg \; (n-2)} + \frac{1}{lg \; (n-4)} + ... + \frac{1}{lg \; 7} + \frac{1}{lg \; 5} + \frac{1}{lg \; 3} $
We can assume $T(1)=1$ and $T(0) = 1$. So to solve it I need to be able to sum up
$ \sum ^{n}_{i=2} \frac{1}{lg\;i} $
I was kinda lost, but got an idea from whuber from mathematica.stackexchange.com. We can view $1/lg(i)$ as the area of a rectangle of height $1/lg(i)$ and width $1$ centered at $i$, we have
$\sum_{i=2}^n \frac{1}{lg(i)} \approx \int_{x=3/2}^{n+1/2} \frac{dx}{lg(x)}.$
But that didn't help much in terms of typical asymptotic analysis. Some help will be greatly appreciated. Thanks.