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

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$$

• Why do you think the limit is $\pi$? I have done some very limited (and possibly incorrect) calculations and it seems that the quotient is close to $\pi$ when $n=200$ but then gets further away up to $n=1000$. Have you done some more extensive calculations? Aug 1, 2022 at 0:02
• @David I get that $f(10^6)\approx \frac{10^{12}}{3.1415865\ldots}$, so $f(n)$ seems pretty close to $n^2/\pi$ for large $n$. Aug 1, 2022 at 0:16
• How did the proof that $\frac{8}{3},4$ are upper/lower bounds respectively go? What were the estimates and results used along the way? Aug 3, 2022 at 8:37
• @SarveshRavichandranIyer I used the fact that we have $n_{n-j} \leq n_{n-j-1} + (j-1)$ and thus $f(n) \leq n_{n/2} + \sum_{k=0}^{n/2-2} k$ now using the fact that $n_{n/2} = n/2(n/2+1)$ we get that $f(n) \leq 3n^2/8 + O(n)$. For the other bound clearly $n/2(n/2+1) \leq f(n)$
– 3m0o
Aug 3, 2022 at 11:07
• @Jean-ArmandMoroni Yes! And $f(9)=30$, $f(10)=34$. The general formula for $n \geq 2$ is given by $f(n) = \left \lceil \frac{2}{1} \left \lceil \frac{3}{2} \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$.
– 3m0o
Aug 3, 2022 at 11:29

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.)

• Nice ideas! I didn't understand, however, how do we know, that $\frac1n a_{n - 1} ≈ \frac1n a{\left(1 - \frac1n\right)}$ ? If we think of $a_k$ as Euler method approximation, then $a'$ is unbounded on $[0, 1)$, so approximation error $|a_{n-1} - a(1 - \frac1n)|$ is maybe unbounded. How do we know, that $\lim_{n \to \infty} \frac1n (a_{n-1} - a(1 - \frac1n)) = 0$ then? Aug 4, 2022 at 3:56
• @D.Dmitriy Looking more closely, I noticed it’s actually an implicit midpoint method approximation. And we’re only interested in the interval $[0, 1 - \frac1n]$, so I think we can get a good enough error bound. There are still some details to be checked though. Aug 4, 2022 at 6:44

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)$$