# Solve the recurrence $T(n)=T(n-2)+\frac{1}{\lg{n}}$

Assume this recurrence: $$T(n)=T(n-2)+\frac{1}{\lg{n}}$$ I tried to draw its recurrence tree and I reached that the whole cost is $$\dfrac{1}{\lg{n}}+\dfrac{1}{\lg{n-2}}+\dots+\dfrac{1}{x}$$ that $$x$$ is $$2$$ if $$n$$ is even, otherwise is $$3$$. So somehow we should solve $$\sum_{i=1}^{\frac{n}{2}}{\dfrac{1}{\lg{2i}}}$$ or $$\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}{\dfrac{1}{\lg{2i+1}}}$$ that both equal to the same $$\Theta(f(n))$$. I read somewhere that it equals $$\Theta(\dfrac{n}{\lg{n}})$$, but I can't find out how. The lower bound is easy, but what about the upper bound?

Ignoring rounding (which does not affect the asymptotic growth rate): $$\sum_{i=1}^{n/2} \frac{1}{\log 2i} \ge \sum_{i=1}^{n/2} \frac{1}{\log n} \ge \frac{1}{2} \cdot \frac{n}{\log n} = \Omega\Big(\frac{n}{\log n}\Big),$$ and
\begin{align*} \sum_{i=1}^{n/2} \frac{1}{\log 2i} &= \sum_{i=1}^{\sqrt{n}/2} \frac{1}{\log 2i} + \sum_{i=\sqrt{n}/2}^{n/2} \frac{1}{\log 2i} \le \sqrt{n} + \frac{n}{\log \sqrt{n}} \\ & = O(\sqrt{n}) + \frac{1}{2} \cdot \frac{n}{\log n} = O\Big(\frac{n}{\log n}\Big). \end{align*}
Every recursion formula of the form $$T(n) = T(n-k) + f(n)$$ for sum fixed $$k$$ can be turned into a sum: $$T(n)$$ is the sum of $$f(n - i\times k)$$ for those $$i$$ where $$f(n - i\times k)$$ is not known, plus the first known value. In your case you would need to know $$T(1)$$ and $$T(0)$$ without the recursion formula.
Note that for $$\sqrt n ≤ j ≤ n$$ we have $$(\log j) / 2 ≤ \log j ≤ \log n$$.