Solve a recurrence with $n/\log n$ Here is the question:

Let $T(n) = T(\frac{n}{\log_2(n)}) + 1$. Solve for $T(n).$

The answer is $T(n) = \Theta(\frac{\log_2(n)}{\log_2{\log_2 (n)}})$.
First of all what is the valid choice for $n$? The expression $f(n) = \frac{n}{\log_2(n)}$ should be a natural number. If we set $n = 2^{2^x}$, then $f(n)$ is a natural number but in the next level it could be non-integer. For example $n= 256$ leads to $n = 8$ and then $f(8) = \frac{8}{3}$ which is nonsense for $T(\frac{8}{3})$ isn't defined. Also I couldn't solve the recurrence. 
Note: Master Theorem isn't eligible.
 A: Calling $\log_2 n = a_n$ and considering $a_n > 0$
$$
T\left((a_n)^{\log_{a_n}n}\right)=T\left((a_n)^{\log_{a_n}n-1}\right)+1
$$
Calling now $\mathbb{T}(\cdot)=T\left((a_n)^{(\cdot)}\right)$ and $z = \log_{a_n}n$ we have the recurrence
$$
\mathbb{T}(z)=\mathbb{T}(z-1)+1
$$
with solution
$$
\mathbb{T}(z)=C_0(z)+z
$$
with $C_0(z)$ a generic periodic function with period $1$ that we will assume constant, or backwards
$$
T(n) = C_0 + \frac{\log_2 n}{\log_2(\log_2 n)}
$$
hence
$$
T(n) = \Theta\left(\frac{\log_2 n}{\log_2(\log_2 n)}\right)
$$
NOTE
for $a > 0, b > 0$
$$
b = a^{\log_a b}
$$
A: We often see recurrences like this, coming from computer science.  But (as we see from the OP) they normally do not have enough explanation to become a mathematical problem.  In this case, even if $n$ is an integer, it need not follow that $n/\log_2 n$ is an integer.
Here is one guess as to how this one should be formulated:  Suppose $T : [a,+\infty) \to (0,+\infty)$ is a sufficiently regular function.  [Meaning perhaps continuous, monotonic, $C^1$, $C^\infty$, analytic, or ...]  Suppose
$$
T(x) = T\left(\frac{x}{\log_2 x}\right) + 1\qquad \text{for all }x \in [a,\infty) \text{ such that } \frac{x}{\log_2 x} \in [a,+\infty).
$$
Then
$$
T(x) = \Theta\left(\frac{\log_2 x}{\log_2\log_2 x}\right)\qquad\text{as } x \to +\infty.
$$
A solution would mention what regularity is assumed.
A: I don't think there is a way to solve the recurrence exactly.
If we iterate,
$$T(n)=T\left(\frac n{\lg(n)}\right)+1
\\=T\left(\frac n{\lg(n)(\lg(n)-\lg(\lg(n)))}\right)+2$$
we can approximate as
$$\approx T\left(\frac n{\lg^2(n)}\right)+2$$
and inductively
$$\approx T\left(\frac n{\lg^k(n)}\right)+k.$$
Now we can estimate $k$ by imposing that the argument of $T$ reaches a constant value, say $1$, so that
$$n\approx\lg^k(n),$$ or 
$$k\approx\frac{\lg(n)}{\lg(\lg(n))}.$$

This is only meant to give some insight in the behavior of $T(n)$ and now remains to formally verify
$$T(n)=\Theta\left(\frac{\lg(n)}{\lg(\lg(n))}\right),$$ i.e. there are two constants such that
$$C_0\dfrac{\lg(n)}{\lg(\lg(n))}\le T(n)\le C_1\dfrac{\lg(n)}{\lg(\lg(n))}$$ for sufficiently large $n$.
