Aller au contenu

Shortlist 2017, A7

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

Concepts : Suites et récurrences · Principe extrémal

Solution officielle : Shortlist officielle 2017 (avec solutions), p. 27 (page 29 du PDF)

Pas encore relu

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

Énoncé

Let \(a_0, a_1, a_2, \ldots\) be a sequence of integers and \(b_0, b_1, b_2, \ldots\) be a sequence of positive integers such that \(a_0 = 0\), \(a_1 = 1\), and

\[a_{n+1} = \begin{cases} a_n b_n + a_{n-1}, & \text{if } b_{n-1} = 1, \\ a_n b_n - a_{n-1}, & \text{if } b_{n-1} > 1, \end{cases}\]

for \(n = 1, 2, \ldots\). Prove that at least one of the two numbers \(a_{2017}\) and \(a_{2018}\) must be greater than or equal to \(2017\).

Indices : les idées clés
  • Suites et récurrences : on montre d'abord que tous les \(a_n\) (\(n \geq 1\)) sont strictement positifs, puis on suit la croissance de la suite selon les valeurs des \(b_n\).
  • Principe extrémal (solution 1) : on considère le plus petit \(n\) avec \(a_n \leq 0\), puis le plus petit \(r\) avec \(a_r \geq a_{r+1} \geq a_{r+2}\).
  • Une fois que la suite croît, elle continue tant que \(b \geq 2\) : \(a_{m+1} = a_mb_m - a_{m-1} \geq a_m + (a_m - a_{m-1})\).
  • Indices « mauvais » (solution 2) : on isole les indices où la suite peut ne pas croître et on montre qu'elle rattrape son retard en au plus trois pas.
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2017 (deux solutions).

Solution 1

La valeur de \(b_0\) ne joue aucun rôle car \(a_0 = 0\) ; on peut donc supposer \(b_0 = 1\).

Lemme. \(a_n \geq 1\) pour tout \(n \geq 1\).

Preuve. Supposons le contraire. Par le principe extrémal, soit

\[n \geq 1 \text{ le plus petit entier tel que } a_n \leq 0. \tag{1}\]

On a \(n \geq 2\). Donc \(a_{n-1} \geq 1\) et \(a_{n-2} \geq 0\). On ne peut donc pas avoir \(a_n = a_{n-1}b_{n-1} + a_{n-2}\) ; ainsi \(a_n = a_{n-1}b_{n-1} - a_{n-2}\). Comme \(a_n \leq 0\), on a \(a_{n-1} \leq a_{n-2}\). Donc \(a_{n-2} \geq a_{n-1} \geq a_n\). Soit alors

\[r \text{ le plus petit indice tel que } a_r \geq a_{r+1} \geq a_{r+2}. \tag{2}\]

D'après ce qui précède, \(r \leq n - 2\) ; mais aussi \(r \geq 2\) : si \(b_1 = 1\), alors \(a_2 = a_1 = 1\) et \(a_3 = a_2b_2 + a_1 > a_2\) ; si \(b_1 > 1\), alors \(a_2 = b_1 > 1 = a_1\) (et \(r = 0\) est exclu car \(a_0 < a_1\)).

Par minimalité de \(r\) dans (2), \(a_{r-1} < a_r\). Comme \(2 \leq r \leq n - 2\), la minimalité de \(n\) dans (1) donne \(a_{r-1}, a_r, a_{r+1} > 0\). Pour avoir \(a_{r+1} \geq a_{r+2}\), il faut \(a_{r+2} = a_{r+1}b_{r+1} - a_r\), donc \(b_r \geq 2\). En rassemblant,

\[a_{r+1} = a_rb_r \pm a_{r-1} \geq 2a_r - a_{r-1} = a_r + (a_r - a_{r-1}) > a_r,\]

ce qui contredit (2). \(\square\)

