Shortlist 2007, A5

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

Concepts : Suites et récurrences · Cauchy-Schwarz et lemme de Titu

Solution officielle : Shortlist officielle 2007 (avec solutions), p. 16 (page 17 du PDF)

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

Let \(c > 2\), and let \(a(1), a(2), \ldots\) be a sequence of nonnegative real numbers such that

\[a(m + n) \leq 2a(m) + 2a(n) \qquad \text{for all } m, n \geq 1, \tag{1}\]

and

\[a(2^k) \leq \frac{1}{(k + 1)^c} \qquad \text{for all } k \geq 0. \tag{2}\]

Prove that the sequence \(a(n)\) is bounded.

Indices : les idées clés

• Sous-additivité itérée : \(a\left(\sum_{i=1}^k n_i\right) \leq \sum 2^i a(n_i)\) et \(\leq 2k\sum a(n_i)\) ; plus finement, \(\leq \sum 2^{s_i}a(n_i)\) dès que \(\sum 2^{-s_i} \leq 1\) (inégalité de type Kraft).
• Écriture binaire : \(n = \sum 2^{u_i}\) ; en regroupant les chiffres par blocs \([M_{k-1}, M_k)\) avec \(M_k = 4^{k/(c-2)} - 1\), on obtient une série géométrique convergente.
• Optimalité : la condition \(c > 2\) est nécessaire ; pour \(c \leq 2\), la suite extrémale n'est pas bornée, par Cauchy-Schwarz.

Solutions

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

Solution 1

Par commodité, posons \(a(0) = 0\) ; la condition (1) reste alors vraie pour tous couples d'indices positifs ou nuls.

Lemme 1. Pour des indices positifs ou nuls quelconques \(n_1, \ldots, n_k\), on a

\[a\left(\sum_{i=1}^{k} n_i\right) \leq \sum_{i=1}^{k} 2^ia(n_i) \tag{3}\]

et

\[a\left(\sum_{i=1}^{k} n_i\right) \leq 2k\sum_{i=1}^{k} a(n_i). \tag{4}\]

Preuve. L'inégalité (3) se prouve par récurrence sur \(k\). Le cas de base \(k = 1\) est trivial, et l'hérédité est donnée par

\[a\left(\sum_{i=1}^{k+1} n_i\right) = a\left(n_1 + \sum_{i=2}^{k+1} n_i\right) \leq 2a(n_1) + 2a\left(\sum_{i=1}^{k} n_{i+1}\right) \leq 2a(n_1) + 2\sum_{i=1}^{k} 2^ia(n_{i+1}) = \sum_{i=1}^{k+1} 2^ia(n_i).\]

Pour établir (4), on prouve d'abord l'inégalité

\[a\left(\sum_{i=1}^{2^d} n_i\right) \leq 2^d\sum_{i=1}^{2^d} a(n_i)\]

par une récurrence évidente sur \(d\). Ensuite, pour (4), on choisit un entier \(d\) tel que \(2^{d-1} < k \leq 2^d\) pour obtenir

\[a\left(\sum_{i=1}^{k} n_i\right) = a\left(\sum_{i=1}^{k} n_i + \sum_{i=k+1}^{2^d} 0\right) \leq 2^d\left(\sum_{i=1}^{k} a(n_i) + \sum_{i=k+1}^{2^d} a(0)\right) = 2^d\sum_{i=1}^{k} a(n_i) \leq 2k\sum_{i=1}^{k} a(n_i). \qquad \square\]

Fixons une suite croissante non bornée \(0 = M_0 < M_1 < M_2 < \cdots\) de réels ; les valeurs exactes seront précisées plus loin. Soit \(n\) un entier strictement positif quelconque, écrit

\[n = \sum_{i=0}^{d}\varepsilon_i \cdot 2^i, \qquad \text{où } \varepsilon_i \in \{0, 1\}.\]

Posons \(\varepsilon_i = 0\) pour \(i > d\), et prenons un entier \(f > 0\) tel que \(M_f > d\). En appliquant (3), on obtient

\[a(n) = a\left(\sum_{k=1}^{f}\sum_{M_{k-1} \leq i < M_k}\varepsilon_i \cdot 2^i\right) \leq \sum_{k=1}^{f} 2^ka\left(\sum_{M_{k-1} \leq i < M_k}\varepsilon_i \cdot 2^i\right).\]

Remarquons qu'il y a moins de \(M_k - M_{k-1} + 1\) entiers dans l'intervalle \([M_{k-1}, M_k)\) ; donc, avec (4), on a

