Shortlist 2020, A7¶

Domaine : Algèbre · Difficulté : ★★★★☆ · Proposé par : Iran

Concepts : Sommes, télescopage et transformation d'Abel · Cauchy-Schwarz et lemme de Titu

Solution officielle : Shortlist officielle 2020 (avec solutions), p. 24 (page 26 du PDF)

Énoncé¶

Let \(n\) and \(k\) be positive integers. Prove that for \(a_1, \ldots, a_n \in [1, 2^k]\) one has

\[\sum_{i=1}^{n} \frac{a_i}{\sqrt{a_1^2 + \cdots + a_i^2}} \leq 4\sqrt{kn}.\]

Indices : les idées clés

Découpage dyadique (solution 1) : on regroupe les indices selon l'intervalle \([2^{j-1}, 2^j]\) qui contient \(a_\ell\) ; dans chaque groupe le dénominateur croît comme \(\sqrt{i}\).
Télescopage : \(\frac{1}{\sqrt{i}} \leq 2(\sqrt{i} - \sqrt{i - 1})\) (solution 1), et le produit \(\prod (1 - x_\ell^2)\) se simplifie en cascade (solution 2).
Cauchy-Schwarz / inégalité QM-AM : \(\sum_{j=1}^{k} \sqrt{|M_j|} \leq \sqrt{k\sum |M_j|}\) (solution 1), et \(\sum x_\ell \leq \sqrt{t \sum x_\ell^2}\) (solution 2).
Récurrence en coupant en deux (solution 2) : la seconde moitié contribue au plus \(\sqrt{2kt}\), grâce à \(1 - y \leq e^{-y}\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2020 (deux solutions et deux remarques).

Solution 1¶

Partitionnons l'ensemble des indices \(\{1, 2, \ldots, n\}\) en sous-ensembles disjoints \(M_1, M_2, \ldots, M_k\) tels que \(a_\ell \in [2^{j-1}, 2^j]\) pour \(\ell \in M_j\) (découpage dyadique). Si \(|M_j| =: p_j\), on a

\[\sum_{\ell \in M_j} \frac{a_\ell}{\sqrt{a_1^2 + \cdots + a_\ell^2}} \leq \sum_{i=1}^{p_j} \frac{2^j}{2^{j-1}\sqrt{i}} = 2\sum_{i=1}^{p_j} \frac{1}{\sqrt{i}},\]

car \(a_\ell \leq 2^j\) et, dans le dénominateur, chaque indice de \(M_j\) déjà rencontré (y compris \(\ell\)) apporte au moins \((2^{j-1})^2\) : si \(\ell\) est le \(i\)-ème élément de \(M_j\), le dénominateur est au moins \(2^{j-1}\sqrt{i}\).

Ensuite, \(\sqrt{i} - \sqrt{i - 1} = \frac{1}{\sqrt{i} + \sqrt{i - 1}} \geq \frac{1}{2\sqrt{i}}\), d'où par télescopage

\[\sum_{\ell \in M_j} \frac{a_\ell}{\sqrt{a_1^2 + \cdots + a_\ell^2}} \leq 2\sum_{i=1}^{p_j} \frac{1}{\sqrt{i}} \leq 2\sum_{i=1}^{p_j} 2\left(\sqrt{i} - \sqrt{i - 1}\right) = 4\sqrt{p_j}.\]

En sommant sur \(j = 1, \ldots, k\) et en utilisant l'inégalité QM-AM (ou Cauchy-Schwarz), on obtient

\[\sum_{\ell=1}^{n} \frac{a_\ell}{\sqrt{a_1^2 + \cdots + a_\ell^2}} \leq 4\sum_{j=1}^{k} \sqrt{|M_j|} \leq 4\sqrt{k\sum_{j=1}^{k} |M_j|} = 4\sqrt{kn}. \ \blacksquare\]

Solution 2¶

On raisonne par récurrence sur \(n\). Si \(n \leq 16\), c'est clair : chaque terme est au plus \(1\), donc la somme ne dépasse pas \(n \leq 4\sqrt{nk}\) (car \(n \leq 16 \leq 16k\)). Pour l'hérédité, de \(1, \ldots, n - 1\) à \(n \geq 17\), on distingue deux cas semblables. Notons

\[x_\ell = \frac{a_\ell}{\sqrt{a_1^2 + \cdots + a_\ell^2}}.\]

Cas 1 : \(n = 2t\). Comme \(1 - y \leq e^{-y}\),

\[\exp\left(-x_{t+1}^2 - \cdots - x_{2t}^2\right) \geq \left(1 - x_{t+1}^2\right)\cdots\left(1 - x_{2t}^2\right) = \frac{a_1^2 + \cdots + a_t^2}{a_1^2 + \cdots + a_{2t}^2} \geq \frac{1}{1 + 4^k}.\]

En effet, \(1 - x_\ell^2 = \frac{a_1^2 + \cdots + a_{\ell-1}^2}{a_1^2 + \cdots + a_\ell^2}\), donc le produit est télescopique ; puis on utilise \(a_{t+i} \leq 2^k a_i\) pour \(i = 1, \ldots, t\), d'où \(a_{t+1}^2 + \cdots + a_{2t}^2 \leq 4^k(a_1^2 + \cdots + a_t^2)\). Par conséquent

\[x_{t+1}^2 + \cdots + x_{2t}^2 \leq \log(4^k + 1) \leq 2k\]

(\(\log\) désignant le logarithme népérien). Par Cauchy-Schwarz, \(x_{t+1} + \cdots + x_{2t} \leq \sqrt{t \cdot 2k} = \sqrt{2kt}\). Avec l'hypothèse de récurrence pour \(n = t\) :

\[\sum_{\ell=1}^{2t} x_\ell \leq 4\sqrt{kt} + \sqrt{2kt} \leq 4\sqrt{2kt}.\]

Cas 2 : \(n = 2t + 1\). De la même façon (en comparant \(a_{t+1+i}\) à \(a_i\)), on obtient \(x_{t+2}^2 + \cdots + x_{2t+1}^2 \leq \log(4^k + 1) \leq 2k\), et, avec l'hypothèse de récurrence pour \(n = t + 1\),

\[\sum_{\ell=1}^{2t+1} x_\ell \leq 4\sqrt{k(t + 1)} + \sqrt{2kt} \leq 4\sqrt{k(2t + 1)}.\]

La dernière inégalité est vraie pour tout \(t \geq 8\) (ce qui est le cas car \(n \geq 17\)), puisque

\[4\sqrt{2t + 1} - \sqrt{2t} \geq 3\sqrt{2t} = \sqrt{18t} \geq \sqrt{16t + 16} = 4\sqrt{t + 1}. \ \blacksquare\]

Remarques¶

Remarque 1 (ranger dans l'ordre croissant). Considérons \(f(a_1, \ldots, a_n) = \sum_{i=1}^{n} \frac{a_i}{\sqrt{a_1^2 + \cdots + a_i^2}}\). Réordonner les variables dans l'ordre croissant ne peut qu'augmenter \(f\). En effet, si \(a_j > a_{j+1}\) pour un indice \(j\), en notant \(a = a_j\), \(b = a_{j+1}\) et \(S = \sqrt{a_1^2 + \cdots + a_{j+1}^2}\),

\[f(a_1, \ldots, a_{j-1}, a_{j+1}, a_j, a_{j+2}, \ldots, a_n) - f(a_1, \ldots, a_n) = \frac{a}{S} + \frac{b}{\sqrt{S^2 - a^2}} - \frac{b}{S} - \frac{a}{\sqrt{S^2 - b^2}},\]

et cette quantité est positive car

\[\frac{b}{\sqrt{S^2 - a^2}} - \frac{b}{S} = \frac{a^2b}{S\sqrt{S^2 - a^2}\left(S + \sqrt{S^2 - a^2}\right)} > \frac{ab^2}{S\sqrt{S^2 - b^2}\left(S + \sqrt{S^2 - b^2}\right)} = \frac{a}{\sqrt{S^2 - b^2}} - \frac{a}{S}.\]

Remarque 2 (optimalité). Si \(k < n\), l'exemple \(a_m := 2^{k(m-1)/n}\) montre que l'énoncé est optimal à une constante multiplicative près. Si \(k \geq n\), c'est la majoration triviale par \(n\) qui est optimale à une constante multiplicative près.