Montrons par récurrence que \(\max\{a_n, a_{n+1}\} \geq n\) pour tout \(n \geq 0\) (ce qui, pour \(n = 2017\), donne le résultat). Les cas \(n = 0, 1\) sont donnés. Supposons le résultat vrai pour tous les entiers positifs ou nuls strictement inférieurs à \(n\), avec \(n \geq 2\). Deux cas.

Cas 1 : \(b_{n-1} = 1\). Alors \(a_{n+1} = a_nb_n + a_{n-1}\). Par hypothèse de récurrence, l'un des nombres \(a_{n-1}, a_n\) est au moins \(n - 1\), et l'autre est au moins \(1\) d'après le lemme. Donc

\[a_{n+1} = a_nb_n + a_{n-1} \geq a_n + a_{n-1} \geq (n-1) + 1 = n,\]

et \(\max\{a_n, a_{n+1}\} \geq n\).

Cas 2 : \(b_{n-1} > 1\). Comme \(b_0 = 1\), il existe un indice \(r\) avec \(1 \leq r \leq n - 1\) tel que

\[b_{n-1}, b_{n-2}, \ldots, b_r \geq 2 \qquad \text{et} \qquad b_{r-1} = 1.\]

On a \(a_{r+1} = a_rb_r + a_{r-1} \geq 2a_r + a_{r-1}\), donc \(a_{r+1} - a_r \geq a_r + a_{r-1}\).

Montrons que \(a_r + a_{r-1} \geq r\). Pour \(r = 1\), c'est immédiat (\(a_1 + a_0 = 1\)) ; pour \(r \geq 2\), l'un des nombres \(a_r, a_{r-1}\) est au moins \(r - 1\) par hypothèse de récurrence, et l'autre est au moins \(1\) d'après le lemme. Donc \(a_r + a_{r-1} \geq r\), et par conséquent \(a_{r+1} - a_r \geq r\).

Comme \(r \geq 1\) et \(a_r \geq 1\) (lemme), on obtient

\[a_{r+1} \geq r + 1 \qquad \text{et} \qquad a_{r+1} > a_r.\]

Observons maintenant que

\[a_m > a_{m-1} \implies a_{m+1} > a_m \qquad \text{pour } m = r+1, r+2, \ldots, n-1,\]

car \(a_{m+1} = a_mb_m - a_{m-1} \geq 2a_m - a_{m-1} = a_m + (a_m - a_{m-1}) > a_m\). Donc

\[a_n > a_{n-1} > \cdots > a_{r+1} \geq r + 1 \implies a_n \geq n.\]

Ainsi \(\max\{a_n, a_{n+1}\} \geq n\), comme voulu. \(\blacksquare\)

Solution 2

On dit qu'un indice \(n > 1\) est mauvais si \(b_{n-1} = 1\) et \(b_{n-2} > 1\) ; sinon \(n\) est bon. La valeur de \(b_0\) ne joue aucun rôle dans la définition de \((a_n)\) car \(a_0 = 0\) ; on suppose ici \(b_0 > 1\).

Lemme 1. (a) \(a_n \geq 1\) pour tout \(n > 0\). (b) Si \(n > 1\) est bon, alors \(a_n > a_{n-1}\).

Preuve. Par récurrence sur \(n\). Pour \(n = 1, 2\) : \(a_1 = 1 \geq 1\), \(a_2 = b_1a_1 \geq 1\), et enfin \(a_2 > a_1\) si \(2\) est bon, car alors \(b_1 > 1\).

Supposons le lemme démontré pour \(n = 1, 2, \ldots, k\) avec \(k \geq 2\), et montrons-le pour \(n = k + 1\). Rappelons que \(a_k\) et \(a_{k-1}\) sont strictement positifs par hypothèse de récurrence.

Cas 1 : \(k\) est mauvais. Alors \(b_{k-1} = 1\), donc \(a_{k+1} = b_ka_k + a_{k-1} \geq a_k + a_{k-1} > a_k \geq 1\).

