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é

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

\[m < \alpha x + \beta y < M\]

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

\[c_n = \frac{\varphi^{n-1} - \psi^{n-1}}{\varphi - \psi} \qquad \text{pour } n \geq 0.\]

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

\[\alpha c_n + \beta c_{n-1} = \frac{\alpha}{\sqrt{5}}(\varphi^{n-1} - \psi^{n-1}) + \frac{\beta}{\sqrt{5}}(\varphi^{n-2} - \psi^{n-2}) = \frac{1}{\sqrt{5}}\left((\alpha\varphi + \beta)\varphi^{n-2} - (\alpha\psi + \beta)\psi^{n-2}\right)\]

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

\[\psi a_J + b_J = \sum_{j \in J}\psi^{j-1} \qquad \text{pour tout } (a_J, b_J) \in S. \tag{1}\]

D'autre part, vu \(-1 < \psi < 0\),

\[-1 = \frac{\psi}{1 - \psi^2} = \sum_{j=0}^{\infty}\psi^{2j+1} < \sum_{j \in J}\psi^{j-1} < \sum_{j=0}^{\infty}\psi^{2j} = \frac{1}{1 - \psi^2} = 1 - \psi = \varphi.\]

Donc, d'après (1),

\[-1 < \psi a_J + b_J < \varphi \qquad \text{pour tout } (a_J, b_J) \in S.\]

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

\[\psi x + y = \sum_{j \in J}\psi^{j-1}. \tag{2}\]

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

\[\psi x + y = \psi^{i_1} + \cdots + \psi^{i_k},\]

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

\[\psi^{j_r} + \psi^{j_{r+1}} = 2\psi^{j_r} = \psi^{j_r - 2}(1 + \psi^3) = \psi^{j_r - 2} + \psi^{j_r + 1},\]

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

\[\psi x + y = \sum_{r=1}^{k}\psi^{j_r} > 2 + \psi^3 + \psi^5 + \psi^7 + \cdots = 2 - \psi^2 = \varphi,\]

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

\[\psi x + y = \sum_{r=1}^{k}\psi^{j_r} < 2\psi + \psi^4 + \psi^6 + \psi^8 + \cdots = 2\psi - \psi^3 = -1,\]

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

\[\text{soit} \quad 1 \leq j_1 < j_2 < \cdots < j_k \qquad \text{soit} \quad j_1 = 0, \ 1 \leq j_2 < \cdots < j_k.\]

Ces ensembles conviennent si

\[\frac{\psi x + y}{\psi} = \psi^{i_1 - 1} + \cdots + \psi^{i_k - 1} \qquad \text{ou} \qquad \frac{\psi x + y - 1}{\psi} = \psi^{i_2 - 1} + \cdots + \psi^{i_k - 1}\]

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

\[\frac{\psi x + y}{\psi} = x + (\psi - 1)y = \psi y + (x - y),\]

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 à

\[\psi x + y \in (\varphi \cdot \psi, (-1) \cdot \psi) = (-1, -\psi). \tag{3}\]

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

\[\frac{\psi x + y - 1}{\psi} = x + (\psi - 1)(y - 1) = \psi(y - 1) + (x - y + 1),\]

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

\[\psi x + y \in (\varphi \cdot \psi + 1, (-1) \cdot \psi + 1) = (0, \varphi). \tag{4}\]

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.