\[\begin{aligned} a(n) &\leq \sum_{k=1}^{f} 2^k \cdot 2(M_k - M_{k-1} + 1)\sum_{M_{k-1} \leq i < M_k}\varepsilon_i \cdot a(2^i) \\ &\leq \sum_{k=1}^{f} 2^k \cdot 2(M_k - M_{k-1} + 1)^2\max_{M_{k-1} \leq i < M_k} a(2^i) \\ &\leq \sum_{k=1}^{f} 2^{k+1}(M_k + 1)^2 \cdot \frac{1}{(M_{k-1} + 1)^c} = \sum_{k=1}^{f}\left(\frac{M_k + 1}{M_{k-1} + 1}\right)^2\frac{2^{k+1}}{(M_{k-1} + 1)^{c-2}}. \end{aligned}\]

En posant \(M_k = 4^{k/(c-2)} - 1\), on obtient

\[a(n) \leq \sum_{k=1}^{f} 4^{2/(c-2)}\frac{2^{k+1}}{\left(4^{(k-1)/(c-2)}\right)^{c-2}} = 8 \cdot 4^{2/(c-2)}\sum_{k=1}^{f}\left(\frac{1}{2}\right)^k < 8 \cdot 4^{2/(c-2)},\]

et la suite \(a(n)\) est bornée. \(\blacksquare\)

Solution 2

Lemme 2. Supposons que \(s_1, \ldots, s_k\) soient des entiers strictement positifs tels que

\[\sum_{i=1}^{k} 2^{-s_i} \leq 1.\]

Alors, pour des entiers strictement positifs quelconques \(n_1, \ldots, n_k\), on a

\[a\left(\sum_{i=1}^{k} n_i\right) \leq \sum_{i=1}^{k} 2^{s_i}a(n_i).\]

Preuve. Récurrence sur \(k\). Les cas de base sont \(k = 1\) (trivial) et \(k = 2\) (qui découle de la condition (1)). Supposons \(k > 2\). On peut supposer \(s_1 \leq s_2 \leq \cdots \leq s_k\). Remarquons que

\[\sum_{i=1}^{k-1} 2^{-s_i} \leq 1 - 2^{-s_{k-1}},\]

puisque le membre de gauche est une fraction de dénominateur \(2^{s_{k-1}}\), et que cette fraction est inférieure à \(1\). Posons \(s'_{k-1} = s_{k-1} - 1\) et \(n'_{k-1} = n_{k-1} + n_k\) ; on a alors

