Shortlist 2013, A1

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

Concepts : Suites et récurrences · Bijections et dénombrement · Polynômes : racines, relations de Viète, factorisation

Solution officielle : Shortlist officielle 2013 (avec solutions), p. 8 (page 8 du PDF)

Énoncé

Let \(n\) be a positive integer and let \(a_1, \ldots, a_{n-1}\) be arbitrary real numbers. Define the sequences \(u_0, \ldots, u_n\) and \(v_0, \ldots, v_n\) inductively by \(u_0 = u_1 = v_0 = v_1 = 1\), and

\[u_{k+1} = u_k + a_k u_{k-1}, \qquad v_{k+1} = v_k + a_{n-k} v_{k-1} \qquad \text{for } k = 1, \ldots, n - 1.\]

Prove that \(u_n = v_n\).

Indices : les idées clés

• Formule explicite (solution 1) : \(u_k\) est la somme des produits \(a_{i_1} \cdots a_{i_t}\) sur les ensembles d'indices de \(\{1, \ldots, k - 1\}\) sans deux indices consécutifs ; cette description est symétrique quand on renverse l'ordre des \(a_i\).
• Récurrence sur des polynômes à plusieurs variables (solution 2) : \(P_n(x_1, \ldots, x_{n-1}) = P_n(x_{n-1}, \ldots, x_1)\), en développant par les deux bouts.
• Matrices (solution 3) : \(u_n\) et \(v_n\) sont le même coefficient du produit \(A_{n-1} \cdots A_1\), lu une fois à droite et une fois à gauche.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2013 (trois solutions et trois remarques).

Solution 1

Montrons par récurrence sur \(k\) que

\[u_k = \sum_{\substack{0 < i_1 < \cdots < i_t < k \\ i_{j+1} - i_j \geq 2}} a_{i_1} \cdots a_{i_t}. \tag{1}\]

La somme contient un terme trivial égal à \(1\) (qui correspond à \(t = 0\) et à la suite vide, dont le produit vaut \(1\)).

Pour \(k = 0, 1\), la somme du membre de droite ne contient que le produit vide, donc (1) est vraie car \(u_0 = u_1 = 1\). Pour \(k \geq 1\), en supposant le résultat vrai pour \(0, 1, \ldots, k\), on a

\[\begin{aligned} u_{k+1} &= \sum_{\substack{0 < i_1 < \cdots < i_t < k \\ i_{j+1} - i_j \geq 2}} a_{i_1} \cdots a_{i_t} + \sum_{\substack{0 < i_1 < \cdots < i_t < k - 1 \\ i_{j+1} - i_j \geq 2}} a_{i_1} \cdots a_{i_t} \cdot a_k \\ &= \sum_{\substack{0 < i_1 < \cdots < i_t < k + 1 \\ i_{j+1} - i_j \geq 2, \; k \notin \{i_1, \ldots, i_t\}}} a_{i_1} \cdots a_{i_t} + \sum_{\substack{0 < i_1 < \cdots < i_t < k + 1 \\ i_{j+1} - i_j \geq 2, \; k \in \{i_1, \ldots, i_t\}}} a_{i_1} \cdots a_{i_t} \\ &= \sum_{\substack{0 < i_1 < \cdots < i_t < k + 1 \\ i_{j+1} - i_j \geq 2}} a_{i_1} \cdots a_{i_t}, \end{aligned}\]

comme voulu.

En appliquant (1) à la suite \(b_1, \ldots, b_n\) définie par \(b_k = a_{n-k}\) pour \(1 \leq k \leq n\), on obtient

\[v_k = \sum_{\substack{0 < i_1 < \cdots < i_t < k \\ i_{j+1} - i_j \geq 2}} b_{i_1} \cdots b_{i_t} = \sum_{\substack{n > i_1 > \cdots > i_t > n - k \\ i_j - i_{j+1} \geq 2}} a_{i_1} \cdots a_{i_t}. \tag{2}\]

Pour \(k = n\), les expressions (1) et (2) coïncident, donc \(u_n = v_n\). \(\blacksquare\)

Solution 2

