The answer of a recursive equation: $T(n) = T(n /\log(n)) + 1$

Question

How to solve:

$$T(n) = T(n / \log(n)) + 1$$

I tried the recursive solution to reach $T(1)$, but I failed. The reason was that I could not find out after how many recursion I would reach $T(1)$.

Answer 1

First of all, it isn't $T(1)$ you are even approaching. Rearrange the equation: $$T\left(\frac n{\log n}\right) = T(n) - 1$$ And note that each starting value $n = x_k$ results in a sequence $$x_{k+1} = \frac{x_k}{\log x_k}$$

If we examine the function $y = \frac x{\log x}, x > 1$, then $$y' = \frac {\log x - 1}{\log^2 x}$$ The denominator is positive, so $y' < 0$ when $\log x < 1$ and $y' > 0$ when $\log x > 1$. I.e., the function is decreasing when $x < e$ and increasing when $x > e$. Its minimum will be at $e$. Note that $y(e) = e$.

So only when $x_k = e$ is $x_{k+1} = e$. Any non-$e$ starting $x_0$ will give you a sequence where $x_{k+1} \ne x_k$ for every $k$. Further because the minimum value of $y$ is $e$, we can say that no matter what $x_0 > 1, x_0 \ne e$ we start with, $x_1 > e$, and from then on the sequence decreases towards $e$, but never actually arrives at that value. (When $x_0 \le 0, x_1$ cannot be calculated. When $0 < x_0 \le 1, x_1 \le 0$, so $x_2$ cannot be calculated.)

So you cannot calculate values for this function by knowing $T(1)$, or even $T(e)$. You never get to that point by recursion. You could calculate values if you knew every $T(x)$ for $x$ in some neighborhood of $e$. But from the recursion formula alone, the best you can say is $$\liminf_{n \to e+} T(n) = -\infty$$