\[\sum_{i=1}^{k-2} 2^{-s_i} + 2^{-s'_{k-1}} \leq (1 - 2 \cdot 2^{-s_{k-1}}) + 2^{1-s_{k-1}} = 1.\]

On peut alors appliquer l'hypothèse de récurrence pour obtenir

\[\begin{aligned} a\left(\sum_{i=1}^{k} n_i\right) = a\left(\sum_{i=1}^{k-2} n_i + n'_{k-1}\right) &\leq \sum_{i=1}^{k-2} 2^{s_i}a(n_i) + 2^{s'_{k-1}}a(n'_{k-1}) \\ &\leq \sum_{i=1}^{k-2} 2^{s_i}a(n_i) + 2^{s_{k-1}-1} \cdot 2\big(a(n_{k-1}) + a(n_k)\big) \\ &\leq \sum_{i=1}^{k-2} 2^{s_i}a(n_i) + 2^{s_{k-1}}a(n_{k-1}) + 2^{s_k}a(n_k). \qquad \square \end{aligned}\]

Posons \(q = c/2 > 1\). Prenons un entier \(n > 0\) quelconque et écrivons

\[n = \sum_{i=1}^{k} 2^{u_i}, \qquad 0 \leq u_1 < u_2 < \cdots < u_k.\]

Choisissons \(s_i = \lfloor \log_2(u_i + 1)^q \rfloor + d\) (\(i = 1, \ldots, k\)) pour un certain entier \(d\). On a

\[\sum_{i=1}^{k} 2^{-s_i} = 2^{-d}\sum_{i=1}^{k} 2^{-\lfloor \log_2(u_i + 1)^q \rfloor},\]

et l'on choisit \(d\) de sorte que

\[\frac{1}{2} < \sum_{i=1}^{k} 2^{-s_i} \leq 1.\]

Cela implique en particulier

\[2^d < 2\sum_{i=1}^{k} 2^{-\lfloor \log_2(u_i + 1)^q \rfloor} < 4\sum_{i=1}^{k}\frac{1}{(u_i + 1)^q}.\]

Maintenant, d'après le lemme 2, on obtient

\[a(n) = a\left(\sum_{i=1}^{k} 2^{u_i}\right) \leq \sum_{i=1}^{k} 2^{s_i}a(2^{u_i}) \leq \sum_{i=1}^{k} 2^d(u_i + 1)^q \cdot \frac{1}{(u_i + 1)^{2q}} = 2^d\sum_{i=1}^{k}\frac{1}{(u_i + 1)^q} < 4\left(\sum_{i=1}^{k}\frac{1}{(u_i + 1)^q}\right)^2,\]

ce qui est borné puisque \(q > 1\). \(\blacksquare\)

Remarques

Remarque 1. En fait, le lemme 2 (appliqué au cas \(n_i = 2^{u_i}\) seulement) donne une borne optimale pour tout \(a(n)\). En effet, posons \(b(k) = \frac{1}{(k + 1)^c}\) et considérons la suite

\[a(n) = \min\left\{\sum_{i=1}^{k} 2^{s_i}b(u_i) \;\middle|\; k \in \mathbb{N}, \ \sum_{i=1}^{k} 2^{-s_i} \leq 1, \ \sum_{i=1}^{k} 2^{u_i} = n\right\}. \tag{5}\]

Montrons que cette suite vérifie les conditions du problème. Prenons deux indices quelconques \(m\) et \(n\). Soient

\[a(m) = \sum_{i=1}^{k} 2^{s_i}b(u_i), \quad \sum_{i=1}^{k} 2^{-s_i} \leq 1, \quad \sum_{i=1}^{k} 2^{u_i} = m ; \qquad a(n) = \sum_{i=1}^{l} 2^{r_i}b(w_i), \quad \sum_{i=1}^{l} 2^{-r_i} \leq 1, \quad \sum_{i=1}^{l} 2^{w_i} = n.\]

On a alors

\[\sum_{i=1}^{k} 2^{-1-s_i} + \sum_{i=1}^{l} 2^{-1-r_i} \leq \frac{1}{2} + \frac{1}{2} = 1, \qquad \sum_{i=1}^{k} 2^{u_i} + \sum_{i=1}^{l} 2^{w_i} = m + n,\]

donc, d'après (5),

\[a(n + m) \leq \sum_{i=1}^{k} 2^{1+s_i}b(u_i) + \sum_{i=1}^{l} 2^{1+r_i}b(w_i) = 2a(m) + 2a(n).\]

Remarque 2. La condition \(c > 2\) est optimale ; montrons que la suite (5) n'est pas bornée si \(c \leq 2\).

Prouvons d'abord que, pour \(n\) quelconque, le minimum dans (5) est atteint par une suite \((u_i)\) formée de nombres distincts. Supposons au contraire que \(u_{k-1} = u_k\). Remplaçons \(u_{k-1}\) et \(u_k\) par un seul nombre \(u'_{k-1} = u_k + 1\), et \(s_{k-1}\) et \(s_k\) par \(s'_{k-1} = \min\{s_{k-1}, s_k\}\). Les suites modifiées donnent une meilleure borne, puisque

\[2^{s'_{k-1}}b(u'_{k-1}) = 2^{s'_{k-1}}b(u_k + 1) < 2^{s_{k-1}}b(u_{k-1}) + 2^{s_k}b(u_k)\]

(on a utilisé que \(b(k)\) est décroissante). C'est impossible.

L'affirmation est donc prouvée, et l'on peut supposer que le minimum est atteint avec \(u_1 < \cdots < u_k\) ; alors

\[n = \sum_{i=1}^{k} 2^{u_i}\]

est simplement l'écriture binaire de \(n\). (En particulier, il s'ensuit que \(a(2^n) = b(n)\) pour tout \(n\).)

Montrons maintenant que la suite \((a(2^k - 1))\) n'est pas bornée. Pour certains \(s_1, \ldots, s_k\), on a

\[a(2^k - 1) = a\left(\sum_{i=1}^{k} 2^{i-1}\right) = \sum_{i=1}^{k} 2^{s_i}b(i - 1) = \sum_{i=1}^{k}\frac{2^{s_i}}{i^c}.\]

Par l'inégalité de Cauchy-Schwarz, on obtient

\[a(2^k - 1) = a(2^k - 1) \cdot 1 \geq \left(\sum_{i=1}^{k}\frac{2^{s_i}}{i^c}\right)\left(\sum_{i=1}^{k}\frac{1}{2^{s_i}}\right) \geq \left(\sum_{i=1}^{k}\frac{1}{i^{c/2}}\right)^2,\]

qui n'est pas borné.

Pour \(c \leq 2\), on peut aussi exhiber un contre-exemple concret. En effet, on peut prouver que la suite

\[a\left(\sum_{i=1}^{k} 2^{u_i}\right) = \sum_{i=1}^{k}\frac{i}{(u_i + 1)^2} \qquad (0 \leq u_1 < \cdots < u_k)\]

vérifie (1) et (2) mais n'est pas bornée.