Shortlist 2006, A3¶
Domaine : Algèbre · Difficulté : ★★★☆☆ · Proposé par : Russia
Concepts : Suites et récurrences · Principe extrémal
Solution officielle : Shortlist officielle 2006 (avec solutions), p. 10 (page 11 du PDF)
Énoncé¶
La suite \(c_0, c_1, \ldots, c_n, \ldots\) est définie par \(c_0 = 1\), \(c_1 = 0\) et \(c_{n+2} = c_{n+1} + c_n\) pour \(n \geq 0\). On considère l'ensemble \(S\) des couples ordonnés \((x, y)\) pour lesquels il existe un ensemble fini \(J\) d'entiers strictement positifs tel que \(x = \sum_{j \in J} c_j\) et \(y = \sum_{j \in J} c_{j-1}\). Montrer qu'il existe des nombres réels \(\alpha\), \(\beta\) et \(m\), \(M\) ayant la propriété suivante : un couple ordonné \((x, y)\) d'entiers positifs ou nuls vérifie l'inégalité
si et seulement si \((x, y) \in S\).
N. B. Une somme portant sur les éléments de l'ensemble vide est égale à \(0\).
Énoncé original (anglais)
The sequence \(c_0, c_1, \ldots, c_n, \ldots\) is defined by \(c_0 = 1\), \(c_1 = 0\) and \(c_{n+2} = c_{n+1} + c_n\) for \(n \geq 0\). Consider the set \(S\) of ordered pairs \((x, y)\) for which there is a finite set \(J\) of positive integers such that \(x = \sum_{j \in J} c_j\), \(y = \sum_{j \in J} c_{j-1}\). Prove that there exist real numbers \(\alpha\), \(\beta\) and \(m\), \(M\) with the following property: An ordered pair of nonnegative integers \((x, y)\) satisfies the inequality
if and only if \((x, y) \in S\).
N. B. A sum over the elements of the empty set is assumed to be \(0\).
Indices : les idées clés
- Formule de Binet : \(c_n = \frac{\varphi^{n-1} - \psi^{n-1}}{\varphi - \psi}\) ; pour que \(\alpha c_n + \beta c_{n-1}\) reste borné, il faut \(\alpha\varphi + \beta = 0\), d'où le choix \(\alpha = \psi\), \(\beta = 1\) (suites récurrentes).
- Somme de puissances distinctes : \(\psi a_J + b_J = \sum_{j \in J}\psi^{j-1}\), qui est strictement compris entre \(-1\) et \(\varphi\) ; donc \(m = -1\), \(M = \varphi\).
- Réciproque : une représentation \(\psi x + y = \sum \psi^{i_r}\) de longueur minimale a des exposants distincts (grâce à \(2\psi^2 = 1 + \psi^3\) et \(1 + \psi = \psi^2\)) ; l'irrationalité de \(\psi\) identifie \((x, y)\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2006 (une solution et une remarque).
Solution¶
Soient \(\varphi = (1 + \sqrt{5})/2\) et \(\psi = (1 - \sqrt{5})/2\) les racines de l'équation \(t^2 - t - 1 = 0\). On a donc \(\varphi\psi = -1\), \(\varphi + \psi = 1\) et \(1 + \psi = \psi^2\). Une récurrence facile montre que le terme général \(c_n\) de la suite donnée vérifie
Supposons que les nombres \(\alpha\) et \(\beta\) aient la propriété voulue, pour des \(m\) et \(M\) convenables. Comme \((c_n, c_{n-1}) \in S\) pour tout \(n\), l'expression
est bornée quand \(n\) tend vers l'infini. Comme \(\varphi > 1\) et \(-1 < \psi < 0\), cela implique \(\alpha\varphi + \beta = 0\).
Pour réaliser \(\alpha\varphi + \beta = 0\), on peut prendre par exemple \(\alpha = \psi\), \(\beta = 1\). Trouvons maintenant \(m\) et \(M\) convenables pour ce choix de \(\alpha\) et \(\beta\).
Remarquons d'abord que l'égalité ci-dessus donne \(c_n\psi + c_{n-1} = \psi^{n-1}\), \(n \geq 1\). Dans la suite, on note les couples de \(S\) sous la forme \((a_J, b_J)\), où \(J\) est une partie finie de l'ensemble \(\mathbb{N}\) des entiers strictement positifs, et \(a_J = \sum_{j \in J} c_j\), \(b_J = \sum_{j \in J} c_{j-1}\). Comme \(\psi a_J + b_J = \sum_{j \in J}(c_j\psi + c_{j-1})\), on obtient
D'autre part, vu \(-1 < \psi < 0\),
Donc, d'après (1),
Ainsi, \(m = -1\) et \(M = \varphi\) est un choix convenable.
Réciproquement, montrons que si un couple d'entiers positifs ou nuls \((x, y)\) vérifie l'inégalité \(-1 < \psi x + y < \varphi\), alors \((x, y) \in S\).
Lemme. Soient \(x\), \(y\) des entiers positifs ou nuls tels que \(-1 < \psi x + y < \varphi\). Il existe alors une partie \(J\) de \(\mathbb{N}\) telle que
Preuve. Pour \(x = y = 0\), il suffit de prendre pour \(J\) la partie vide de \(\mathbb{N}\) ; supposons donc que l'un au moins de \(x\), \(y\) est non nul. Il existe des représentations de \(\psi x + y\) de la forme
où \(i_1 \leq \cdots \leq i_k\) est une suite d'entiers positifs ou nuls, pas forcément distincts. Par exemple, on peut prendre \(x\) termes \(\psi^1 = \psi\) et \(y\) termes \(\psi^0 = 1\). Considérons toutes les représentations de ce type de longueur \(k\) minimale, et parmi elles celles pour lesquelles \(i_1\) a la plus petite valeur possible \(j_1\). Parmi celles-ci, considérons les représentations où \(i_2\) a la plus petite valeur possible \(j_2\). En choisissant de même \(j_3, \ldots, j_k\), on obtient une suite \(j_1 \leq \cdots \leq j_k\) qui vérifie évidemment \(\psi x + y = \sum_{r=1}^{k}\psi^{j_r}\). Pour prouver le lemme, il suffit de montrer que \(j_1, \ldots, j_k\) sont deux à deux distincts.
Supposons au contraire que \(j_r = j_{r+1}\) pour un certain \(r = 1, \ldots, k - 1\). Considérons d'abord le cas \(j_r \geq 2\). Comme \(2\psi^2 = 1 + \psi^3\), remplaçons \(j_r\) et \(j_{r+1}\) par \(j_r - 2\) et \(j_r + 1\) respectivement. Comme
la nouvelle suite représente aussi \(\psi x + y\) comme voulu, et la valeur de \(i_r\) qu'elle donne contredit le choix minimal de \(j_r\).
Soit \(j_r = j_{r+1} = 0\). Alors la somme \(\psi x + y = \sum_{r=1}^{k}\psi^{j_r}\) contient au moins deux termes égaux à \(\psi^0 = 1\). D'autre part, \(j_s \neq 1\) pour tout \(s\), car l'égalité \(1 + \psi = \psi^2\) implique qu'une représentation de longueur minimale ne peut pas contenir des \(i_r\) consécutifs. Il s'ensuit que
ce qui contredit la condition du lemme.
Soit \(j_r = j_{r+1} = 1\) ; alors \(\sum_{r=1}^{k}\psi^{j_r}\) contient au moins deux termes égaux à \(\psi^1 = \psi\). Comme dans le cas \(j_r = j_{r+1} = 0\), on en déduit aussi que \(j_s \neq 0\) et \(j_s \neq 2\) pour tout \(s\). Donc
ce qui est de nouveau une contradiction. La conclusion en découle. \(\square\)
Soit maintenant un couple \((x, y)\) vérifiant \(-1 < \psi x + y < \varphi\) ; le lemme s'applique donc à \((x, y)\). Soit \(J \subset \mathbb{N}\) tel que (2) soit vrai. En comparant (1) et (2), on conclut que \(\psi x + y = \psi a_J + b_J\). Or \(x\), \(y\), \(a_J\) et \(b_J\) sont entiers, et \(\psi\) est irrationnel. La dernière égalité implique donc \(x = a_J\) et \(y = b_J\). Cela montre que les nombres \(\alpha = \psi\), \(\beta = 1\), \(m = -1\), \(M = \varphi\) conviennent. \(\blacksquare\)
Remarque¶
Voici une autre façon de prouver le lemme, en construisant l'ensemble \(J\) par récurrence. Pour \(x = y = 0\), on choisit \(J = \varnothing\). On procède par récurrence sur \(n = 3x + 2y\). Supposons qu'un ensemble \(J\) convenable existe quand \(3x + 2y < n\), et supposons maintenant \(3x + 2y = n > 0\). L'ensemble \(J\) cherché doit être
Ces ensembles conviennent si
respectivement ; il suffit donc de trouver un ensemble convenable pour \(\frac{\psi x + y}{\psi}\) ou pour \(\frac{\psi x + y - 1}{\psi}\) respectivement.
Considérons \(\frac{\psi x + y}{\psi}\). Sachant que
posons \(x' = y\), \(y' = x - y\) et testons l'hypothèse de récurrence sur ces nombres. On demande \(\frac{\psi x + y}{\psi} \in (-1, \varphi)\), ce qui équivaut à
La relation (3) implique \(y' = x - y \geq -\psi x - y > \psi > -1\) ; donc \(x', y' \geq 0\). De plus, \(3x' + 2y' = 2x + y \leq \frac{2}{3}n\) ; donc, si (3) est vraie, la récurrence s'applique : les nombres \(x'\), \(y'\) se représentent sous la forme voulue, donc \(x\), \(y\) aussi.
Considérons maintenant \(\frac{\psi x + y - 1}{\psi}\). Comme
posons \(x' = y - 1\) et \(y' = x - y + 1\). On demande de nouveau \(\frac{\psi x + y - 1}{\psi} \in (-1, \varphi)\), c'est-à-dire
Si (4) est vraie, alors \(y - 1 \geq \psi x + y - 1 > -1\) et \(x - y + 1 \geq -\psi x - y + 1 > -\varphi + 1 > -1\), donc \(x', y' \geq 0\). De plus, \(3x' + 2y' = 2x + y - 1 < \frac{2}{3}n\), et la récurrence fonctionne.
Enfin, \((-1, -\psi) \cup (0, \varphi) = (-1, \varphi)\), donc l'une au moins des relations (3) et (4) est vraie, et l'hérédité est justifiée.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2017 A4 ★★☆☆☆ : Une suite définie par \(a_n = -\max_{i+j=n}(a_i + a_j)\) au-delà d'un certain rang est bornée.
- 2023 N5 ★★★☆☆ : Une suite croissante dont chaque terme divise le double de la somme des précédents : si elle fait intervenir une infinité de premiers, tout entier divise l'un de ses termes.
- 2009 A6 ★★★☆☆ · OIM P3 : Si deux sous-suites extraites d'une suite croissante sont arithmétiques, la suite elle-même l'est.
- 2017 A7 ★★★★☆ : Une récurrence dont le signe dépend de \(b_{n-1}\) : l'un des termes \(a_{2017}\), \(a_{2018}\) vaut au moins \(2017\).