Proposed by Soroosh Ebadian from Iran

Dadgarnia wrote: Proposed by Soroosh Ebadian from Iran Great!very interesting

A local refinement solution which shows that the minimum value of the left hand side is reached when the $x_i$'s are of the form $1,1,...,1,ad,ad^2,...,ad^m,2^n,2^n,...,2^n$. Let $$f(a_1,...,a_n)=\sum_{i=1}^n\frac{a_i}{\sqrt{a_1^2+...+a_n^2}}$$Claim. If $a_i>a_{i+1}$, then $$f(a_1,...,a_{i-1},a_{i+1},a_i,...,a_n)>f(a_1,...,a_{i-1},a_i,a_{i+1},...,a_n)$$In other words, swapping $a_{i}$ and $a_{i+1}$ will increase the value of $f$. \Proof Let $m=a_1^2+...+a_{i-1}^2$, it suffice to show \begin{align*}\frac{a_{i+1}}{\sqrt{m+a_{i+1}^2}}+\frac{a_i}{\sqrt{m+a_{i+1}^2+a_i^2}}&>\frac{a_i}{\sqrt{m+a_i^2}}+\frac{a_{i+1}}{\sqrt{m+a_{i+1}^2+a_i^2}}\\ \iff a_{i+1}\left(\frac{1}{\sqrt{m+a_{i+1}^2}}-\frac{1}{\sqrt{m+a_i^2+a_{i+1}^2}}\right)&>a_{i}\left(\frac{1}{\sqrt{m+a_{i}^2}}-\frac{1}{\sqrt{m+a_i^2+a_{i+1}^2}}\right)\\ \iff\frac{a_{i+1}a_i^2}{\sqrt{m+a_{i+1}^2}(\sqrt{m+a_{i+1}^2}+\sqrt{m+a_i^2+a_{i+1}^2})}&>\frac{a_{i}a_{i+1}^2}{\sqrt{m+a_i^2}(\sqrt{m+a_i^2}+\sqrt{m+a_i^2+a_{i+1}^2})} \end{align*}which is obviously true. $\blacksquare$ \newline\newline Hence it suffices to consider the case when $1=a_1\leq a_2\leq...\leq a_n=2^k$. \newline\newline Let $a_2=\tan\theta_2$, and $$a_i=\left(\prod_{j=1}^{i-1}\sec\theta_j\right)\cdot \tan\theta_i$$than the condition translates to $$ \begin{cases} \tan\theta_2\geq 1\\ \tan\theta_3\geq \sin\theta_2\\ ...\hspace{200pt}(1)\\ \tan\theta_n\geq \sin\theta_{n-1}\\ \sec\theta_2\sec\theta_3...\sec\theta_{n-1}\tan\theta_n\leq 2^k\hspace{50pt}(2) \end{cases}$$and $$f(a_1,...,a_n)=\sum_{i=1}^n\sin\theta_i\hspace{50pt}(1)$$Claim. If $w<x<y<z$ and $w+z=x+y$ then \begin{enumerate} \item $\sec x\sec y\leq \sec w\sec z$ \item $\sin x+\sin y\geq \sin w+\sin z$ \end{enumerate} \newproof They are simple corollaries of the sum-to-product and product-to-sum identites. $\blacksquare$ \newline\newline Therefore, if $\theta_i>\theta_j$ and we replace $(\theta_i,\theta_j)$ with $(\theta_i-x,\theta_j+x)$, such that $\theta_i-x>\theta_j+x$ and $(1)$ still holds (in other words, we mix $\theta_i,\theta_j$ without violating $(1)$), then $(2)$ still holds, and by $(3)$, the value of $f$ increases. \newline\newline We now mix the variables without violating $(1)$. \newline\newline Firstly, if $\theta_i>\theta_{i+1}$, we can just replace them by $(\frac{\theta_i+\theta_{i+1}}{2},\frac{\theta_i+\theta_{i+1}}{2})$, then it is easy to see that $(1)$ still holds. \newline\newline Hence it suffices to consider the case when $\theta_1\leq \theta_2\leq...\leq \theta_n$. \newline\newline Let $i_1$ be the largest integer such that $\tan\theta_m=\sin\theta_m$ for all $m<i_1$, let $j_1$ be the largest integer such that $\theta_{i_1}=\theta_{i_j}$. Similarly, let $i_2$ be the largest integer such that $\tan{\theta_m}=\sin\theta_m$ for all $m>i_2$, and let $j_2$ be the smallest integers such that $\theta_{j_2}=\theta_{i_2}$. \newline\newline Now for all $\alpha>0$ we define $\beta>0$ such that $$(j_i-i_1+1)\alpha=(i_2-j_2+1)\beta$$and we define an $\alpha$-operation by changing $(\theta_{i_1},...,\theta_{j_1},\theta_{j_2},...,\theta_{i_2})$ to $$(\theta_{i_1}',...,\theta_{j_1}',\theta_{j_2}',...,\theta_{i_2}' )=(\theta_{i_1}-\alpha,...,\theta_{j_1}-\alpha,\theta_{j_2}+\beta,...\theta_{i_2}+\beta)$$By continuity there exists $\epsilon_1,\epsilon_2,\epsilon_3,\epsilon_4$ such that \begin{enumerate} \item After an $\epsilon_1$-operation, $$\tan\theta_{i_1-1}=\sin(\theta_{i_1}')$$\item After an $\epsilon_2$-operation $$\tan\theta_{i_2+1}=\sin(\theta_{i_2}')$$\item After an $\epsilon_3$ operation, $$\theta_{j_1}'=\theta_{j_1+1}$$\item After an $\epsilon_4$-operation $$\theta_{j_2}'=\theta_{j_2-1}$$\end{enumerate} Let $\epsilon=\min\{\epsilon_1,\epsilon_2,\epsilon_3,\epsilon_4\}$, it is easy to see that after an $\epsilon$-operation, $(1)$ is not violated, and that $(2)$ holds while the value of $(3)$ increased, as noted in the previous discussion. \newline\newline Therefore, after finitely many refinements, we achieve the state $$\begin{cases} \tan\theta_2=1\\ ...\\\tan_{\theta_i}=\sin\theta_{i-1}\\\tan\theta_{i+1}>\sin\theta_i\\\theta_{i+1}=...=\theta_j\\\tan\theta_{j+1}>\sin\theta_j\\ \tan\theta_{j+2}=\tan\theta_{j+1} \end{cases}$$In other words, the sequence is of the form $$\underbrace{1,...,1}_{i \text{ times}},a,a\left(\frac{a^2}{i}+1\right)^{\frac{1}{2}},a\left(\frac{a^2}{i}+1\right),...,a\left(\frac{a^2}{i}+1\right)^{\frac{m}{2}},\underbrace{2^k,...,2^k}_{j\text{ times }}$$Now, notice that \begin{align*}\sum_{p=1}^i\frac{a_p}{\sqrt{a_1^2+...+a_p^2}}+\sum_{p=i+m+2}^{i+m+1+j}\frac{a_p}{\sqrt{a_1^2+...+a_p^2}}&<\sum_{p=1}^i\frac{\sqrt{1}}{\sqrt{p}}+\sum_{p=2}^{j+1}\frac{1}{\sqrt{p}}\\&<\int_1^i\frac{1}{\sqrt{x}}dx+\int_2^{j+1}\frac{1}{\sqrt{x}}dx\\&\leq 2\sqrt{i}+2\sqrt{j}-2\\&<\sqrt{8(i+j)}-2 \hspace{30pt}(4) \end{align*}Meanwhile \begin{align*} a\left(\frac{a^2+i}{i}\right)^{\frac{m}{2}}&\leq 2^k\\ \implies \left(\frac{a^2+i}{i}\right)^m&\leq 2^{2k}\\ \implies m&\leq \frac{2k\ln 2}{\ln\left(\frac{a^2+i}{i}\right)} \end{align*}Notice that $$\sum_{p=i+1}^{i+m+1}\frac{a_p}{\sqrt{a_1^2+...+a_p^2}}=\frac{(m+1)a}{\sqrt{a^2+i}}$$Meanwhile by differentiation it is easy to see that, $x-1\leq x\ln x$ for all $x\geq 1$. Therefore, $$2\ln 2\frac{a^2}{i}\leq \frac{a^2+i}{i}\ln\left(\frac{a^2+i}{i}\right)\cdot 2\ln 2$$which implies $$(2\ln 2)km\geq \frac{ma^2}{a^2+i}\cdot \frac{2k\ln 2}{\ln (\frac{a^2+i}{i})}\geq \frac{m^2a^2}{a^2+i}$$Hence $$\frac{ma}{\sqrt{a^2+i}}\leq\sqrt{2\ln 2km} \hspace{30pt}(5)$$Combining all these bounds we have $$\sum_{i=1}^n\frac{a_i}{\sqrt{a_1^2+...+a_i^2}}\leq \sqrt{8(i+j)}+\sqrt{2\ln 2km}\leq \sqrt{16(i+j)+4\ln 2km}\leq 4\sqrt{k(i+j+m+1)}=\sqrt{4kn}$$as desired.

IMO Shortlist 2020 A7 wrote: Let $n$ and $k$ be positive integers. Prove that for $a_1, \dots, a_n \in [1,2^k]$ one has \[ \sum_{i = 1}^n \frac{a_i}{\sqrt{a_1^2 + \dots + a_i^2}} \le 4 \sqrt{kn}. \] We'll proceed by induction on $n$. We'll first deal with the trivial case (base cases) first: indeed, if $n \le 16k$, then \[ \sum_{i = 1}^n \frac{a_i}{\sqrt{a_1^2 + \dots + a_i^2}} \le \sum_{i = 1}^n 1 = n \le 4 \sqrt{kn} \] Claim 01. For any $a_1, a_2, \dots, a_i \in \mathbb{R}$, we have \[ e^{- \sum_i a_i} \ge \prod_i (1 - a_i) \]Proof. First, we will prove that $e^x \ge x + 1$. Indeed, by Bernoulli Inequality, we have \[ e^x = \lim_{n \to \infty} \left(1 + \frac{x}{n} \right)^n \ge 1 + n \cdot \frac{x}{n} = x + 1 \]which works since for large enough $n$, we have $\frac{x}{n} \ge -1$. Now, from our claim above, we have \[ e^{- \sum_i a_i} = \prod_i e^{-a_i} \ge \prod_i (1 - a_i). \] We'll now suppose the statement is true for $n = i$. Inductive Step 1. The statement is true for $n = 2i$. Proof. Now, let us rewrite \[ \frac{a_\ell}{\sqrt{a_1^2 + \dots + a_\ell^2}} = x_\ell \]Since $a_\ell \le [1,2^k]$ for every $\ell$, this means that $a_\ell \le 2^k a_m$ for any $\ell,m$. This gives us \[ (1 - x_{i + 1}^2)(1 - x_{i + 2}^2)\dots(1 - x_{2i}^2) = \frac{a_1^2 + \dots + a_i^2}{a_1^2 + \dots + a_{2i}^2} \ge \frac{1}{4^k + 1} \]Applying our claim, and $e > 2$, we have \begin{align*} e^{- \sum_{j = i + 1}^{2i} x_j^2} &\ge \prod_{j = i + 1}^{2i} (1 - x_j^2) \ge \frac{1}{4^k + 1} \\ \sum_{j = i + 1}^{2i} x_j^2 &\le \ln(4^k + 1) \le 2k \\ \sum_{j = i + 1}^{2i} x_j &\le \sqrt{i \cdot \left( \sum_{j = i + 1}^{2i} x_j^2 \right)} \le \sqrt{2ki} \end{align*}Therefore, by inductive hypothesis, we have \begin{align*} \sum_{j = 1}^{2i} x_j &= \sum_{j = 1}^i x_j + \sum_{j = i + 1}^{2i} x_j \\ &\le 4 \sqrt{ki} + \sqrt{2ki} \\ &\le 4 \sqrt{2ki} \end{align*} Inductive Step 2. The statement is true for $n = 2i + 1$. Proof. Similarly as before, we get \[ (1 - x_{i + 2}^2)(1 - x_{i + 3}^2)\dots (1 - x_{2i + 1}^2) = \frac{a_1^2 + \dots + a_{i + 1}^2}{a_1^2 + \dots + a_{2i + 1}^2} > \frac{a_1^2 + \dots + a_{i + 1}^2}{(a_1^2 + \dots + a_{i + 1}^2) + (a_{i + 1}^2 + \dots + a_{2i + 1}^2)} \ge \frac{1}{4^k + 1} \]where this inequality holds because $a_j^2 + a_{j + i}^2 \le (4^k + 1)a_j^2$ for all $1 \le j \le i + 1$. Therefore, similarly as before, we get \[ \sum_{j = i + 2}^{2i + 1} x_j < \sqrt{2ki} \]Therefore, \begin{align*} \sum_{j = 1}^{2i + 1} x_j &= \sum_{j = 1}^{i + 1} x_j + \sum_{j = i + 2}^{2i + 1} x_j \\ &\le 4\sqrt{k(i + 1)} + \sqrt{2ki} \\ &\le 4\sqrt{k(2i + 1)} \end{align*}where the last inequality holds because for $i \ge 8$, we have

We first solve the problem for $k=1$: indeed this is simple bounding. Observe that $\frac{\sum\limits_{t=1}^j a_t^2}{a_j^2} \ge \frac{j+3}{4}$. Hence it follows that the sum $$\sum\limits_{j=1}^n \frac{a_j}{\sqrt{\sum\limits_{t=1}^j a_t^2}} \le \sum\limits_{j=1}^n \frac{2}{\sqrt{j+3}} \le \sum\limits_{j=1}^n \frac{4}{\sqrt{j+1}+\sqrt{j}} = \sum\limits_{j=1}^n 4(\sqrt{j+1}-\sqrt{j}) = 4\sqrt{n+1}-4 \le 4\sqrt{n}$$ Note the same argument holds for any $\max a_i / \min a_i \le 2$. Now, for $k>1$, we first make a structural observation. Claim: The maximal sum is obtained when $a_1\le a_2\le \cdots \le a_n$. (Oh wait oops this is not necessary, I can just gather terms in each $[2^t, 2^{t+1})$ to do the same argument) Proof: Suppose $a_j>a_{j+1}$. Let $S=\sum\limits_{t=1}^{j-1} a_t^2$. The sum only differs in two terms: it suffices to show that $\frac{a_{j+1}}{\sqrt{S+a_{j+1}^2}} + \frac{a_j}{\sqrt{S+a_{j+1}^2+a_j^2}} < \frac{a_j}{\sqrt{S+a_{j}^2}} + \frac{a_{j+1}}{\sqrt{S+a_{j+1}^2+a_j^2}}$ Let $a_j=x, a_{j+1}=y$ We want to show $x(S+x^2)^{-\frac 12} < y(S+y^2)^{-\frac 12} + \frac{x-y}{\sqrt{S+x^2+y^2}}$ Rearranging, $(x-y)(\frac{1}{\sqrt{S+x^2}} - \frac{1}{\sqrt{S+x^2+y^2}}) < y(\frac{1}{\sqrt{S^2+y^2}} - \frac{1}{\sqrt{S^2+x^2}}$. Since $(x-y)y^2 < y(x-y)(x+y)$ It follows that $(x-y)(\sqrt{S+x^2+y^2}-\sqrt{S+x^2}) < y(\sqrt{S+x^2}-\sqrt{S+y^2})$ By dividing LHS by $\sqrt{S+x^2+y^2}+\sqrt{S+x^2}$ and RHS by $\sqrt{S+x^2}+\sqrt{S+y^2}$ Now dividing LHS by $\sqrt{S+x^2+y^2}\sqrt{S+x^2}$ and RHS by $\sqrt{S+x^2}\sqrt{S+y^2}$ proves the unnecessary claim. Now, suppose $a_{x_{t-1}+1}, \cdots, a_{x_t} \in [2^{t-1},2^t)$ for all $1\le t\le k$. Then $\sum\limits_{m=x_{t-1}+1}^{x_t} \frac{a_x}{\sqrt{\sum_{j=1}^x a_j^2}} \le \sum\limits_{m=x_{t-1}+1}^{x_t} \frac{a_x}{\sqrt{\sum_{j=x_{t-1}+1}^x a_j^2}} \le 4\sqrt{x_t-x_{t-1}}$ by the problem for $k=1$. Therefore, it suffices to show that $\sum\limits_{j=1}^k \sqrt{x_j-x_{j-1}}<\sqrt{kn}$ where $\sum\limits_{j=1}^k (x_j-x_{j-1})=n$. This is clear by Karamata, so the conclusion follows.

Lemma: The problem holds for $k=1$. Proof. We kill this with Cauchy-Schwarz + telescope. Note that \[ \frac1{\sqrt{a_1^2}}+\frac1{\sqrt{a_1^2+a_2^2}}+\dots+\frac1{\sqrt{a_1^2+\dots+a_n^2}} \le \sum_{i=1}^n \frac1{\sqrt{i}}. \]We telescope the RHS of the above to \[ \sum_{i=1}^n \frac1{\sqrt{i}} \le 1 + \sum_{i=1}^n \frac1{(\sqrt{i-1}+\sqrt{i})/2} = 2 \sqrt{n}-2+1 \le 2 \sqrt{n}, \]which returns the first bound. We similarly bound \[ \frac{a_1^2}{\sqrt{a_1^2}}+\frac{a_2^2}{\sqrt{a_1^2+a_2^2}}+\dots+\frac{a_n^2}{\sqrt{a_1^2+\dots+a_n^2}} \le a_1 + \sum_{i=1}^{n-1} \frac{a_i^2}{(\sqrt{a_1^2+\dots+a_i^2}+\sqrt{a_1^2+\dots+a_{i+1}^2})/2}. \]We again telescope and find \[ \frac{a_1^2}{\sqrt{a_1^2}}+\frac{a_2^2}{\sqrt{a_1^2+a_2^2}}+\dots+\frac{a_n^2}{\sqrt{a_1^2+\dots+a_n^2}} \le 2\sqrt{a_1^2+\dots+a_n^2}-2a_1+a_1 \le 4 \sqrt{n}. \]Let the first summation be denoted by $S_1$ and the second by $S_2$. By Cauchy-Schwarz, we have \[ \left(\frac{a_1}{\sqrt{a_1^2}}+\frac{a_2}{\sqrt{a_1^2+a_2^2}}+\dots+\frac{a_n}{\sqrt{a_1^2+\dots+a_n^2}}\right)^2 \le S_1 \cdot S_2 \le (2\sqrt{n}) \cdot (4\sqrt{n}) = 8n < (4\sqrt{n})^2, \]and we are done. Note that if we multiply each $a_i$ by some $\lambda$, then the LHS of the desired inequality remains the same. Thus if we take $\lambda$ a power of $2$, then the lemma holds when $a_1, \dots, a_n \in [2^j,2^{j+1}]$ for all $j$. Now we do the following amusing thing. Partition $\{a_1, \ldots, a_n\}$ into subsets $A_i$ consisting of all elements in $(2^i, 2^{i+1}]$ for $i \ge 1$ and $[1, 2]$ for $i=0$. Order the elements of $A_i$ in increasing order as $a_{i, 1}, a_{i, 2}, \ldots$ for each $i$. Thus we can rewrite the LHS of the desired inequality as \[ \sum_i \sum_j \frac{a_{i, j}}{a_1^2+\ldots+a_{i, j}^2} \le \sum_i \sum_j \frac{a_{i, j}}{a_{i, 1}^2+\ldots+a_{i, j}^2} \le \sum_i 4 \sqrt{|A_i|} \le 4k \sqrt{\frac{n}{k}} = 4\sqrt{kn}, \]with the second to last inequality by Jensen's, as desired. Remark: [motivations] The first thing that I noticed was that the inequality was homogeneous. That meant that if I proved the $k=1$ case, then I proved it for all intervals of the form $[2^j,2^{j+1}]$. So I proved the $k=1$ case using Cauchy-Schwarz and telescoping, somewhat motivated by the telescoping in 2016 A8, although in this case it was far simpler. The cool part was showing that we can prove the inequality for the union of all $[2^j,2^{j+1}]$; the hope was in the fact that you could partition $(a_i)$ into sets contained in these intervals and somehow use it to prove the final inequality. I first thought that to generalize it, I would need to use Titu's or something like that, but it worked out in a trivial way, and the finish was by Jensen.

As my 500th post!!! I will give an elegant solution to this problem, without induction. For $2\le i\le k$, define $S_i:=\{i\in [n]:2^{k-1}<a_i\le 2^k\}$, let $S_1:=\{i\in [n]:2^0\le a_i\le 2^1\}$. Let $n_t:=|S_t|$ for all $t\in [k]$, then $\sum _{t=1}^kn_t= n$. Therefore \begin{align*}\sum_{i = 1}^n \frac{a_i}{\sqrt{a_1^2 + \dots + a_i^2}} &=\sum_{t=1}^k\sum_{i\in S_t}\frac{a_i}{\sqrt{a_1^2 + \dots + a_i^2}}\\&\le\sum_{t=1}^k\sum_{i\in S_t}\frac{2^t}{\sqrt{(2^{t-1})^2\cdot\#\{j\in S_t:j\le i\}}}\\&=2\sum_{t=1}^k\left(\frac 1{\sqrt 1}+\frac 1{\sqrt 2}+\cdots+\frac 1{\sqrt {n_t}}\right)\\&\le 2\sum_{t=1}^k\int_0^{n_t}\frac{dx}{\sqrt x}=4\sum_{t=1}^k\sqrt{n_t}\\&\le 4\sqrt{k\sum_{t=1}^kn_t}\\&= 4 \sqrt{kn}\end{align*}Done.$\Box$ Remark. The idea here is dyadic decomposition, the benefit of it is that we can ge the upper and lower bounds in the same time, which is really useful in inequality.

Why