Show $\sum^M_{i=1}a_i/\sqrt{a'_{i-1}}\leq(\sqrt2+1)\sqrt{a'_M}$ for non-negative integers $a_i$ with $a_n\leq a'_{n-1}=\max\{1,\sum^{n-1}_{k=0}a_k\}$

Question

Let $\{ a_0, a_1, \dots\}$ be a sequence of non-negative integers such that for every $n\geq 1$ the sequence satisfies $a_n \leq a'_{n-1} = \max\{ 1, \sum^{n-1}_{k=0}a_k\}$. Show that $$ \sum^{M}_{i=1}\frac{a_i}{\sqrt{a'_{i-1}}} \leq (\sqrt 2 + 1) \sqrt{a'_M}$$

This is my attempt. Let $p$ be first integer for which $a'_p = a_1 + a_2 + \dots + a_{p}$. Thus, each of the first $p$ elements of the sum are bounded by $1$. For $i \geq p$ we can find that $a'_{i+1} - a'_{i} = a_{i+1} \leq a'_{i}$, and thus $\frac{a'_{i+1}}{a'_{i}}\leq 2$. What else could I do?

Answer 1

Induction works.

First note that if $\ a_i=0\ $ for all $\ i\ $, then $\ a_i'=1\ $ for all $\ i\ $, and the inequality holds.

Otherwise, let $\ m=\min\{i\,|\,a_i\ne0\}\ $. Then $\ a_i'=\max\left\{1,\sum_\limits{k=0}^ia_k=0\right\}=$$\ \max\{1,0\}=1\ $ for $\ i<m\ $. Also, if $\ m\ge1\ $, then since $\ a_m\le a_{m-1}'=1\ $ and $\ a_m\ne0\ $, it follows that $\ a_m=1\ $ and $\ a_m'=\max\left\{1,\sum_\limits{k=0}^ma_k\right\}=1\ $. For $\ i\ge m\ $ we have $\ a_i'=\sum_\limits{k=0}^ia_k=\sum_\limits{k=m}^ia_k\ $. Thus, whatever the value of $\ m\ $, we have $\ a_{i+1}'= a_i'+a_{i+1}\le2a_i'\ $ for $\ i\ge0\ $.

If $\ m\ge2 $ then $$\sum_{i=1}^1\frac{a_i}{\sqrt{a_{i-1}'}}=0\ ,$$ so the inequality certainly holds for $\ M=1\ $ in that case.

If $\ m=1\ $ then $$\sum_{i=1}^1\frac{a_i}{\sqrt{a_{i-1}'}}=a_1=1\ ,$$ while $$\big(1+\sqrt{2}\big)\sqrt{a_1'}=1+\sqrt{2}\ , $$ and the inequality holds for $\ M=1\ $ in this case as well.

Finally, if $\ m=0\ $, then $$\sum_{i=1}^1\frac{a_i}{\sqrt{a_{i-1}'}}=\frac{a_1}{\sqrt{a_0'}}\le\sqrt{a_0'}=\sqrt{a_0}\ ,$$ while $$\big(1+\sqrt{2}\big)\sqrt{a_M'}=\big(1+\sqrt{2}\big)\sqrt{a_0+a_1}\ ,$$ so again the inequality holds for $\ M=1\ $. Thus, whatever the value of $\ m\ $, the inequality holds for $\ M=1\ $.

Now let $\ N\ $ be any value of $\ M\ $ for which the inequality holds: $$\sum_{i=1}^N\frac{a_i}{\sqrt{a_{i-1}'}}\le\big(1+\sqrt{2}\big)\sqrt{a_N'}\ .$$ Then \begin{align}\sum_{i=1}^{N+1}\frac{a_i}{\sqrt{a_{i-1}'}}&=\sum_{i=1}^N\frac{a_i}{\sqrt{a_{i-1}'}}+\frac{a_{N+1}}{\sqrt{a_N'}}\\&\le\big(1+\sqrt{2}\big)\sqrt{a_N'}+\frac{a_{N+1}}{\sqrt{a_N'}}\\&=\frac{\big(1+\sqrt{2}\big)a_N'+a_{N+1}}{\sqrt{a_N'}}\\&=\frac{a_{N+1}'+a_N'\sqrt{2}}{\sqrt{a_N'}}\\&=\frac{\big(1+\sqrt{2}\big)\sqrt{a_{N+1}'a_N'}}{\sqrt{a_N'}}\\&\hspace{1em}-\frac{\left(\sqrt{2a_N'}-\sqrt{a_{N+1}'}\right)\left(\sqrt{a_{N+1}'}-\sqrt{a_N'}\right)}{\sqrt{a_N'}}\\&\le\big(1+\sqrt{2}\big)\sqrt{a_{N+1}}\ .\end{align} Thus, the inequality holds for $\ M=N+1\ $ if it holds for $\ M=N\ $, and since it holds for $\ M=1\ $, then it holds for all positive integers $\ M\ $ by induction.