# Series of terms following polynomial recurrence relation

Hello!

I'm stuck trying to prove a statement that seems very reasonable based on computer experiments. For an integer $N$ and any $\epsilon \in (0,1)$, I define a sequence $u_0 = N$ and for all $k\geq 1$: $$u_k = u_{k-1} - \frac{\epsilon^2}{2N}u_{k-1}(u_{k-1}-1) + \frac{\epsilon^3}{6N^2} u_{k-1} (u_{k-1}-1) (u_{k-1}-2)$$ The claim is that $$\sum_{k\geq 0} (u_k - 1) \leq C N \log N$$ for some $0 < C < \infty$ independent of $N$. I don't need $C$ to be explicit, just independent of $N$.

By defining the function $g$ such that $u_k = g(u_{k-1})$, and looking at $g$, I can say that $g$ is increasing, concave, $\lambda$-contracting with $\lambda \leq 1 - \epsilon^2/N = \sup_{u\in[1,N]} \vert g'(u)\vert = \vert g'(1)\vert$, which is not good enough when I compute the sum; I get a bound in $N^2$ instead of the desired $N \log N$.

I've tried looking at $u_{k+1}/u_k$, $u_{k+1} - u_k$, tried to bound $g$ in various ways but couldn't conclude... any help would be hugely appreciated!

• If it helps, I now have that $$\sum_{k=0}^\tau (u_k-1) \leq C N \log N$$ where $\tau = \inf\{k: u_k \leq 2\}$. This can be proven by looking at the number of iterations $k$ required to go from any $M$ to $\alpha M$ for any $\alpha \in (0,1)$, that is, $k$ such that $u_{n} = M$ implies $u_{n+k} \leq \alpha M$. So I now want to prove the same claim as in my original question, but starting from $u_0 = 2$. Don't know if it's much easier since the problem is mostly "near $1$". – Pierrot Jun 19 '13 at 11:54
• Note that if $u_0\in(1,2)$, then $1<u_k<2$ for all $k$ (induction) and $u_k-1\le (1-\frac{\varepsilon^2}{2N})(u_{k-1}-1)$. To sum a geometric progression shouldn't be a big headache. – fedja Jun 19 '13 at 16:38
• Aaaah of course! If doing this reasoning from $u_0 = N$ it yields a bound in $N^2$ but from $u_0 = 2$ it yields a bound in $N$, indeed! Thanks fedja, that was a big help. I'll write the full answer for the record. – Pierrot Jun 20 '13 at 0:42

