Aller au contenu

Shortlist 2008, N3

Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : non indiqué

Concepts : Divisibilité, PGCD et algorithme d'Euclide · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2008 (avec solutions), p. 46 (page 47 du PDF)

Énoncé

Let \(a_0, a_1, a_2, \ldots\) be a sequence of positive integers such that the greatest common divisor of any two consecutive terms is greater than the preceding term; in symbols, \(\gcd(a_i, a_{i+1}) > a_{i-1}\). Prove that \(a_n \geq 2^n\) for all \(n \geq 0\).

Indices : les idées clés
  • Croissance : \(a_{i+1} - a_i \geq \gcd(a_i, a_{i+1}) > a_{i-1}\) ; les cas de base \(n \leq 3\) se vérifient à la main (\(a_3 = 7\) est impossible).
  • Récurrence : avec \(d = \gcd(a_n, a_{n+1}) > a_{n-1}\), le seul cas difficile est \(a_n = 2d\), \(a_{n+1} = 3d\).
  • Descente sur les pgcd : on écrit \(a_n = md'\) avec \(d' = \gcd(a_{n-1}, a_n)\) ; seul \(m = 5\) résiste, et le même raisonnement un cran plus bas clôt tous les cas.
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2008 (une solution).

Solution

Comme \(a_i \geq \gcd(a_i, a_{i+1}) > a_{i-1}\), la suite est strictement croissante. En particulier, \(a_0 \geq 1\), \(a_1 \geq 2\). Pour tout \(i \geq 1\), on a aussi \(a_{i+1} - a_i \geq \gcd(a_i, a_{i+1}) > a_{i-1}\), et par conséquent \(a_{i+1} \geq a_i + a_{i-1} + 1\). Donc \(a_2 \geq 4\) et \(a_3 \geq 7\). L'égalité \(a_3 = 7\) forcerait l'égalité dans les estimations précédentes, ce qui mènerait à \(\gcd(a_2, a_3) = \gcd(4, 7) > a_1 = 2\), ce qui est faux. Donc \(a_3 \geq 8\) ; le résultat est vrai pour \(n = 0, 1, 2, 3\). Ce sont les cas de base d'une preuve par récurrence.

Prenons \(n \geq 3\) et supposons \(a_i \geq 2^i\) pour \(i = 0, 1, \ldots, n\). Il faut montrer que \(a_{n+1} \geq 2^{n+1}\). Posons \(\gcd(a_n, a_{n+1}) = d\). On sait que \(d > a_{n-1}\). L'hérédité est immédiate dans les cas suivants :

\[\begin{aligned} &\text{si } a_{n+1} \geq 4d, & &\text{alors } a_{n+1} > 4a_{n-1} \geq 4 \cdot 2^{n-1} = 2^{n+1} ; \\ &\text{si } a_n \geq 3d, & &\text{alors } a_{n+1} \geq a_n + d \geq 4d > 4a_{n-1} \geq 4 \cdot 2^{n-1} = 2^{n+1} ; \\ &\text{si } a_n = d, & &\text{alors } a_{n+1} \geq a_n + d = 2a_n \geq 2 \cdot 2^n = 2^{n+1}. \end{aligned}\]

La seule possibilité restante est \(a_n = 2d\) et \(a_{n+1} = 3d\), ce qu'on suppose dans la suite. Donc \(a_{n+1} = \frac{3}{2}a_n\).

Posons maintenant \(\gcd(a_{n-1}, a_n) = d'\) ; alors \(d' > a_{n-2}\). Écrivons \(a_n = md'\) (\(m\) entier). En se rappelant que \(d' \leq a_{n-1} < d\) et \(a_n = 2d\), on obtient \(m \geq 3\). De plus, \(a_{n-1} < d = \frac{1}{2}md'\), \(a_{n+1} = \frac{3}{2}md'\). On isole de nouveau les cas qui donnent immédiatement l'hérédité :

\[\begin{aligned} &\text{si } m \geq 6, & &\text{alors } a_{n+1} = \tfrac{3}{2}md' \geq 9d' > 9a_{n-2} \geq 9 \cdot 2^{n-2} > 2^{n+1} ; \\ &\text{si } 3 \leq m \leq 4, & &\text{alors } a_{n-1} < \tfrac{1}{2} \cdot 4d', \text{ donc } a_{n-1} = d', \text{ et } a_{n+1} = \tfrac{3}{2}ma_{n-1} \geq \tfrac{3}{2} \cdot 3a_{n-1} \geq \tfrac{9}{2} \cdot 2^{n-1} > 2^{n+1}. \end{aligned}\]

Il reste le cas \(m = 5\), ce qui signifie que \(a_n = 5d'\), \(a_{n+1} = \frac{15}{2}d'\), \(a_{n-1} < d = \frac{5}{2}d'\). La dernière relation implique que \(a_{n-1}\) vaut \(d'\) ou \(2d'\). Dans les deux cas, \(a_{n-1} \mid 2d'\).

Le même schéma se répète encore une fois. Notons \(\gcd(a_{n-2}, a_{n-1}) = d''\) ; alors \(d'' > a_{n-3}\). Comme \(d''\) est un diviseur de \(a_{n-1}\), donc aussi de \(2d'\), on peut écrire \(2d' = m'd''\) (\(m'\) entier). Comme \(d'' \leq a_{n-2} < d'\), on obtient \(m' \geq 3\). De plus, \(a_{n-2} < d' = \frac{1}{2}m'd''\), \(a_{n+1} = \frac{15}{2}d' = \frac{15}{4}m'd''\). Comme précédemment, on considère les cas :

\[\begin{aligned} &\text{si } m' \geq 5, & &\text{alors } a_{n+1} = \tfrac{15}{4}m'd'' \geq \tfrac{75}{4}d'' > \tfrac{75}{4}a_{n-3} \geq \tfrac{75}{4} \cdot 2^{n-3} > 2^{n+1} ; \\ &\text{si } 3 \leq m' \leq 4, & &\text{alors } a_{n-2} < \tfrac{1}{2} \cdot 4d'', \text{ donc } a_{n-2} = d'', \text{ et } a_{n+1} = \tfrac{15}{4}m'a_{n-2} \geq \tfrac{15}{4} \cdot 3a_{n-2} \geq \tfrac{45}{4} \cdot 2^{n-2} > 2^{n+1}. \end{aligned}\]

Les deux cas donnent l'hérédité. Mais il ne reste maintenant aucun cas. La récurrence est complète ; l'inégalité \(a_n \geq 2^n\) est vraie pour tout \(n\). \(\blacksquare\)