Définissons par récurrence une suite de polynômes à plusieurs variables par

\[P_0 = P_1 = 1, \qquad P_{k+1}(x_1, \ldots, x_k) = P_k(x_1, \ldots, x_{k-1}) + x_k P_{k-1}(x_1, \ldots, x_{k-2}),\]

de sorte que \(P_n\) est un polynôme en \(n - 1\) variables pour tout \(n \geq 1\). Deux récurrences faciles montrent que

\[u_n = P_n(a_1, \ldots, a_{n-1}), \qquad v_n = P_n(a_{n-1}, \ldots, a_1),\]

donc il s'agit de prouver \(P_n(x_1, \ldots, x_{n-1}) = P_n(x_{n-1}, \ldots, x_1)\) pour tout entier \(n \geq 1\). Les cas \(n = 1, 2\) sont évidents, et les cas \(n = 3, 4\) découlent de \(P_3(x, y) = 1 + x + y\) et \(P_4(x, y, z) = 1 + x + y + z + xz\).

Procédons par récurrence, en supposant \(n \geq 5\) et l'affirmation vraie pour les cas plus petits. Notons \(F(a, b)\) une abréviation pour \(P_{\lvert a - b \rvert + 1}(x_a, \ldots, x_b)\) (les indices \(a, \ldots, b\) pouvant être dans l'ordre croissant ou décroissant). Alors

\[\begin{aligned} F(n, 1) &= F(n, 2) + x_1 F(n, 3) = F(2, n) + x_1 F(3, n) \\ &= \big(F(2, n - 1) + x_n F(2, n - 2)\big) + x_1 \big(F(3, n - 1) + x_n F(3, n - 2)\big) \\ &= \big(F(n - 1, 2) + x_1 F(n - 1, 3)\big) + x_n \big(F(n - 2, 2) + x_1 F(n - 2, 3)\big) \\ &= F(n - 1, 1) + x_n F(n - 2, 1) = F(1, n - 1) + x_n F(1, n - 2) \\ &= F(1, n), \end{aligned}\]

ce qu'il fallait démontrer. \(\blacksquare\)

Solution 3

Avec des matrices, la relation de récurrence s'écrit

\[\begin{pmatrix} u_{k+1} \\ u_{k+1} - u_k \end{pmatrix} = \begin{pmatrix} u_k + a_k u_{k-1} \\ a_k u_{k-1} \end{pmatrix} = \begin{pmatrix} 1 + a_k & -a_k \\ a_k & -a_k \end{pmatrix} \begin{pmatrix} u_k \\ u_k - u_{k-1} \end{pmatrix}\]

pour \(1 \leq k \leq n - 1\), et de même

\[(v_{k+1}; \; v_k - v_{k+1}) = (v_k + a_{n-k} v_{k-1}; \; -a_{n-k} v_{k-1}) = (v_k; \; v_{k-1} - v_k) \begin{pmatrix} 1 + a_{n-k} & -a_{n-k} \\ a_{n-k} & -a_{n-k} \end{pmatrix}\]

pour \(1 \leq k \leq n - 1\). En introduisant les matrices \(2 \times 2\)

\[A_k = \begin{pmatrix} 1 + a_k & -a_k \\ a_k & -a_k \end{pmatrix},\]

on a donc

\[\begin{pmatrix} u_{k+1} \\ u_{k+1} - u_k \end{pmatrix} = A_k \begin{pmatrix} u_k \\ u_k - u_{k-1} \end{pmatrix} \quad \text{et} \quad (v_{k+1}; \; v_k - v_{k+1}) = (v_k; \; v_{k-1} - v_k) A_{n-k}\]

pour \(1 \leq k \leq n - 1\). Comme \(\binom{u_1}{u_1 - u_0} = \binom{1}{0}\) et \((v_1; \; v_0 - v_1) = (1; \; 0)\), on obtient

\[\begin{pmatrix} u_n \\ u_n - u_{n-1} \end{pmatrix} = A_{n-1} A_{n-2} \cdots A_1 \begin{pmatrix} 1 \\ 0 \end{pmatrix} \quad \text{et} \quad (v_n; \; v_{n-1} - v_n) = (1; \; 0) \, A_{n-1} A_{n-2} \cdots A_1.\]

