What is the asymptotic upper bound of a variable in the functional equation $f(x)=\left\lceil\frac{f(x+1)}{\lceil\log_2(f(x+1))\rceil}\right\rceil$?

Question

We are given a recursive function $ f ( x ) = \left\lceil \frac { f ( x + 1 ) } { \lceil \log_2 ( f ( x + 1 ) ) \rceil } \right\rceil $. We know that $ f ( 1 ) = 2 $ and $ f ( a ) = n $. What is the asymptotic upper bound of $ a $ expressed in terms of $ n $?

Answer 1

$ \require {begingroup} \begingroup \def \Z {\mathbb Z ^ +} \def \Zs {\mathbb Z ^ + \setminus \{ 1 \}} \def \C {\mathcal C} \def \t {\quad \longrightarrow \quad} $ Let $ \Z $ be the set of positive integers and $ h : \Zs \to \Zs $ be the function defined with $ h ( y ) = \left\lceil \frac y { \left\lceil \log _ 2 y \right\rceil } \right\rceil $ for all $ y \in \Zs $. Here's one reading of your question:

Let $ \C $ be the family of all functions $ f : \Z \to \Zs $ such that $ f ( 1 ) = 2 $ and $ f ( x ) = h \big( f ( x + 1 ) \big) $ for all $ x \in \Z $. For $ n \in \Zs $, let $ A _ n $ be the set of all $ a \in \Z $ for which there is some $ f \in \C $ with $ f ( a ) = n $. What is the least upper bound of $ A _ n $?

Reading the question like this, the answer is that there is no upper bound (assuming $ A _ n \ne \varnothing $, which we will later show to be true). Consider any $ f \in \C $ with $ f ( a ) = n $ and define $ g : \Z \to \Zs $ with $$ g ( x ) = \begin {cases} 2 & 1 \le x \le m \\ f ( x - m + 1 ) & x > m \end {cases} $$ Then it's easy to see that $ g \in \C $ and $ g ( a + m - 1 ) = n $. As $ a + m - 1 $ can be as large as you want, $ A _ n $ is unbounded.

But the above only happens because $ h ( 2 ) \nless 2 $. $ 2 $ is the only element of $ \Zs $ with this property, and if we only consider those $ f \in C $ that $ f ( 2 ) \ne 2 $, this won't happen. I think that is what you intended, so I'll continue to follow this road. Note that as $ h ( y ) < y $ for all $ y \in \Zs $ with $ y \ne 2 $, any $ f \in \C $ with $ f ( 2 ) \ne 2 $ will be strictly increasing. In particular, for any $ n \in \Zs $ there will be at most one $ a \in \Z $ with $ f ( a ) = n $. For $ n \in \Zs $, let $ B _ n $ be the set of all $ a \in \Z $ for which there is some $ f \in \C $ with $ f ( 2 ) \ne 2 $ and $ f ( a ) = n $. Opposite to what happened to $ A _ n $, $ B _ n $ will have no more than a single element, since for any $ f \in \C $ and any $ x \in \Z $, $ f ( x ) $ is uniquely determined by $ f ( x + 1 ) $ through applying $ h $; this means that if $ f ( a ) = n $, you apply $ h $ repeatedly to $ n $, $ h ( n ) $ and so on, until you reach $ 2 $. This process always ends for those $ f $ with $ f ( 2 ) \ne 2 $, as they are strictly increasing, and when reaching $ 2 $ we know that that is $ f ( 1 ) $ and not $ f ( x ) $ for any other $ x $, and thus $ a $ will be the number of times you applied $ h $ plus one. The following lemma makes this precise, together with showing that starting with any $ n \in \Zs $ is always possible.

---

Lemma: Let $ n \in \Zs $.

1. For any $ f , g \in \C $ with $ f ( 2 ) \ne 2 \ne g ( 2 ) $, if there exist $ a , b \in \Z $ such that $ f ( a ) = n = g ( b ) $, then $ a = b $, and for all $ x \in \Z $ with $ x \le a $, $ f ( x ) = g ( x ) $.
2. There is some strictly increasing $ f \in \C $ and some $ a \in \Z $ such that $ f ( a ) = n $.
3. $ B _ n $ is a singleton, and its only element is $ a ( n ) $, where $ a : \Zs \to \Z $ is recursively defined with $ a ( 2 ) = 1 $ and $ a ( y ) = a \big( h ( y ) \big) + 1 $ for $ y > 2 $.

Proof:

1. Without loss of generality, assume that $ a \le b $. Use induction on $ x $ to prove $ f ( a - x ) = g ( b - x ) $ for all $ x < a $, noting that we have $ f ( a ) = g ( b ) $ and $ f , g \in \C $. This will also show that $ g ( b - a + 1 ) = f ( 1 ) = 2 = g ( 1 ) $, which by the fact that $ g $ is strictly increasing, gives $ a = b $.
2. Since $ h ( y ) < y $ for any $ y \in \Zs $ with $ y \ne 2 $, there is some smallest $ a \in \Z $ such that $ h ^ { a - 1 } ( n ) = 2 $, where $ h ^ m $ denotes $ m $-th iteration of $ h $. Let $ f ( x ) = h ^ { a - x } ( n ) $ for $ 1 \le x \le a $, and continue assigning values of $ f ( x ) $ for $ x > a $ by using the fact that $ h $ is surjective. The fact that constructed this way, $ f $ will become strictly increasing, again comes from $ h ( y ) < y $ for $ 2 \ne y \in \Zs $.
3. By part 1, $ B _ n $ has at most one element, and by part 2, it has at least one element, and hence it is a singleton. The fact that $ a ( n ) $ is its only element comes from the construction in the previous part.

