1

Given $\Delta_1=1$, consider the following recursive form $$\Delta_{t+1} = \left(1-\frac{1}{t+1}\right)\Delta_t + \left(\frac{1}{t+1}\right)^2 D_t, \quad t=1,2,\dots$$ where $$D_t = \left(2-\frac{1}{t+1}\right) \sum_{i=1}^t \left( \frac{t+1}{i+1} \right)^2 0.5^{t-i+1}, \quad t=1,2,\dots$$

I want to know the relations of $\Delta_t$ and $D_t$. From numerical experiments, I find that $\frac{(t+1)\Delta_t}{D_t}$ grows sublinearly, i.e., $$\frac{\Delta_t}{D_t} \leq O\left(\frac{\log t}{t}\right)$$

enter image description here

I do not know how to show it. Any help is appreciated.

antonio
  • 61
  • This is a inhomogeneous first-order linear recurrence relation, it is possible to solve it exactly; to do so, you can follow this answer of mine : https://math.stackexchange.com/questions/4604906/how-to-derive-the-general-term-formula-for-this-sequence/4605086#4605086 – Abezhiko May 21 '23 at 07:33
  • @Abeziko Thank you for the suggestion. I may not want to solve the exact rate, I only need an upper bound. – antonio May 21 '23 at 07:50

1 Answers1

1

This is a very rough engineering approach to the problem. Your relations may be written as

$$\dfrac{\Delta_{t+1}-\Delta_{t}}{(t+1)-(t)} = -\left(\frac{1}{t+1}\right)\Delta_t + \left(\frac{1}{t+1}\right)^2 D_t, \quad t=1,2,\dots$$ where $$D_t = \left(2-\frac{1}{t+1}\right) \sum_{n=1}^t \left( \frac{t+1}{n+1} \right)^2 0.5^{t-n+1}, \quad t=1,2,\dots$$

For large values of $t\gg 1$, we can write $t+1\approx t,$ and on dropping the suffixes on $\Delta $ and $D$, the equations can be written as $$\dfrac{\rm d \Delta}{dt} = -\dfrac{\Delta}{t} + \dfrac{D}{t^2}, $$ and $$ D = 2t^2 \sum_{n=1}^t \left( \dfrac{1}{n+1}\right)^2 \left(\dfrac{1}{2}\right)^{t-n+1}. $$ The last term in $D$ is approximately $ 2t^2 /2t^2 \sim\mathcal {O}(1)$, and assuming that $D\sim\mathcal {O}(1),$ the differential equation for $\Delta$ becomes $$\dfrac{\rm d \Delta}{dt} = -\dfrac{\Delta}{t} + \dfrac{D}{t^2},\quad \text{or} \quad\dfrac{\rm d \Delta}{\Delta} = -\dfrac{{\rm d} t}{t} + \dfrac{D\,{\rm d}t}{t^2\Delta }.$$ If we now make use of your hunch, namely that $\dfrac{t\Delta}{D}\sim \log(t)$, then the integration yields $$\log(\Delta)\sim-\log(t)+\int \dfrac{{\rm d}t}{t\log(t)}, $$ or $$\log(t\Delta)\sim \log(\log(t))\quad\text{or}\quad t\Delta\sim \log(t).$$ Since $D \sim\mathcal {O}(1), $ we finally arrive at $$ \dfrac{t\Delta}{D}\sim \log(t). $$

So your hunch yields a result, which in itself, is self-consistent with the approximate differential equations for $t\gg 1.$

The approximation that $D \sim\mathcal {O}(1)$ might need a closer inspection, since I only looked at the last term.