Limit of $n^2$ and a recurrence relation with ceiling function

Question

For all positive integer $n$ we define a finite sequence in the following way: $n_0 = n$, then $n_1\geq n_0$ and has the property that $n_1$ is a multiple of $n_0-1$ such that the difference $n_1 - n_0$ is minimal among all multiple of $n_0 -1 $ that are bigger than $n_0$. More generally $n_k \geq n_{k-1}$ and has the property that is a multiple of $n_0-k$ such that the difference $n_k - n_{k-1}$ is minimal among all multiple of $n_0 -k $ that are bigger than $n_{k-1}$. We stop the procedure when $k=n-1$ so that we define $f$ to be $f(n_0) = n_{n-1} $.

Question: What is the value of $\lim_{n \to \infty} \frac{n^2}{f(n)} $ ?

I'm able to prove that $$ \frac{8}{3} \leq \lim_{n \to \infty} \frac{n^2}{f(n)} \leq 4 $$ but I can't do better. Someone has an idea? I think that the limit is $ \pi $ but don't know how to prove that.

My idea is to prove that $$ f(n) = \frac{n^2}{\pi} + O(n) $$ the general term for $n_k$ is given by $$ n_k = (n-k) \left \lceil \frac{n_{k-1}}{n-k} \right \rceil $$ So that $$ n_k = (n-k) \left \lceil \frac{n-(k-1)}{n-k} \left \lceil \frac{n-(k-2)}{n-(k-1)} \left \lceil \ldots \left \lceil \frac{n-1}{n-2} \left \lceil \frac{n}{n-1} \right \rceil \right \rceil \right \rceil \right \rceil \right \rceil $$

Answer 1

Under the substitution

$$t_k = \frac kn, \quad a_k = \frac{n_k}{n(n - k)}, \quad Δt = \frac1n,$$

we have

$$t_0 = 0, \quad a_0 = Δt, \quad t_k = t_{k - 1} + Δt, \quad a_k = a_{k - 1} + \left\lceil\frac{a_{k - 1}}{1 - t_k}\right\rceil Δt,$$

which approximates* the differential equation

$$a(0) = 0, \quad a'(t) = \left\lfloor\frac{a(t)}{1 - t} + 1\right\rfloor.$$

The solution to this differential equation is piecewise linear; the piece with slope $i$ goes from $a(1 - b_{i - 1}) = (i - 1)b_{i - 1}$ to $a(1 - b_i) = ib_i$ where

$$b_0 = 1, \quad b_i = \frac{2i - 1}{2i}b_{i - 1}.$$

Observe that $\frac{1}{b_ia(1 - b_i)}$ is exactly the Wallis product that tends to $π$.

\begin{align*} \frac{1}{b_ia(1 - b_i)} = \frac1{ib_i^2} &= \frac 21 ⋅ \frac21 ⋅ \frac43 ⋅ \frac43 ⋅ \frac65 ⋅ \frac65 ⋯ \frac{2i}{2i - 1} ⋅ \frac{2i}{2i - 1} ⋅ \frac1i \\ &= \frac21 ⋅ \frac23 ⋅ \frac43 ⋅ \frac45 ⋅ \frac65 ⋅ \frac57 ⋯ \frac{2i}{2i - 1} \cdot 2 → π. \end{align*}

Therefore, at $b_i ≈ \frac1n$, we have

$$\frac{n^2}{n_{n - 1}} = \frac1{\frac1n a_{n - 1}} ≈ \frac{1}{\frac1n a{\left(1 - \frac1n\right)}} → π.$$

---

(* The approximation differs slightly from the forward Euler method in that the $1 - t_{k - 1}$ in the denominator is replaced by $1 - t_k$. With some rearrangement, in fact, we see that it’s extremely close to the implicit midpoint method:

\begin{align*} a_k &= a_{k - 1} + \left\lceil\frac{a_{k - 1}}{1 - t_k}\right\rceil Δt = a_{k - 1} + \left\lceil\frac{a_{k - 1} + \frac{a_{k - 1}}{1 - t_k} ⋅ \frac{Δt}{2}}{1 - \frac{t_{k - 1} + t_k}{2}}\right\rceil Δt \\ &≈ a_{k - 1} + \left\lceil\frac{a_{k - 1} + \left\lceil\frac{a_{k - 1}}{1 - t_k}\right\rceil ⋅ \frac{Δt}{2}}{1 - \frac{t_{k - 1} + t_k}{2}}\right\rceil Δt = a_{k - 1} + \left\lceil\frac{\frac{a_{k - 1} + a_k}{2}}{1 - \frac{t_{k - 1} + t_k}{2}}\right\rceil Δt. \end{align*}

The implicit midpoint method solves the related differential equation $a'(t) = \frac{a(t)}{1 - t} + c$ exactly(!), so we can expect some kind of $O(Δt^2)$ bound on the error, but there are some details to be checked here if we want it to be rigorous.)

Answer 2

Not sure but I think I did one direction in another way: Claim: For $ n/2 < k < n$ and $n$ big enough we have that $$ \left \lceil \frac{n_{k-1}}{n-k} \right \rceil \leq \frac{(k+1)^2}{\pi} \frac{ \Gamma(k+1/2)\Gamma(k+3/2)}{\Gamma(k+1)^2} $$ hence $$ n_k = (n-k) \left \lceil \frac{n_{k-1}}{n-k} \right \rceil \leq (n-k)\frac{(k+1)^2}{\pi} \frac{ \Gamma(k+1/2)\Gamma(k+3/2)}{\Gamma(k+1)^2} $$ thus when $k=n-1$ we have $$ f(n) \leq \frac{n^2}{\pi} \frac{ \Gamma(n+1/2)\Gamma(n-1/2)}{\Gamma(n)^2} = \frac{n^2}{\pi} + O(n) $$

Proof of the claim: We have that the claim holds for $k=n/2+1$ in fact for $n > 6$ we have that $ n_{n/2+1} = (n/2-1) (n/2+3)$. Hence $ \left \lceil \frac{n_{n/2}}{n/2-1} \right \rceil = (n/2+3)$ Then suppose that the claim holds for $ n/2 < k < n$, now we have that $ \left \lceil x \right \rceil \leq x +1 $, then $$ \frac{(k+1)^2}{\pi} \frac{ \Gamma(k+1/2)\Gamma(k+3/2)}{(n-k)\Gamma(k+1)^2} + 1 \leq \frac{(k+1)^2}{\pi} \frac{ \Gamma(k+1/2)\Gamma(k+3/2)}{\Gamma(k+1)^2} + 1 \leq \frac{(k+2)^2}{\pi} \frac{ \Gamma(k+1+1/2)\Gamma(k+1+3/2)}{\Gamma(k+2)^2} $$ where the last inequality cames from the fact that when $k$ is big enough the Laurent series of $ \frac{ \Gamma(k+1+1/2)\Gamma(k+1+3/2)}{\pi\Gamma(k+2)^2} $ and of $\frac{ \Gamma(k+1/2)\Gamma(k+3/2)}{\pi \Gamma(k+1)^2} $ is equal too $$ \frac{1}{\pi} + O(1/k) $$ and we have that $$ 1 \leq \left( (k+2)^2 - (k+1)^2 \right) \left( \frac{1}{\pi} + O(1/k) \right) $$

hence $$ f(n) \leq \frac{n^2}{\pi} + O(n) $$