Il s'ensuit que

\[(u_n) = (1; \; 0) \begin{pmatrix} u_n \\ u_n - u_{n-1} \end{pmatrix} = (1; \; 0) \, A_{n-1} A_{n-2} \cdots A_1 \begin{pmatrix} 1 \\ 0 \end{pmatrix} = (v_n; \; v_{n-1} - v_n) \begin{pmatrix} 1 \\ 0 \end{pmatrix} = (v_n). \qquad \blacksquare\]

Remarques

Remarque 1. Ces suites sont liées à la suite de Fibonacci : quand \(a_1 = \cdots = a_{n-1} = 1\), on a \(u_k = v_k = F_{k+1}\), le \((k+1)\)-ème nombre de Fibonacci. De plus, pour tout entier \(k \geq 1\), le polynôme \(P_k(x_1, \ldots, x_{k-1})\) de la solution 2 est la somme de \(F_{k+1}\) monômes.

Remarque 2. On peut remarquer que la condition équivaut à

\[\frac{u_{k+1}}{u_k} = 1 + \cfrac{a_k}{1 + \cfrac{a_{k-1}}{1 + \cdots + \cfrac{a_2}{1 + a_1}}} \qquad \text{et} \qquad \frac{v_{k+1}}{v_k} = 1 + \cfrac{a_{n-k}}{1 + \cfrac{a_{n-k+1}}{1 + \cdots + \cfrac{a_{n-2}}{1 + a_{n-1}}}},\]

de sorte que le problème affirme que les fractions continues correspondantes pour \(\frac{u_n}{u_{n-1}}\) et \(\frac{v_n}{v_{n-1}}\) ont le même numérateur.

Remarque 3. Voici une variante du problème.

Soit \(n\) un entier strictement positif et \(a_1, \ldots, a_{n-1}\) des réels quelconques. On définit les suites \(u_0, \ldots, u_n\) et \(v_0, \ldots, v_n\) par \(u_0 = v_0 = 0\), \(u_1 = v_1 = 1\), et \(u_{k+1} = a_k u_k + u_{k-1}\), \(v_{k+1} = a_{n-k} v_k + v_{k-1}\) pour \(k = 1, \ldots, n - 1\). Montrer que \(u_n = v_n\).

Les trois solutions ci-dessus s'adaptent à cet énoncé ; on peut prouver

\[u_n = v_n = \sum_{\substack{0 = i_0 < i_1 < \cdots < i_t = n \\ i_{j+1} - i_j \text{ impair}}} a_{i_1} \cdots a_{i_{t-1}} \quad \text{pour } n > 0,\]

ou observer que

\[\begin{pmatrix} u_{k+1} \\ u_k \end{pmatrix} = \begin{pmatrix} a_k & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} u_k \\ u_{k-1} \end{pmatrix} \quad \text{et} \quad (v_{k+1}; \; v_k) = (v_k; \; v_{k-1}) \begin{pmatrix} a_{n-k} & 1 \\ 1 & 0 \end{pmatrix}.\]

(Le livret écrit \(a_k\) dans la seconde matrice ; il faut lire \(a_{n-k}\).) On a ici

\[\frac{u_{k+1}}{u_k} = a_k + \cfrac{1}{a_{k-1} + \cfrac{1}{a_{k-2} + \cdots + \cfrac{1}{a_1}}} = [a_k; a_{k-1}, \ldots, a_1]\]

et

\[\frac{v_{k+1}}{v_k} = a_{n-k} + \cfrac{1}{a_{n-k+1} + \cfrac{1}{a_{n-k+2} + \cdots + \cfrac{1}{a_{n-1}}}} = [a_{n-k}; a_{n-k+1}, \ldots, a_{n-1}],\]

de sorte que cet énoncé équivaut au fait connu que les fractions continues \([a_{n-1}; a_{n-2}, \ldots, a_1]\) et \([a_1; a_2, \ldots, a_{n-1}]\) ont le même numérateur.