Here is the full answer in case you are interested. Let $N\in \mathbb{N}$ and $\epsilon \in (0,1)$, and define $(u_k)_{k\geq 0}$ by $u_0 = N$ and $$u_k = g_{N,\epsilon}(u_{k-1}) = u_{k-1} - \frac{\epsilon^2}{2N}u_{k-1}(u_{k-1}-1) + \frac{\epsilon^3}{6N^2} u_{k-1} (u_{k-1}-1) (u_{k-1}-2).$$
Note first that $g_{N,\epsilon}$ is contracting and is such that $g_{N,\epsilon}(1) = 1$, so that $u_k$ goes to $1$ using Banach fixed-point theorem. The contraction coefficient of $g_{N,\epsilon}$ can be bounded by \begin{align*} \sup_{x} \lvert g_{N,\epsilon}'(x) \rvert &\leq g_{N,\epsilon}'(1) = 1 - \frac{\epsilon^2}{2N} < 1, \end{align*} however this contraction coefficient depends on $N$ and a direct use of it yields a bound on $\sum_{k\geq 0} (u_k - 1)$ that is not in $N \log N$.
Note also that even though $u_k$ goes to $1$, we can focus on the partial sum $\sum_{k=0}^{\sigma_2}(u_k-1)$ where $\sigma_2 = \inf\{k : u_k \leq 2\}$, because $\sum_{k=\sigma_2}^\infty (u_k - 1)$ is essentially bounded by $N$. Indeed note that for $u_k\leq 2$ we have $$\frac{\epsilon^3}{6N^2} u_{k-1} (u_{k-1}-1) (u_{k-1}-2)\leq 0$$ so that \begin{align*} u_k - 1 &\leq u_{k-1} - 1 - \frac{\epsilon^2}{2N}u_{k-1}(u_{k-1}-1)\\ & \leq (u_{k-1} - 1 )(1 - \frac{\epsilon^2}{2N}) \mbox{ since }u_{k-1}\geq 1 \end{align*} Hence we have \begin{align*} \sum_{k\geq \sigma_2} (u_k-1) &\leq 2 \frac{1}{1 - (1 - \frac{\epsilon^2}{2N})} = \frac{4N}{\epsilon^2} \end{align*} Therefore we can focus on bounding $\sum_{k=0}^{\sigma_2}(u_k - 1)$ by $N\log N$. Let us split this sum into partial sums, where the first partial sum is over indices $k$ such that $N/2 \leq u_k \leq N$, the second is over indices $k$ such that $N/4 \leq u_k \leq N/2$, etc. More formally, we introduce $(k_j)_{j = 0}^J$ such that $k_0 = 0$, $k_1 = \inf\{k: u_k \leq N/2\}$, ..., $k_j = \inf\{k: u_k \leq N/2^j\}$, up to $k_J = \inf\{k: u_k \leq N/2^J\}$ where $J$ is such that $N/2^J \leq 2$, or equivalently \begin{align*} &\log N - J \log 2 \leq \log 2 \\ \Leftrightarrow &\log N / \log 2 - 1 \leq J. \end{align*} For instance we take $J = \lceil \log N / \log 2\rceil$. Thus we have split $\sum_{k=0}^{\sigma_2}(u_k - 1)$ into $J$ partial sums of the form $$\sum_{k=k_j}^{k_{j+1}} (u_k - 1)$$ and we are now going to bound each of these partial sum by the same quantity $C(\epsilon) N$ for some $C(\epsilon)$ that depends only on $\epsilon$.
To do so, we consider the time needed by $(u_k)_{k\geq 0}$ to from a value $N/m_j$ to a value $N/m_{j+1}$, with $m_{j+1} > m_j$; we will later take $m_j = 2^j$ and $m_{j+1} = 2^{j+1}$. Note that for any $m$ we have \begin{align*} g_{N, \epsilon}\left(\frac{N}{m}\right) &= \frac{N}{m}\left(1 - \frac{\epsilon^2}{2N}(\frac{N}{m}-1) + \frac{\epsilon^3}{6N^2} (\frac{N}{m}-1) (\frac{N}{m}-2)\right)\\ &= \frac{N}{m}\left(1 - \frac{1}{m}\left[\frac{\epsilon^2}{2} - \frac{m \epsilon^2}{2N} - \frac{\epsilon^3}{6m} + \frac{\epsilon^3}{2N} - \frac{m\epsilon^3}{3N^2}\right]\right). \end{align*} Define $$\beta(N,m,\epsilon) = \frac{\epsilon^2}{2} - \frac{m \epsilon^2}{2N} - \frac{\epsilon^3}{6m} + \frac{\epsilon^3}{2N} - \frac{m\epsilon^3}{3N^2}$$ and note that for any $N$ and $m\leq N/2$ we have $$\underline{\beta}(\epsilon) := \frac{\epsilon^2}{4} \leq \beta(N,m,\epsilon),$$ which is clear upon noticing that $\beta(N,m,\epsilon)\geq \beta(N,N/2,\epsilon) = \epsilon^2/4$. For any $x > N/m_{j+1}$ we can check that $$g_{N,\epsilon}(x) \leq \frac{g_{N,\epsilon}(N/m_{j+1})}{N/m_{j+1}} \times x$$ by noticing that $x\mapsto g_{N,\epsilon}(x)/x$ is decreasing. Hence for $k\geq 0$ such that $u_{k-1}\geq N/m_{j+1}$, we have $$u_{k} \leq \left(1 - \frac{1}{m_{j+1}} \underline{\beta}(\epsilon)\right) u_{k-1}.$$ Now suppose that for some $k_j\geq 0$ we have $u_{k_j}\leq N/m_j$. Then let us find $K$ such that $u_{k_j+K} \leq N/m_{j+1}$. It is sufficient to find $K$ such that \begin{align*} &\left(1 - \frac{1}{m_{j+1}} \underline{\beta}(\epsilon)\right)^{K} \frac{N}{m_j} \leq \frac{N}{m_{j+1}}\\ &\Leftrightarrow K\log \left(1 - \frac{1}{m_{j+1}} \underline{\beta}(\epsilon)\right) \leq \log \frac{m_j}{m_{j+1}}\\ &\Leftrightarrow K \geq \log \frac{m_{j+1}}{m_j} \left(-\log\left(1 - \frac{1}{m_{j+1}} \underline{\beta}(\epsilon)\right)\right)^{-1} \end{align*} Finally we conclude that $K$ defined as follows $$K= \left\lceil \left(\log \frac{m_{j+1}}{m_j}\right) \frac{m_{j+1}}{\underline\beta(\epsilon)}\right\rceil$$ guarantees the inequality $u_{k_j+K} \leq N/m_{j+1}$. In other words $(u_k)_{k\geq 0}$ needs less than $K$ steps to decrease from $N/m_j$ to $N/m_{j+1}$. Summing the terms between $k_j$ and $k_j + K$, we obtain \begin{align*} \sum_{k = k_j}^{k_j+K} u_k &\leq K \frac{N}{m_j}\leq \left\lceil \left(\log \frac{m_{j+1}}{m_j}\right) \frac{m_{j+1}}{\underline\beta(\epsilon)}\right\rceil \frac{N}{m_j}\\ &\leq \left[\left(\log \frac{m_{j+1}}{m_j}\right) \frac{m_{j+1}}{\underline\beta(\epsilon)} + 1\right]\frac{N}{m_j}. \end{align*} Taking $m_j = 2^j$ and $m_{j+1} = 2^{j+1}$, we have $k_{j+1}\leq k_j + K$ and thus obtain \begin{align*} \sum_{k = k_j}^{k_{j+1}} u_k \leq \sum_{k = k_j}^{k_j+K} u_k &\leq \left[\left(\log 2\right) \frac{2^{j+1}}{\underline\beta(\epsilon)} + 1\right]\frac{N}{2^j}\\ &\leq \left[\left(\log 2\right) \frac{2}{\underline\beta(\epsilon)} + \frac{1}{2^j}\right]N\\ &\leq C(\epsilon) N \end{align*} with $C(\epsilon) = \left(\log 2\right) \frac{2}{\underline\beta(\epsilon)} + \frac{1}{2}$. To summarize the full sum can be bounded as follows \begin{align*} \sum_{k\geq 0} (u_k - 1) &\leq \sum_{k=0}^{\sigma_2} (u_k - 1) + \sum_{k\geq \sigma_2} (u_k - 1)\\ &\leq \sum_{j=1}^J \sum_{k=k_{j-1}}^{k_j} u_k + \frac{4N}{\epsilon^2} \\ &\leq \left\lceil \frac{\log N}{\log 2} \right\rceil C(\epsilon)N + \frac{4N}{\epsilon^2} \\ &\leq D(\epsilon) N \log N \end{align*} for some $D(\epsilon)$ that depends only on $\epsilon$.