Cas 2 : \(k\) est bon. On a déjà \(a_k > a_{k-1} \geq 1\) par hypothèse de récurrence. Trois sous-cas faciles :

  • Sous-cas 2.1 : \(b_k > 1\). Alors \(a_{k+1} \geq b_ka_k - a_{k-1} \geq a_k + (a_k - a_{k-1}) > a_k \geq 1\).
  • Sous-cas 2.2 : \(b_k = b_{k-1} = 1\). Alors \(a_{k+1} = a_k + a_{k-1} > a_k \geq 1\).
  • Sous-cas 2.3 : \(b_k = 1\) mais \(b_{k-1} > 1\). Alors \(k + 1\) est mauvais, et il suffit de prouver (a), ce qui est immédiat : \(a_{k+1} = a_k - a_{k-1} \geq 1\).

Dans les trois sous-cas, les relations voulues sont vérifiées. \(\square\)

Lemme 2. Soit \(n > 1\) un indice mauvais. Alors il existe \(j \in \{1, 2, 3\}\) tel que \(a_{n+j} \geq a_{n-1} + j + 1\), et \(a_{n+i} \geq a_{n-1} + i\) pour tout \(1 \leq i < j\).

Preuve. Rappelons que \(b_{n-1} = 1\). Posons

\[m = \inf\{i > 0 : b_{n+i-1} > 1\}\]

(éventuellement \(m = +\infty\)). Montrons que \(j = \min\{m, 3\}\) convient. On distingue plusieurs cas selon la valeur de \(m\), en utilisant le lemme 1 sans le rappeler.

Cas 1 : \(m = 1\), donc \(b_n > 1\). Alors \(a_{n+1} \geq 2a_n + a_{n-1} \geq a_{n-1} + 2\), comme voulu.

Cas 2 : \(m = 2\), donc \(b_n = 1\) et \(b_{n+1} > 1\). On obtient successivement

\[a_{n+1} = a_n + a_{n-1} \geq a_{n-1} + 1, \qquad a_{n+2} \geq 2a_{n+1} + a_n \geq 2(a_{n-1} + 1) + a_n = a_{n-1} + (a_{n-1} + a_n + 2) \geq a_{n-1} + 4,\]

ce qui est même mieux que nécessaire.

Cas 3 : \(m > 2\), donc \(b_n = b_{n+1} = 1\). On obtient successivement

\[a_{n+1} = a_n + a_{n-1} \geq a_{n-1} + 1, \qquad a_{n+2} = a_{n+1} + a_n \geq a_{n-1} + 1 + a_n \geq a_{n-1} + 2,\]
\[a_{n+3} \geq a_{n+2} + a_{n+1} \geq (a_{n-1} + 1) + (a_{n-1} + 2) \geq a_{n-1} + 4. \qquad \square\]

Conclusion. Les lemmes 1(b) et 2 suffisent pour montrer que \(\max\{a_n, a_{n+1}\} \geq n\) pour tout \(n\), et même que \(a_n \geq n\) assez souvent. En effet, supposons trouvé un \(n\) tel que \(a_{n-1} \geq n - 1\) (au départ, \(a_1 = 1\) et \(n = 2\)). Si \(n\) est bon, le lemme 1(b) donne aussi \(a_n \geq n\), et on recommence avec \(n + 1\). Si \(n\) est mauvais, le lemme 2 donne

\[\max\{a_{n+i}, a_{n+i+1}\} \geq a_{n-1} + i + 1 \geq n + i \quad (0 \leq i < j) \qquad \text{et} \qquad a_{n+j} \geq a_{n-1} + j + 1 \geq n + j,\]

de sorte que l'on peut recommencer à partir de l'indice \(n + j\) (qui joue le rôle de \(n - 1\)). On obtient ainsi \(\max\{a_n, a_{n+1}\} \geq n\) pour tout \(n\), en particulier pour \(n = 2017\). \(\blacksquare\)