---

Now that we have all these, we can see that the function $ a $ defined above can be considered as some sort of "inverse" to any $ f \in \C $, which helps with making sense of what you've asked. So, we're finally ready to reformulate the question in a precise manner, and start solving the main problem.

Define $ a : \Zs \to \Z $ recursively with $ a ( 2 ) = 1 $ and $ a ( n ) = a \big( h ( n ) \big) + 1 $ for $ n > 2 $. Find asymptotic bounds for $ a $ in terms of elementary functions.

You can check that $ a ( n ) \in \Theta \left( \frac { \log _ 2 n } { \log _ 2 \log _ 2 n } \right) $. In fact, the explicit bounds $$ 1 + \left\lceil \frac { \log _ 2 n - 1 } { \log _ 2 \left\lceil \log _ 2 n \right\rceil } \right\rceil \le a ( n ) \le 2 + \left\lfloor \frac { \log _ 2 n - 1 } { \log _ 2 \log _ 2 n - 1 } \right\rfloor $$ can be given for $ n \ge 5 $. To see that how one can get these bounds, let's take a look at the sequence $$ n \t h ( n ) \t h \big( h ( n ) \big) \t h \Big( h \big( h ( n ) \big) \Big) \t \dots $$ starting from $ n $ and ending in $ 2 $. Remember that $ a ( n ) $ is equal to the length of the above sequence (i.e. the number of steps needed for reaching $ 2 $) plus one. Instead of the actual sequence $$ n \t \left\lceil \frac n { \left\lceil \log _ 2 n \right\rceil } \right\rceil \t \left\lceil \frac { \left\lceil \frac n { \left\lceil \log _ 2 n \right\rceil } \right\rceil } { \left\lceil \log _ 2 \left\lceil \frac n { \left\lceil \log _ 2 n \right\rceil } \right\rceil \right\rceil } \right\rceil \t \left\lceil \frac { \left\lceil \frac { \left\lceil \frac n { \left\lceil \log _ 2 n \right\rceil } \right\rceil } { \left\lceil \log _ 2 \left\lceil \frac n { \left\lceil \log _ 2 n \right\rceil } \right\rceil \right\rceil } \right\rceil } { \left\lceil \log _ 2 \left\lceil \frac { \left\lceil \frac n { \left\lceil \log _ 2 n \right\rceil } \right\rceil } { \left\lceil \log _ 2 \left\lceil \frac n { \left\lceil \log _ 2 n \right\rceil } \right\rceil \right\rceil } \right\rceil \right\rceil } \right\rceil \t \dots $$ let's take a look at another one which has a simpler look. Since $ h ( y ) \ge \frac y { \left\lceil \log _ 2 y \right\rceil } $ and $ h ( y ) \le y $ for $ y > 2 $, we can see that the sequence $$ n \t \frac n { \left\lceil \log _ 2 n \right\rceil } \t \frac n { \left\lceil \log _ 2 n \right\rceil ^ 2 } \t \frac n { \left\lceil \log _ 2 n \right\rceil ^ 3 } \t \dots $$ consists of terms no greater than their corresponding terms in the original sequence. This means that this sequence may reach a value less than or equal to $ 2 $ in fewer steps. If $ b $ is the mentioned number of steps, it means that we have $ \frac n { \left\lceil \log _ 2 n \right\rceil ^ b } \le 2 $. By taking logarithms and rearranging, we get $ b \ge \frac { \log _ 2 n - 1 } { \log _ 2 \left\lceil \log _ 2 n \right\rceil } $, and since $ a ( n ) \ge b + 1 $, we get the desired lower bound for $ a ( n ) $. Similarly, and this time using $ h ( y ) \le \left\lceil \frac y { \log _ 2 y } \right\rceil $ and $ h ( y ) \le \frac y 2 $ for $ y > 3 $, we can see that the sequence $$ n \t \left\lceil \frac n { \log _ 2 n } \right\rceil \t \left\lceil \frac { 2 n } { ( \log _ 2 n ) ^ 2 } \right\rceil \t \left\lceil \frac { 2 ^ 2 n } { ( \log _ 2 n ) ^ 3 } \right\rceil \t \dots $$ consists of terms which are no less than corresponding terms in the original sequence. Thus $ b $, the number of steps needed for reaching a value less than or equal to $ 2 $ is more than that of the original sequence. In case that $ b \ge 1 $ (i.e. at least one step is needed, which happens for $ n \ge 5 $) $ b - 1 $ steps are not enough, which gives $ \frac { 2 ^ { b - 2 } n } { ( \log _ 2 n ) ^ { b - 1 } } + 1 \ge \left\lceil \frac { 2 ^ { b - 2 } n } { ( \log _ 2 n ) ^ { b - 1 } } \right\rceil \ge 3 $. Taking logarithms and rearranging, we get $ b \le 1 + \frac { \log _ 2 n - 1 } { \log _ 2 \log _ 2 n - 1 } $, which by $ a ( n ) \le b + 1 $, gives the desired upper bound for $ a ( n ) $.

Finally, note that using the bounds, by squeezing we have $$ \lim _ { n \to \infty } \frac { a ( n ) \log _ 2 \log _ 2 n } { \log _ 2 n } = 1 $$ or in other terms $$ a ( n ) \sim \frac { \log _ 2 n } { \log _ 2 \log _ 2 n } $$ which is even better than mere $ a ( n ) \in \Theta \left( \frac { \log _ 2 n } { \log _ 2 \log _ 2 n } \right) $. $ \endgroup $