Shortlist 2010, A4¶
Domaine : Algèbre · Difficulté : ★★☆☆☆ · Proposé par : Austria
Concepts : Suites et récurrences · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2010 (avec solutions), p. 11 (page 12 du PDF)
Énoncé¶
A sequence \(x_1, x_2, \ldots\) is defined by \(x_1 = 1\) and \(x_{2k} = -x_k\), \(x_{2k-1} = (-1)^{k+1}x_k\) for all \(k \geq 1\). Prove that \(x_1 + x_2 + \cdots + x_n \geq 0\) for all \(n \geq 1\).
Indices : les idées clés
- Relations de récurrence : \(x_{4k-3} = -x_{4k-2}\) et \(x_{4k-1} = x_{4k} = x_k\), d'où \(S_{4k} = 2S_k\) et \(S_{4k+2} = S_{4k}\).
- Parité : \(S_n \equiv n \pmod 2\) ; pour \(k\) impair, \(S_{4k} \geq 2\), donc \(S_{4k+1} \geq 1\).
- Récurrence forte sur \(k\) : on montre \(S_i \geq 0\) pour \(i \leq 4k\) ; ou bien (solution 2) on décrit l'ensemble \(M = \{n : S_n = 0\}\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2010 (deux solutions et une remarque).
Solution 1¶
Commençons par quelques observations. D'abord, la définition des \(x_i\) donne, pour tout entier \(k > 0\),
Donc, en notant \(S_n = \sum_{i=1}^{n} x_i\), on a
Remarquons aussi que \(S_n = \sum_{i=1}^{n} x_i \equiv \sum_{i=1}^{n} 1 = n \pmod 2\).
Montrons maintenant par récurrence sur \(k\) que \(S_i \geq 0\) pour tout \(i \leq 4k\). Le cas de base est vrai puisque \(x_1 = x_3 = x_4 = 1\), \(x_2 = -1\). Pour l'hérédité, supposons \(S_i \geq 0\) pour tout \(i \leq 4k\). Avec les relations (1)–(3), on obtient
Il reste donc à prouver que \(S_{4k+1} \geq 0\). Si \(k\) est impair, alors \(S_{4k} = 2S_k \geq 0\) ; comme \(k\) est impair, \(S_k\) l'est aussi, donc \(S_{4k} \geq 2\) et par conséquent \(S_{4k+1} = S_{4k} + x_{4k+1} \geq 1\).
Inversement, si \(k\) est pair, alors \(x_{4k+1} = x_{2k+1} = x_{k+1}\), donc \(S_{4k+1} = S_{4k} + x_{4k+1} = 2S_k + x_{k+1} = S_k + S_{k+1} \geq 0\). L'hérédité est établie. \(\blacksquare\)
Solution 2¶
On utilise la notation \(S_n\) et les relations (1)–(3) de la solution précédente.
Supposons le contraire et considérons le plus petit \(n\) tel que \(S_{n+1} < 0\) ; on a sûrement \(n \geq 1\), et de \(S_n \geq 0\) on tire \(S_n = 0\), \(x_{n+1} = -1\). On s'intéresse donc particulièrement à l'ensemble \(M = \{n : S_n = 0\}\) ; notre but est de prouver que \(x_{n+1} = 1\) dès que \(n \in M\), ce qui donnera une contradiction.
Pour cela, décrivons d'abord l'ensemble \(M\) par récurrence. Montrons que (i) \(M\) ne contient que des nombres pairs, (ii) \(2 \in M\), et (iii) pour tout nombre pair \(n \geq 4\), on a \(n \in M \iff \lfloor n/4 \rfloor \in M\). En effet, (i) vient de \(S_n \equiv n \pmod 2\), (ii) est immédiat, et (iii) découle des relations \(S_{4k+2} = S_{4k} = 2S_k\).
Il reste à prouver que \(x_{n+1} = 1\) si \(n \in M\). On procède par récurrence sur \(n\). Le cas de base est \(n = 2\), le plus petit élément de \(M\) ; on a bien \(x_3 = 1\).
Pour l'hérédité, considérons un \(n \in M\) avec \(n \geq 4\), et posons \(m = \lfloor n/4 \rfloor \in M\) ; alors \(m\) est pair, et \(x_{m+1} = 1\) par hypothèse de récurrence. Montrons que \(x_{n+1} = x_{m+1} = 1\). Si \(n = 4m\), alors \(x_{n+1} = x_{2m+1} = x_{m+1}\) puisque \(m\) est pair ; sinon, \(n = 4m + 2\), et \(x_{n+1} = -x_{2m+2} = x_{m+1}\), comme voulu. La preuve est complète. \(\blacksquare\)
Remarque¶
En utilisant la définition récursive de l'ensemble \(M\), on peut le décrire explicitement : \(M\) est formé exactement des entiers strictement positifs dont l'écriture en base \(4\) ne contient pas les chiffres \(1\) et \(3\).