Let $a_1,a_2,\dots,a_m$ be a finite sequence of positive integers. Prove that there exist nonnegative integers $b,c,$ and $N$ such that $$\left\lfloor \sum_{i=1}^m \sqrt{n+a_i} \right\rfloor =\left\lfloor \sqrt{bn+c} \right\rfloor$$holds for all integers $n>N.$ Proposed by Carl Schildkraut
Problem
Source: ELMO 2018 #5, 2018 ELMO SL A2
Tags: algebra
28.06.2018 10:19
28.06.2018 10:20
28.06.2018 10:42
Let $S=a_1+a_2+\ldots + a_m$. If all the $a_i$ are the same, then take the obvious choice $(b,c)=\boxed{(m^2, mS)}$. Thus, assume not all the $a_i$ are the same; we claim the choice $(b,c)=\boxed{(m^2, mS-1)}$ works. First of all, note that $$\sqrt{n}+\frac{a}{2\sqrt{n}}-\sqrt{n+a}=\frac{a}{2\sqrt{n}}-\frac{a}{\sqrt{n}+\sqrt{n+a}}=a\left(\frac{\sqrt{n+a}-\sqrt{n}}{2\sqrt{n}(\sqrt{n+a}+\sqrt{n})}\right)=\frac{a^2}{2\sqrt{n}(\sqrt{n+a}+\sqrt{n})^2}=O(n^{-3/2})$$and thus $\sqrt{n+a}=\sqrt{n}+\frac{a}{2\sqrt{n}}-O(n^{-3/2})$. Thus, it follows that $$X=\sum_{i=1}^m \sqrt{n+a_i}=m\sqrt{n}+\frac{S}{2\sqrt{n}}-O(n^{-3/2})$$On the other hand, we have $$Y=\sqrt{m^2n+mS}=m\sqrt{n+\frac{S}{m}}=m\sqrt{n}+\frac{S}{2\sqrt{n}}-O(n^{-3/2})$$Thus, $Y-X=O(n^{-3/2})>0$ (note that $Y>X$ by QM-AM and the assumption that not all the $a_i$ are the same). On the other hand, note that $$Z=\sqrt{m^2n+mS-1}=Y-(\sqrt{m^2n+mS}-\sqrt{m^2n+mS-1})=Y-\frac{1}{\sqrt{m^2n+mS}+\sqrt{m^2n+mS-1}}<X$$since $Y-X=O(n^{-3/2})<\frac{1}{\sqrt{m^2n+mS}+\sqrt{m^2n+mS-1}}$ for $n$ large enough. Thus, $$\sqrt{m^2n+mS-1}<X<\sqrt{m^2n+mS}$$for $n$ large enough. Moreover, note that it is never possible for there to be an integer $a$ such that $\sqrt{t}<a<\sqrt{t+1}$ where $t$ is an integer. Thus, if $\lfloor \sqrt{m^2n+mS-1}\rfloor \neq \lfloor X\rfloor$, it follows that there is an integer $a$ satisfying $\sqrt{m^2n+mS-1}<a\le X<\sqrt{m^2n+mS}$, contradiction! Thus, $\lfloor \sqrt{m^2n+mS-1}\rfloor = \lfloor X\rfloor$ and the choice $(m^2, mS-1)$ satisfies the problem requirements as desired. $\square$
28.06.2018 11:16
Here is my solution for question 5 Suppose all $a_i$ are not equal. I choose $b=m^2$ and $c=m\sum_{k=1}^ma_k-1$ For any sequence of positive integers $a_k$ So first i intend to generate a lower bound. Claim $ m^2n+m\sum_{k=1}^ma_k-1 \geq (\lfloor\sqrt{n+a_1}+\sqrt{n+a_2}+\cdots \sqrt{n+a_m}\rfloor)^2$ Proof Applying cauchy-schawrz inequality $(1+1+1+1+...mtimes)(mn+\sum_{k=1}^ma_k)> (\sqrt{n+a_1}+\sqrt{n+a_2}+\cdots \sqrt{n+a_m})^2\geq (\lfloor\sqrt{n+a_1}+\sqrt{n+a_2}+\cdots \sqrt{n+a_m}\rfloor)^2 $ Thus $m^2n+m\sum_{k=1}^ma_k\geq (\lfloor\sqrt{n+a_1}+\sqrt{n+a_2}+\cdots \sqrt{n+a_m}\rfloor)^2+1$ $\implies \sqrt{m^2n+m\sum_{k=1}^ma_k-1}\geq (\lfloor\sqrt{n+a_1}+\sqrt{n+a_2}+\cdots \sqrt{n+a_m})\rfloor$ which is indeed our claim.$\square$ Now i construct an another sequence $m^2n+m\sum_{k=1}^ma_k-\frac{(m^2-m)l}{2}$ such that $l<\frac{2}{m^2-m}$. Now we would using this sequence to create an upper bound. Claim-2 $m^2n+m\sum_{k=1}^ma_k-1<m^2n+m\sum_{k=1}^ma_k-\frac{m^2-m}{2}l$ Proof As we had chosen $l<\frac{2}{m^2-m}$ so inequality is proven. Claim-3 $m^2n+m\sum_{k=1}^ma_k-\frac{m^2-m}{2}l<(\sqrt{n+a_1}+\sqrt{n+a_2}+\cdots \sqrt{n+a_m})^2$ for large n. Proof Expanding rhs of the inequality, $\implies R.H.S=mn+\sum_{k=1}^ma_k+2(\sqrt{n+a_1}\cdot\sqrt{n+a_2}....)$ Manipulating lhs we get $\implies L.H.S=mn+\sum_{k=1}^ma_k+2(\frac{m^2-m}{2}n+\frac{(m-1)(\sum_{k=1}^ma_k)}{2}-\frac{m^2-m}{4}l)$ On deep analysis we find that $rhs-lhs=2(( \sqrt{n^2+a_1n+a_2n+a_1a_2} -(n +\frac{a_1+a_{2}-l}{2})+ \sqrt{n^2+a_1n+a_3n+a_1a_3}-(n+\frac{a_1+a_{3}-l}{2}).....(m-1)terms)+(\sqrt{n^2+a_2n+a_3n+a_2a_3}-(n+\frac{a_2+a_{3}-l}{2})+ \sqrt{n^2+a_2n+a_4n+a_2a_4}-(n+\frac{a_2+a_{4}-l}{2}).....(m-2)terms)...and so on)$ Now lets check individual terms $\sqrt{n+a_b} \cdot \sqrt{n+a_{b+x}}>(n+\frac{a_b+a_{b+x}-l}{2})$ $\implies n^2+(a_b+a_{b+x})n+a_b\cdot a_{b+x}> n^2+(a_b+a_{b+x}-l)n+(\frac{a_b+a_{b+x}-l}{2})^2$ $\implies ln>(\frac{a_b+a_{b+x}-l}{2})^2$ Which is true for very large n such that $n>(a_b+a_{b+x})^2$ for all terms of a particular sequence. Thus $R.H.S>L.H.S$$\square$ Now using claim 3 we can say $m^2n+m\sum_{k=1}^ma_k-\frac{m^2-m}{2}l<(\lfloor\sqrt{n+a_1}+\sqrt{n+a_2}+\cdots \sqrt{n+a_m}\rfloor+1)^2$. Now using all our claims we get that for n such that $n>(a_b+a_{b+x})^2$ for all terms of a particular sequence and $(b,c)=(m^2,m\sum_{k=1}^ma_k-1)$ $(\lfloor\sqrt{n+a_1}+\sqrt{n+a_2}+\cdots \sqrt{n+a_m}\rfloor+1)^2>m^2n+m\sum_{k=1}^ma_k-1 \geq (\lfloor\sqrt{n+a_1}+\sqrt{n+a_2}+\cdots \sqrt{n+a_m}\rfloor)^2$ which is indeed the question. Edit:the case when all terms are equal is trivial.
28.06.2018 17:41
If all the $a_i$ are equal, then $\sum_{i=1}^m \sqrt{n+a_i} = \sqrt{m^2 n + m^2 a_1}$ and so $(b,c) = (m^2, m^2a_1)$ works fine. Let us assume this is not the case. Instead, will take $b = m^2$ and $c = m(a_1+\dots+a_m)-1$ and claim it works for $N$ large enough. On the one hand, \begin{align*} \sum_{i=1}^m \sqrt{n+a_i} &< m \cdot \sqrt{n + \frac{a_1 + \dots + a_m}{m}} \\ &= \sqrt{m^2 \cdot n + c + 1} \le \left\lceil \sqrt{m^2 \cdot n + c + 1} \right\rceil \le \left\lfloor \sqrt{m^2 \cdot n + c} \right\rfloor + 1. \end{align*}On the other hand, let $\lambda = \frac{c}{2(c+1)} < \frac{1}{2}$. We use the following estimate. Claim: If $n$ is large enough in terms of $(a_1, \dots, a_n)$ then $\sqrt{n+a_i} \ge \sqrt{n} + \frac{\lambda a_i}{\sqrt n}$. Proof. Squaring both sides, it's equivalent to $a_i \ge 2\lambda \cdot a_i + \frac{\lambda^2 a_i^2}{n}$, which holds for $n$ big enough as $2\lambda < 1$. $\blacksquare$ Now, \begin{align*} \sum_{i=1}^m \sqrt{n+a_i} &\ge \sum_{i=1}^m \left( \sqrt n + \frac{\lambda a_i}{\sqrt n} \right) \\ &\ge m \sqrt n + \frac{\lambda \cdot (a_1 + \dots + a_n)}{\sqrt n} \\ &= m \sqrt n + \frac{\lambda \cdot (c+1)}{m\sqrt n} \\ &= m \sqrt n + \frac{c}{2m\sqrt n} > \sqrt{m^2 \cdot n + c} &\ge \left\lfloor \sqrt{m^2n + c} \right\rfloor. \end{align*}This finishes the problem. Remark: Obviously, $b = m^2$ for asymptotic reasons (by taking $n$ large). As for possible values of $c$: If $a_1 = \dots = a_m$, then one can show $c = m(a_1 + \dots + a_m)$ is the only valid choice. Indeed, taking $n$ of the form $n = k^2-a$ and $n = \frac{k^2-1}{m^2}-a$ is enough to see this. But if not all $a_i$ are equal, the natural guess of taking $c = m(a_1+\dots+a_n)$ is not valid in general. For example, we have that \[ \left\lfloor \sqrt{n}+\sqrt{n+2} \right\rfloor \neq \left\lfloor \sqrt{4n+4} \right\rfloor \qquad n \in \{t^2-1 \mid t = 2, 3, \dots \}. \]I think one can actually figure out exactly which $c$ are valid, though the answer will depend on some quadratic residues, and we do not pursue this line of thought here. So any correct solutions must distinguish these two cases.
30.06.2018 15:17
Actually $ \left\lceil \sqrt{m^2 \cdot n + c + 1} \right\rceil =\left\lfloor \sqrt{m^2 \cdot n + c} \right\rfloor + 1. $
03.11.2019 04:10
Let $S=a_1+a_2+\cdots+a_m$. If $a_1=a_2=\cdots=a_m$, take $b=m^2$ and $c=mS$; henceforth assume that they are not all equal. We claim that taking $b=m^2$ and $c=mS-1$ is valid. For the upper bound, by Jensen's Inequality \[\sum_{i=1}^m\sqrt{n+a_i}<m\sqrt{n+\frac Sm}=\sqrt{bn+c+1}\le\left\lfloor\sqrt{bn+c}\right\rfloor+1,\]so we only need to prove that $\textstyle\sum_{i=1}^m\sqrt{n+a_i}\ge\left\lfloor\sqrt{bn+c}\right\rfloor$. Claim. For all $k<1/2$ and $x$, there is an $N$ such that for all $n>N$, we have $\sqrt{n+x}\ge\sqrt n+k\frac x{\sqrt n}$. Proof. Squaring both sides, we find that the inequality holds when\[\left(\sqrt n+\frac{kx}{\sqrt n}\right)^2\le\left(\sqrt{n+x}\right)^2\iff n\ge\frac{k^2x}{1-2k},\]as desired. $\blacksquare$ By the above argument, $\sqrt{n+x}\ge\sqrt n+\frac x{2\sqrt n}$ for all $n$ and $x$. Take some $k<1/2$ such that \[\frac{kS}{\sqrt n}\ge\frac{mS-1}{2m\sqrt n}\iff k\ge\frac12-\frac1{2mS}.\]We arrive at the conclusion that \[\sum_{i=1}^n\sqrt{n+a_i}\ge m\sqrt n+\frac{kS}{\sqrt n}\ge m\sqrt n+\frac{mS-1}{2m\sqrt n}\ge\sqrt{bn+c}\]for sufficiently large $n$, which is sufficient.
31.07.2020 16:53
19.11.2020 13:18
Solved with dantaxyz. Define $A:=\sum_{i=1}^m \sqrt{n+a_i}$ and $S=a_1+\cdots+a_n$. The main idea to prove $\lfloor A \rfloor = \lfloor \sqrt{bn+c} \rfloor$ is to instead show \[ \sqrt{bn+c} \le A < \sqrt{bn+c+1}, \]which is sufficient since there are no integers in $[\sqrt{t},\sqrt{t+1}]$ for an integer $t$. Obviously take $b=m^2$. The key is to use $c=mS-1$. Upper Bound: We have \begin{align*} \sqrt{bn+c+1} &= \sqrt{m^2n+mS} = m\sqrt{n+\frac{S}{m}} > \sum_{i=1}^m \sqrt{n+a_i} = A \end{align*}by concave Jensen's inequality, assuming the $a_i$'s are not all equal. Lower Bound: For some $N$, we have $n>N$ the estimate (well-known by second-order Taylor expansion): \[ \sqrt{1+\frac{a_i}{n}} \ge 1 + \frac{a_i}{2n} - \frac{a_i}{8n^2} \]Multiplying by $\sqrt{n}$ and summing over all $i$ gives \[ A\ge m\sqrt{n} + \frac{S}{2\sqrt{n}} - \frac{S}{8n\sqrt{n}}. \]We claim the RHS above is at least $\sqrt{bn+c}$, which would finish. Indeed, \begin{align*} &\qquad m\sqrt{n} + \frac{S}{2\sqrt{n}} - \frac{S}{8n\sqrt{n}} \ge \sqrt{bn+c} = \sqrt{m^2n+mS-1} \\ &\iff m^2n + \frac{S^2}{4n} + \frac{S^2}{64n^3} + 2\left( \frac{mS}{2} - \frac{mS}{8n} - \frac{S^2}{16n^2}\right) \ge m^2n + mS - 1 \\ &\iff \frac{S^2}{4n} + \frac{S^2}{64n^3} - \frac{mS}{4n} - \frac{S^2}{8n^2} \ge -1 \\ &\iff -16n^2S^2 - S^2 + 16n^2mS + 8nS^2 \le 64n^3, \end{align*}which is true for large enough $n$ since the LHS is $O(n^2)$ and the RHS is $O(n^3)$.
16.07.2021 18:35
Define $S=a_1+\cdots+a+m$. If all the $a_i$ are equal, then we can take $(b,c)=(m^2,mS)$, which clearly works. Henceforth suppose otherwise, in which case I claim $(b,c)=(m^2,mS-1)$ works. We begin with the following claim: Claim: If $k<mS$, then for sufficiently large $n$ we have $$\sum_{i=1}^m \sqrt{n+a_i}\geq \sqrt{m^2n+k}$$Proof: By AM-GM it suffices to show that for sufficiently large $n$ we have $$m\sqrt[2m]{(n+a_1)(n+a_2)\ldots(n+a_m)}\geq \sqrt{m^2n+k} \iff m^{2m}(n+a_1)(n+a_2)\ldots(n+a_m)\geq (m^2n+k)^m$$Now note that the LHS is $$m^{2m}n^m+m^{2m}Sn^{m-1}+O(n^{m-2}),$$wheras the RHS is $$m^{2m}n^m+m^{2m-1}kn^{m-1}+O(n^{m-2}).$$As $k<mS$, it follows that LHS-RHS is $O(n^{m-1})$, so the inequality holds for all sufficiently large $n$. Importantly, this claim implies that for sufficiently large $n$ we have $$\sum_{i=1}^m \sqrt{n+a_i}\geq \sqrt{m^2n+(mS-1)}.$$By Jensen's, we also have $$\sum_{i=1}^m \sqrt{n+a_i}<\sqrt{m^2n+mS},$$as not all the $a_i$ are equal. Now, I claim that if $m^2n+mS$ is a perfect square, then $$\left\lfloor \sum_{i=1}^m \sqrt{n+a_i} \right\rfloor =\left\lfloor \sqrt{m^2n+mS} \right\rfloor-1=\left\lfloor \sqrt{m^2+(mS-1)}\right\rfloor.$$The right-side inequality is clear. To prove the left-hand inequality, we have $$\sqrt{m^2+(mS-1)}\leq \sum_{i=1}^m \sqrt{n+a_i}<\sqrt{m^2n+mS},$$for sufficiently large $n$, and since $\sqrt{m^2n+mS}$ is an integer it follows that $$\left\lfloor\sqrt{m^2+(mS-1)}\right\rfloor\leq \left\lfloor\sum_{i=1}^m \sqrt{n+a_i}\right\rfloor<\left\lfloor\sqrt{m^2n+mS}\right\rfloor,$$(again for sufficiently large $n$), which implies the equality. Next, I claim that if $m^2n+mS$ is not a perfect square, we have $$\left\lfloor \sum_{i=1}^m \sqrt{n+a_i} \right\rfloor =\left\lfloor \sqrt{m^2n+mS} \right\rfloor=\left\lfloor \sqrt{m^2+(mS-1)}\right\rfloor.$$Again, the left equality is obvious, while the right equality follows as $$\sqrt{m^2+(mS-1)}\leq \sum_{i=1}^m \sqrt{n+a_i}<\sqrt{m^2n+mS},$$for large enough $n$, so $$\left\lfloor\sqrt{m^2+(mS-1)}\right\rfloor\leq \left\lfloor\sum_{i=1}^m \sqrt{n+a_i}\right\rfloor\leq\left\lfloor\sqrt{m^2n+mS}\right\rfloor$$for $n$ large enough. Combining these two cases implies that $(b,c)=(m^2,mS-1)$ works, so we're done. $\blacksquare$
07.03.2022 21:56
We want to find some $c \in \mathbb{N}$ such that $\sqrt{bn+c} < \sum_{i=1}^{m} \sqrt{n+a_i} < \sqrt{bn+c+1}$, what better way to do than explicitly find such a $c$ given the $a_i$'s. Firstly, if $a_1 = \cdots = a_m$ take $b = m^2$ and $c = ma_1$ which can be verified to work, otherwise, we will take $b = m^2$ and $c = m \cdot \sum_{i=1}^{m} a_i-1$ $\textbf{Lemma 1}$ We have the following inequality $$\sum_{i=1}^{m} \sqrt{n+a_i} < \sqrt{m^2n+m \cdot (\sum_{i=1}^{m} a_i)}$$$\textbf{Proof}$ This follows by Jensen's inequality on $f(x) = \sqrt{n+x}$ which is concave over the positive reals. $\blacksquare$ $\textbf{Lemma 2}$ We have the following inequality for all sufficiently large $n \in \mathbb{N}$ $$\sum_{i=1}^{m} \sqrt{n+a_i} > \sqrt{m^2n+m \cdot (\sum_{i=1}^{m} a_i)-1}$$$\textbf{Proof}$ Notice that $$(\frac{\sum_{i=1}^{m} \sqrt{n+a_i}}{m})^{2m} > \prod_{i=1}^{m} (n+a_i) \geq (n+\frac{(\sum_{i=1}^{m} a_i)-1}{m})^m$$where the first inequality follows by AM-GM and the second inequality is because if we define $$P(n) = \prod_{i=1}^{m} (n+a_i)-(n+\frac{(\sum_{i=1}^{m} a_i)-1}{m})^m$$then $P(n) > 0$ for all sufficiently large $n$ because the leading coefficent of $P$ is positive. $\blacksquare$ We therefore have that $\sqrt{m^2n+c} < \sum_{i=1}^{m} \sqrt{n+a_i} < \sqrt{m^2n+c+1}$ for $c = \frac{(\sum_{i=1}^{m} a_i)-1}{m}$ for all sufficiently large $n \in \mathbb{N}$ by $\textbf{Lemma 1}$ and $\textbf{Lemma 2}$ which means that $\lfloor \sqrt{m^2n+c} \rfloor = \lfloor \sum_{i=1}^{m} \sqrt{n+a_i} \rfloor$ for all sufficiently large $n \in \mathbb{N}$, as desired. $\blacksquare$
17.07.2023 17:37
Obviously we have to set $b=m^2$ due to size reason. If all $a_i$ are the same, just take $c=m^2\cdot a_1$. From here we assume that not all $a_i$ are equal. We will show that $c=mS-1$ works, where $S:=\sum\limits_{i=1}^ma_i$. Claim: For sufficiently large $n$, we have $$\sqrt{m^2n+mS-1}<\sum \limits_{i=1}^m \sqrt{n+a_i} <\sqrt{m^2n+mS}$$Proof of the claim: First notice that by Cauchy-Schwarz inequality $$\sum \limits_{i=1}^m \sqrt{n+a_i} \leq \sqrt{m\sum \limits_{i=1}^m(n+a_i)} =\sqrt{m^2n+mS} \quad (\star)$$And not all $a_i$ are equal, whereupon the equality case in $(\star)$ cannot hold, thus $$\sum \limits_{i=1}^m \sqrt{n+a_i} <\sqrt{m^2n+mS}$$Set $\delta _n=\sum \limits_{i=1}^m \sqrt{n+a_i}-\sqrt{m^2n+mS-1}$. We know that $$ \delta_n =\sum\limits_{i=1}^m(\sqrt{n+a_i}-\sqrt{n+\frac{S}{m}-\frac{1}{m^2}}) =\sum\limits_{i=1}^m\frac{a_i-\frac{S}{m}+\frac{1}{m^2}}{\sqrt{n+a_i}+\sqrt{n+\frac{S}{m}-\frac{1}{m^2}}} $$As a result, $\lim_{n\to \infty}\sqrt{n}\delta_n=\sum\limits_{i=1}^m\frac{1}{2}(a_i-\frac{S}{m}+\frac{1}{m^2})=\frac{1}{2m}>0$. Hence for sufficiently large $n$, $\delta_n>0$. The claim is proved. $\blacksquare$ From the claim we can easily conclude that $$\left\lfloor \sum_{i=1}^m \sqrt{n+a_i} \right\rfloor =\left\lfloor \sqrt{bn+c} \right\rfloor$$is true for $(b,c)=(m^2,mS-1)$ and sufficiently large $n$.
20.08.2024 20:15
I'll explain my thinking during the solution for a little motivation. Notice that if we pick $n$ super big, the LHS and RHS approach $m\sqrt{n}$ and $\sqrt{bn}$, respectively. So we guess that $b=m^2$. From CBS we have $$m((n+a_1)+(n+a_2)+\ldots+(n+a_m))\ge\left(\sum_{i=1}^m \sqrt{n+a_i}\right)^2$$So we get $$\sum_{i=1}^m \sqrt{n+a_i}\le \sqrt{m^2n+m\sum_{i=1}^m a_i}$$ If the $a_i$ are equal, we have equality so just pick $c=m\sum_{i=1}^m a_i$. Now notice that for big enough $n$ this inequality is pretty tight since all the $n+a_i$ are close together. Therefore $c=m\sum_{i=1}^m a_i-1$ will most likely work. Now if the $a_i$ aren't equal we get $$\sum_{i=1}^m \sqrt{n+a_i} < \sqrt{m^2n+m\sum_{i=1}^m a_i}\le \left\lfloor \sqrt{m^2n+m\sum_{i=1}^m a_i-1}\right\rfloor + 1$$ Now we just need to show that $$\sum_{i=1}^m \sqrt{n+a_i}\ge \sqrt{m^2n+m\sum_{i=1}^m a_i-1}$$$$\iff 2\sum_{i\neq j}\sqrt{(n+a_i)(n+a_j)}\ge m(m-1)n+(m-1)\sum_{i=1}^m a_i-1$$ So we need some inequality $\sqrt{(n+a_i)(n+a_j)}\ge n+x \iff n(a_i+a_j)+a_ia_j\ge 2nx+x^2$ that holds for all sufficiently large $n$. Therefore we have $x \le \frac{1}{2}(a_i+a_j)$ so just pick $x=\frac{1}{2}(a_i+a_j-\epsilon)$. Substituting in we have $$n\cdot \epsilon\ge \left(\frac{1}{4}a_i+a_j-\epsilon\right)^2-a_ia_j$$ And this is true for big enough $n$. Now choose $\epsilon=\frac{2}{m(m-1)}$. We have that $\sqrt{(n+a_i)(n+a_j)}\ge n+\frac{1}{2}\left(a_i+a_j-\frac{2}{m(m-1)}\right)$ so summing for all pairs we get the desired inequality. $\square$
13.11.2024 19:48
Let $S = a_1 + a_2 + \dots + a_m$. If all $a_i$ are equal, then we set $b = m^2$ and $c = mS$. Now, if not all $a_i$ are equal, we set $b = m^2$ and $c = mS - 1$. Then it suffices to show that $$ \sqrt{m^2 n + c} < \sum_{k=1}^m \sqrt{n + a_k} < \sqrt{m^2 n + c + 1}. $$For the upper bound, observe that by Jensen's inequality we have $$ \sum_{k=1}^m \sqrt{n + a_k} < m \sqrt{n + \frac{S}{m}} = \sqrt{m^2 n + m S} = \sqrt{m^2 n + c + 1}. $$For the lower bound, by AM-GM it suffices to show that $$ m \sqrt[2m]{(n + a_1)(n + a_2) \cdots (n + a_k)} \geq \sqrt{m^2 n + c}. $$For $n$ large enough. This is equivalent to showing that $$ m^{2m} (n + a_1)(n + a_2) \cdots (n + a_m) - (m^2 n + c)^m \geq 0. $$For $n$ large enough. The leading coefficient of this polynomial is $$ m^{2m} S - m^{2m-1}(m S - 1) = m^{2m - 1} > 0. $$Therefore, the inequality holds, and we are done with the problem.