BANQUE COMMUNE D'EPREUVES CONCOURS D'ADMISSION DE 2009 Conception : HAUTES ETUDES COMMERCIALES 280 OPTION SCIENTIFIQUE MATHEMATIQUES HEC__MATS Mardi 28 avril 2009, de 8 h. à 12 h. La présentation, la lisibilité, l'orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l'appréciation des copies. Les candidats sont invités à encadrer dans la mesure du possible les résultats de leurs calculs. Ils ne doivent faire usage d'aucun document : l'utilisation de toute calculatrice et de tout matériel électronique est interdite. Seule l'utilisation d'une règle graduée est autorisée. Si au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il la signalera sur sa copie et poursuivra sa composition en expliquant les raisons des initiatives qu'il sera amené à prendre Le problème a pour objet l'étude de quelques propriétés des suites récurrentes linéaires intervenant notamment dans l'analyse de processus aléatoires utilisés en prévision économique, ainsi que leur lien avec la notion de polynôme minimal. Les parties II, III et IV sont indépendantes de la partie I. Partie I. Deux exemples Exemple 1. 1. On considère la suite $s = (s_n)_{n \in \mathbb{N}^*}$ définie par $s_1 = 1$, $s_2 = \frac{4}{5}$, $s_3 = \frac{2}{5}$ et la relation : pour tout $n$ de $\mathbb{N}^*$, $s_{n+3} = \frac{3}{2} s_{n+2} - s_{n+1} + \frac{1}{4} s_n$. a) Écrire une fonction Pascal d'en-tête suite(s1,s2,s3 : real, n : integer) : real qui, pour tout $n$ de $\mathbb{N}^*$, renvoie le $n$-ième terme de cette suite. b) Établir, pour tout $n$ de $\mathbb{N}^*$, l'égalité : $s_n = \frac{1}{5 \times 2^{n-2}} + \frac{3}{5 \times 2^{(n-2)/2}} \times \sin\left(\frac{n\pi}{4}\right)$. c) Déterminer la limite de la suite $(s_n)_{n \in \mathbb{N}^*}$. d) Montrer que le polynôme $P(X) = X^3 - \frac{3}{2}X^2 + X - \frac{1}{4}$ admet une unique racine réelle $\lambda_1$, valant $\frac{1}{2}$ ; déterminer ses deux racines complexes $\lambda_2$ et $\lambda_3$ dont on précisera le module et un argument. e) On admet qu'il existe trois nombres complexes $\alpha_1, \alpha_2, \alpha_3$ vérifiant, pour tout $n$ de $\mathbb{N}^*$, la relation suivante : $s_n = \frac{\alpha_1}{2^n} + \alpha_2 \lambda_2^n + \alpha_3 \lambda_3^n$. Calculer $\alpha_1$, $\alpha_2$ et $\alpha_3$. Retrouver la limite de la suite $(s_n)_{n \in \mathbb{N}^*}$. Exemple 2. Soit $(x, y)$ un élément de $\mathbb{R}^2$ et $P$ le polynôme de $\mathbb{R}[X]$ défini par : $P(X) = X^2 - xX - y$. On note $r_1$ et $r_2$ les racines réelles ou complexes, distinctes ou confondues du polynôme $P$. 2. a) Dans le plan rapporté à un repère orthonormé $(O, \vec{i}, \vec{j})$, représenter graphiquement l'ensemble $\mathcal{D}$ des points de coordonnées $(x, y)$ défini par : $$\mathcal{D} = \{(x, y) \in \mathbb{R}^2 \mid |y| < 1 \text{ et } |x| < 1 - y\}$$ b) Distinguer sur le graphique la partie de $\mathcal{D}$ dans laquelle les racines de $P$ sont réelles. 3. En étudiant séparément le cas où les racines $r_1$ et $r_2$ sont réelles et le cas où elles sont complexes, établir l'équivalence des trois conditions suivantes : i) $|r_1| < 1$ et $|r_2| < 1$. ii) $P(-1) > 0$, $P(1) > 0$ et $|r_1 r_2| < 1$. iii) $|y| < 1$ et $|x| < 1 - y$. On désigne par $\mathcal{E}$ l'ensemble des variables aléatoires discrètes définies sur un espace probabilisé et admettant un moment d'ordre 2. On note $E(A)$ et $V(A)$ respectivement, l'espérance et la variance d'une variable aléatoire $A$ de $\mathcal{E}$. Si $A$ et $B$ appartiennent à $\mathcal{E}$, leur covariance est notée $\text{cov}(A, B)$. On appelle processus aléatoire $Y = (Y_t)_{t \in \mathbb{Z}}$, toute application $Y$ définie sur $\mathbb{Z}$ à valeurs dans $\mathcal{E}$. Soit $W = (W_t)_{t \in \mathbb{Z}}$ un processus aléatoire constitué de variables aléatoires mutuellement indépendantes, vérifiant pour tout $t$ de $\mathbb{Z}$, les égalités suivantes : $E(W_t) = 0$ et $V(W_t) = \sigma^2$, avec $\sigma$ strictement positif fixé. Soit $(a_1, a_2)$ un élément de $\mathbb{R}^2$. On considère un processus aléatoire $Y = (Y_t)_{t \in \mathbb{Z}}$ formé de variables aléatoires centrées, de même variance strictement positive et qui vérifient, pour tout $t$ de $\mathbb{Z}$ : $$Y_t = a_1 Y_{t-1} + a_2 Y_{t-2} + W_t$$ On suppose que : - pour tout couple $(t, k)$ de $\mathbb{Z} \times \mathbb{N}^*$, $\text{cov}(W_t, Y_{t-k}) = 0$ ; - pour tout couple $(t, k)$ de $\mathbb{Z}^2$, $\text{cov}(Y_t, Y_{t-k})$ ne dépend que de $k$. On pose, pour tout $k$ de $\mathbb{Z}$ : $\gamma_k = \text{cov}(Y_t, Y_{t-k})$ et $\rho_k = \frac{\gamma_k}{\gamma_0}$. 4. a) Que représente $\gamma_0$ pour le processus $Y$ ? b) Établir, pour tout $k$ de $\mathbb{Z}$, l'égalité : $\gamma_{-k} = \gamma_k$. c) Montrer, pour tout $t$ de $\mathbb{Z}$, l'égalité : $\text{cov}(W_t, Y_t) = \sigma^2$. 5. On suppose dans cette question que le couple $(a_1, a_2)$ appartient à l'ensemble $\mathcal{D}$ défini dans la question 2.a. a) Exprimer $\gamma_1$ et $\gamma_2$ en fonction de $\gamma_0$, $a_1$ et $a_2$. En déduire l'expression de $\rho_1$ et $\rho_2$ en fonction de $a_1$ et $a_2$. b) Établir les deux inégalités : $a_1 \rho_1 + a_2 \rho_2 \geqslant 0$ et $|\rho_1| < 1$, ainsi que l'encadrement : $0 \leqslant a_1 \rho_1 + a_2 \rho_2 < 1$. c) Exprimer $\gamma_0$ en fonction de $\sigma^2$, $a_1$, $a_2$ et $\rho_2$. 6. a) Montrer que la suite $(\rho_k)_{k \in \mathbb{N}}$ vérifie une relation de récurrence linéaire d'ordre 2. b) Soit $r_1$ et $r_2$ les racines du polynôme $P(X) = X^2 - a_1 X - a_2$. Montrer que la suite $(\rho_k)_{k \in \mathbb{N}}$ converge vers 0 si et seulement si $|r_1| < 1$ et $|r_2| < 1$ (on distinguera trois cas : $r_1$ et $r_2$ réels avec $|r_1| < |r_2|$, $r_1$ et $r_2$ réels avec $|r_1| = |r_2|$, $r_1$ et $r_2$ complexes conjugués). Partie II. Suites récurrentes linéaires d'ordre $p$ Dans cette partie, $p$ est un entier de $\mathbb{N}^*$ et $(a_1, a_2, \ldots, a_p)$ un élément de $\mathbb{C}^p$ vérifiant $a_p \neq 0$. On note $\mathcal{S}$ le $\mathbb{C}$-espace vectoriel des suites complexes et $\mathcal{S}_p$ le sous-ensemble de $\mathcal{S}$ formé des suites $s = (s_n)_{n \in \mathbb{N}^*}$ récurrentes linéaires d'ordre $p$, c'est-à-dire, qui vérifient pour tout $n$ de $\mathbb{N}^*$ : $$s_{n+p} = a_1 s_{n+p-1} + a_2 s_{n+p-2} + \cdots + a_p s_n$$ 7. Montrer que $\mathcal{S}_p$ est un sous-espace vectoriel de $\mathcal{S}$. 8. Soit $\Phi$ l'application de $\mathcal{S}_p$ dans $\mathbb{C}^p$ qui, à toute suite $(s_n)_{n \in \mathbb{N}^*}$ de $\mathcal{S}_p$, associe le $p$-uplet $(s_1, s_2, \ldots, s_p)$ de $\mathbb{C}^p$. Montrer que $\Phi$ est un isomorphisme d'espaces vectoriels. En déduire la dimension de $\mathcal{S}_p$. 9. On note $(e_1, e_2, \ldots, e_p)$ la base canonique de $\mathbb{C}^p$ et $\Phi^{-1}$ l'application réciproque de $\Phi$. Pour tout $i$ de $[1, p]$, on considère la suite $v^{(i)} = (v^{(i)}_n)_{n \in \mathbb{N}^*}$ définie par : $v^{(i)} = \Phi^{-1}(e_i)$. a) Justifier que $(v^{(1)}, v^{(2)}, \ldots, v^{(p)})$ constitue une base de $\mathcal{S}_p$. Préciser les coordonnées de toute suite $(s_n)_{n \in \mathbb{N}^*}$ de $\mathcal{S}_p$ dans la base $(v^{(1)}, v^{(2)}, \ldots, v^{(p)})$. b) Calculer, pour tout $j$ de $[1, p]$, $v^{(j)}_1, v^{(j)}_2, \ldots, v^{(j)}_p$. Montrer que, pour tout $i$ de $[1, p]$, on a : $v^{(i)}_{p+1} = a_{p-i+1}$. 10. Soit $\delta$ l'application définie sur $\mathcal{S}_p$ par : pour toute suite $s = (s_n)_{n \in \mathbb{N}^*}$ de $\mathcal{S}_p$, $\delta(s) = (s_{n+1})_{n \in \mathbb{N}^*}$. a) Montrer que $\delta$ est un endomorphisme de $\mathcal{S}_p$. b) Déterminer la matrice $\Delta$ de $\delta$ dans la base $(v^{(1)}, v^{(2)}, \ldots, v^{(p)})$. 11. Soit $P$ le polynôme de $\mathbb{C}[X]$ défini par : $P(X) = X^p - a_1 X^{p-1} - \cdots - a_{p-1} X - a_p$. a) Montrer que $\lambda$ est une valeur propre de $\delta$ si et seulement si $\lambda$ est une racine de $P$. b) Soit $\lambda$ une valeur propre de $\delta$. Déterminer la dimension du sous-espace propre associé à $\lambda$, et en déduire une condition nécessaire et suffisante sur $P$ pour que $\delta$ soit diagonalisable. c) On suppose que $P$ admet $p$ racines distinctes $\lambda_1, \ldots, \lambda_p$. Établir, pour toute suite $s = (s_n)_{n \in \mathbb{N}^*}$ de $\mathcal{S}_p$, l'existence d'un unique $p$-uplet $(\alpha_1, \alpha_2, \ldots, \alpha_p)$ de $\mathbb{C}^p$ tel que, pour tout $n$ de $\mathbb{N}^*$, on ait : $s_n = \sum_{i=1}^{p} \alpha_i \lambda_i^n$. Partie III. Polynôme minimal d'une suite récurrente linéaire Le contexte et les notations de cette partie sont ceux du préambule de la partie II et de la question 10. On considère une suite $s = (s_n)_{n \in \mathbb{N}^*}$ de $\mathcal{S}_p$. On dit qu'un polynôme $Q$ de $\mathbb{C}[X]$ est un polynôme générateur de la suite $s$, si $[Q(\delta)](s) = 0_{\mathcal{S}_p}$. On note $J$ l'ensemble des polynômes générateurs de la suite $s$. 12. Montrer que $J$ n'est pas réduit au polynôme nul. 13. Montrer que $J$ est un sous-espace vectoriel de $\mathbb{C}[X]$. 14. Montrer que, si $Q$ est un polynôme de $J$ et $A$ un polynôme de $\mathbb{C}[X]$, alors $Q \times A$ appartient à $J$. 15. On note $N$ l'ensemble des degrés des polynômes non nuls de $J$. a) Justifier l'existence d'un polynôme $\Pi$ de $J$ tel que son degré soit le plus petit élément de $N$. On note $d$ le degré de $\Pi$. b) En utilisant la division euclidienne des polynômes, montrer que $J$ est l'ensemble des polynômes de la forme $\Pi \times L$, avec $L$ élément de $\mathbb{C}[X]$. c) En déduire qu'il existe un unique polynôme de $J$, noté $\Pi^*$, de coefficient dominant égal à 1 et de degré $d$. On dit que $\Pi^*$ est le polynôme générateur minimal de $s$ et que son degré $d$ est le degré de la suite $s$. 16. Un exemple. Déterminer le polynôme générateur minimal et le degré de la suite $s = (s_n)_{n \in \mathbb{N}^*}$ récurrente linéaire d'ordre 3 définie par $s_1 = 0$, $s_2 = s_3 = 1$ et la relation : pour tout $n$ de $\mathbb{N}^*$, $s_{n+3} = 2s_{n+1} + s_n$. 17. Soit $s = (s_n)_{n \in \mathbb{N}^*}$ une suite récurrente linéaire de degré $d$ ($d \geqslant 1$) et soit $k$ un entier strictement supérieur à $d$. On note $H$ la matrice de $\mathcal{M}_k(\mathbb{C})$ définie par : $$H = \begin{pmatrix} s_1 & s_2 & \ldots & s_k \\ s_2 & s_3 & \ldots & s_{k+1} \\ \vdots & & & \vdots \\ s_k & s_{k+1} & \ldots & s_{2k-1} \end{pmatrix}$$ Pour tout $j$ de $[1, k]$, on note $U_j$ la $j$-ième colonne de $H$. On désigne par $h$ l'endomorphisme de $\mathbb{C}^k$ canoniquement associé à $H$, et, pour tout $j$, on note $u_j$ le vecteur de $\mathbb{C}^k$ canoniquement associé à $U_j$. a) Montrer que la famille $(u_1, u_2, \ldots, u_d)$ est une famille libre de $\text{Im}(h)$. b) Établir que, pour tout $j$ de $[\![d+1, k]\!]$, la famille $(u_1, u_2, \ldots, u_d, u_j)$ est liée. En déduire le rang de $h$ et la dimension de $\text{Ker}(h)$. c) Montrer qu'un polynôme $Q(X) = \sum_{j=0}^{k-1} q_j X^j$ de $\mathbb{C}[X]$ appartient à $J$, si et seulement si l'élément $(q_0, q_1, \ldots, q_{k-1})$ de $\mathbb{C}^k$ appartient à $\text{Ker}(h)$. d) Un exemple. Soit $(s_n)_{n \in \mathbb{N}^*}$ une suite récurrente linéaire de degré inférieur ou égal à 3 dont les premiers termes sont : $-1, 7, 5, 19, 29, 67, 125$. Déterminer le polynôme générateur minimal de cette suite. Partie IV. Un algorithme de calcul d'un polynôme générateur d'une suite récurrente linéaire Soit $d$ et $k$ deux entiers tels que $1 \leqslant d \leqslant k$ et soit $s = (s_n)_{n \in \mathbb{N}^*}$ une suite complexe récurrente linéaire de degré $d$ dont on connaît les $2k$ premiers termes ; on pose : $S(X) = \sum_{i=0}^{2k-1} s_{2k-i} X^i$. On note $\mathbb{C}_k[X]$ l'espace vectoriel des polynômes à coefficients complexes de degré inférieur ou égal à $k$. Soit $Q(X) = \sum_{j=0}^{k} q_j X^j$ un polynôme de $\mathbb{C}_k[X]$. Le degré d'un polynôme $T$ est noté $\deg(T)$. 18. On note $(\star)$ la relation suivante : pour tout $n$ de $[1, k]$, on a $\sum_{j=0}^{k} q_j s_{n+j} = 0$. Montrer que $Q$ est un polynôme générateur de la suite $s$ si et seulement si la relation $(\star)$ est vérifiée. 19. a) On pose, pour tout $n$ de $[0, 3k-1]$ : $t_n = \sum_{i \in [0, 2k-1], j \in [0, k], i+j=n} q_j s_{2k-i}$. Établir l'égalité : $QS = \sum_{n=0}^{3k-1} t_n X^n$. b) On suppose la relation $(\star)$ vérifiée. Montrer, pour tout $n$ de $[k, 2k-1]$, l'égalité : $t_n = 0$. En déduire l'existence de deux polynômes $A$ et $B$ de $\mathbb{C}_{k-1}[X]$ vérifiant : $QS = A + X^{2k} B$. c) Réciproquement, s'il existe deux polynômes $A$ et $B$ de $\mathbb{C}_{k-1}[X]$ vérifiant : $QS = A + X^{2k} B$. Montrer que la relation $(\star)$ est vérifiée. 20. Dans l'algorithme suivant, les variables $A, B, C, D, E, F, R, S$ sont des polynômes, $k$ une constante entière. L'entier $k$ et le polynôme $S$ ont les valeurs données précédemment. Initialisation : $A := X^{2k}$, $B := S$, $C := 0$, $D := 1$. Corps : Tant que $\deg(B) \geqslant k$ effectuer la division euclidienne de $A$ par $B$, $A = BF + R$ avec $R = 0$ ou $\deg(R) < \deg(B)$. $E := C - DF$. $C := D$, $D := E$, $A := B$, $B := R$. Fin de Tant que. Sortie : Rendre $D$ et $B$. Si $U$ et $V$ sont deux polynômes de $\mathbb{C}[X]$ tels qu'il existe un polynôme $W$ de $\mathbb{C}_{k-1}[X]$ vérifiant $U = V + X^{2k} W$, on notera : $U \equiv V$. a) Montrer que cet algorithme se termine, c'est-à-dire que l'on sort de la boucle. b) Montrer qu'à l'initialisation, on a : $\deg(C) \leqslant 2k - \deg(A)$, $\deg(D) \leqslant 2k - \deg(B)$, $k \leqslant \deg(B) \leqslant \deg(A)$, $CS \equiv A$, $DS \equiv B$. c) On suppose qu'à l'issue du $j$-ième passage dans la boucle, les relations précédentes sont vérifiées. Montrer qu'elles le sont encore à l'issue du $(j+1)$-ième passage. d) Montrer que lorsque l'algorithme se termine, l'une des variables contient un polynôme générateur de la suite $s$. Quelle est cette variable ?