4 Bulgarian National Olympiad - Regional Round

Applying AM-GM inequality to each term of the right-hand side, we get, $$x_n^2\le \sum _{i=1}^{n-1}{x}_i,n>N.$$ Let us set $x_n=a\cdot n+\Delta (n)$, where $a$ is a constant that will be determined later. Vaguely speaking, we want to pick a value for $a$ such that $\Delta (n)$ has a smaller growth rate than $n$. For $n>N$ we obtain, $$a^2{n}^2+2an\Delta (n)+\Delta (n{)}^2\le \frac{a(n-1)n}{2}+\sum _{i=1}^{n-1}\Delta (i)$$ $$2an\Delta (n)\le \left(\frac{a(n-1)n}{2}-a^2{n}^2\right)-\Delta (n{)}^2+\sum _{i=1}^{n-1}\Delta (i)(1).$$ The plan is to divide both sides by $n$ so let's determine $a$ such that the term in the brackets of the right side of (1) be of degree $n$ (not $n^2$ as it is now). It can be easily calculated that $a=1/2$. Putting it in (1), we get $$\Delta (n)\le -\frac{1}{4}-\frac{\Delta (n{)}^2}{n}+\frac{1}{n}\sum _{i=1}^{n-1}\Delta (i).$$ Now, write $$\Delta (n)\le \frac{1}{n}\sum _{i=1}^{n-1}\Delta (i),\forall n>N$$ which yields $$\Delta (n)\le \max \{\Delta (i):i<n\},$$ hence $\Delta (n)\le \max \{\Delta (i):i\le N\}$ for any $n>N$. This yields $x_n\le n/2+c,\forall n\in \mathbb{N}$ for some constant $c$.

Sharper estimate. We want to go a bit further, so let's write $$\Delta (n)\le -\frac{1}{4}+\frac{1}{n}\sum _{i=1}^{n-1}\Delta (i),n>N$$ Define the sequence ${\Delta }^{\prime }(n)$ as follows: $${\Delta }^{\prime }(n)=-\frac{1}{4}+\frac{1}{n}\sum _{i=1}^{n-1}{\Delta }^{\prime }(i),\text{ for }n>N(2),$$ and ${\Delta }^{\prime }(n)={\Delta }^{\prime }(n)$, for $n\le N$. Clearly $\Delta (n)\le {\Delta }^{\prime }(n),\forall n\in \mathbb{N}$. We have $${\Delta }^{\prime }(n+1)=-\frac{1}{4}+\frac{1}{n+1}\left(\sum _{i=1}^{n-1}\Delta (i)+-\frac{1}{4}+\frac{1}{n}\sum _{i=1}^{n-1}\Delta (i)\right),n>N(3).$$ Subtracting (2) from (3) yields $${\Delta }^{\prime }(n+1)-{\Delta }^{\prime }(n)=\frac{-1}{4(n+1)},\forall n>N.$$ Summing up the above inequality gives $${\Delta }^{\prime }(n)={\Delta }^{\prime }(N+1)-\frac{1}{4}\sum _{k=N+2}^n\frac{1}{k},n\ge N+2.$$ Therefore, using a well known property of harmonic series, $${\Delta }^{\prime }(n)\le -\frac{\ln n}{4}+c$$ where $c$ is a constant. Finally, we get $$x_n\le \frac{n}{2}-\frac{\ln n}{4}+c,n\in \mathbb{N},$$