Sum of series with log in each term [closed]

Question

I was solving recurrence relation of Introduction to Algorithms by CLRS, 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} $$

Some help will be greatly appreciated. Thanks.

Answer 1

Sums can often be closely approximated by integrals.

Viewing $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_{i=3/2}^{n+1/2} \frac{dx}{lg(x)}.$$

Mathematica expressions for the two sides are

f[n_] := Sum[1/Log[2, i], {i, 2, n}];
g[n_] := Evaluate @ Integrate[1/Log[2, x], {x, 2 - 1/2, n + 1/2}];

A plot shows show close the two areas really are:

With[{n = 10},
 Show[Plot[{g[x], g[Round[x]]}, {x, 3/2, n+1/2}, 
   PlotRange -> {Full, {0, Automatic}}, AxesOrigin -> {0, 0}, Filling -> 0],  
  DiscretePlot[f[i], {i, 2, n}, PlotStyle -> PointSize[0.015], 
   Filling -> 0, FillingStyle -> Directive[Black, Thick]]]]

We can ask what the integral is in closed form:

? g

It is a "LogIntegral". What you're interested in for analysis of algorithms is the aymptotic behavior as the argument grows large. Obtain this with a series expansion:

a = Simplify[Series[LogIntegral[j], {j, Infinity, 1}]]

It's a bit of a mess, but a moment's inspection will reveal that the first half can be ignored--it's just messing around with the possibility that $j$ is complex--and the $i$'s cancel in the second half. So we can invoke Simplify on that second half, obtaining

(j (24 + 6 Log[j] + 2 Log[j]^2 + Log[j]^3 + Log[j]^4))/Log[j]^5

As $j$ grows large, so do all these terms. The two fastest-growing are the $j$ in the numerator and the $\log(j)^5$ in the denominator. Focusing on them, we can determine they are the only ones that matter asymptotically:

Limit[a / ( j/Log[j]), j -> Infinity]

1

As a double check, let's plot how close the evident approximation $f(n) \approx \frac{n}{lg(n)}$ really is as $n$ grows large. The horizontal axis here is logarithmic:

ListPlot[Table[f[n] / (n / Log[2, n]), {n, 10^Range[5]}], 
 Joined -> True, PlotStyle -> Thick, AxesOrigin -> {0, 1}]

OK, it will take a while before $f(n)$ is very closely approximated by $\frac{n}{lg(n)}$, but up to a small constant multiple it really looks like $T(n) = O(\frac{n}{lg(n)})$.

Answer 2

RSolve[{ t[n + 2] - t[n] - 1/Log[n] == 0, t[0] == 1, t[1] == 1}, t[n], n]

Let's define T :

T[n_Integer /; n >= 0] = t[n] /. First[%]

Mathematica cannot further simplify the result, e.g. :

T[#] & /@ Range[6, 10]

unless one looks for numerical results :

T[#] & /@ Range[6, 10] // N

{3.16404, 2.53157, 3.72215, 3.04547, 4.20305}

or a plot of the functon T :

DiscretePlot[ T[n], {n, 100}]