\documentclass{article}
\usepackage{epsf}
\usepackage{amsfonts}
\usepackage{amsmath}

\setlength{\oddsidemargin}{0.5cm}
\setlength{\textwidth}{15cm}
\setlength{\headheight}{0cm}
\setlength{\topmargin}{0cm} 
\setlength{\headsep}{0cm}
\setlength{\textheight}{23cm}
\setlength{\parindent}{1cm}



\def\aujourdhui{\number\day\space\ifcase\month\or
  Janvier\or F\'evrier\or Mars\or Avril\or Mai\or Juin\or
  Juillet\or Ao\^ut\or Septembre\or Octobre\or Novembre\or D\'ecembre\fi
, \number\year}


\newcommand{\solution}[1]{\par\noindent{\em R\'eponse --- #1}}

%\renewcommand{\thepage}{ }
\newcommand{\1}[1]{\`{#1}}
%sublist
\newcounter{point}
\newenvironment{sublist}{
\begin{list}{\alph{point})}{\usecounter{point}
\setlength{\itemsep}{0cm}\setlength{\leftmargin}{0.5cm}}
}{\end{list}}
                                                                
%initialize point
\newcommand{\initpoint}{\setcounter{point}{0}}
%Print point and step
\newcommand{\np}{\stepcounter{point}
\mbox{\quad\quad\alph{point})\,\,\,}\displaystyle}


%liste d'exercices
\newcounter{exo}
\newenvironment{list-of-exercises}{
\begin{list}{\arabic{exo})}{\usecounter{exo}            
\setlength{\itemsep}{0cm}}                                      
}{\end{list}}                                                   
                                                                
\newcommand{\tit}[1]{\par\bigskip\noindent {\bf #1}\bigskip\par\noindent}


% abbreviations
% Black Board Bold Face
\newcommand{\N}{\mathbb{N}}
\newcommand{\sN}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\sZ}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\K}{\mathbb{K}}
%Comma, forall
\newcommand{\ko}{\: , \;}
\newcommand{\fa}{\forall \,}
%Overline, Underline
\newcommand{\ol}{\overline}
\newcommand{\ul}{\underline}

%Greek letters
\newcommand{\eps}{\varepsilon}


%Calligraphic letters
\newcommand{\ca}{{\cal A}}
\newcommand{\cb}{{\cal B}}
\newcommand{\cc}{{\cal C}}
\newcommand{\cd}{{\cal D}}
\newcommand{\ce}{{\cal E}}
\newcommand{\cf}{{\cal F}}
\newcommand{\cg}{{\cal G}}
\newcommand{\ch}{{\cal H}}
\newcommand{\ci}{{\cal I}}
\newcommand{\ck}{{\cal K}}
\newcommand{\cl}{{\cal L}}
\newcommand{\cm}{{\cal M}}
\newcommand{\cn}{{\cal N}}
\newcommand{\cp}{{\cal P}}
\newcommand{\cq}{{\cal Q}}
\newcommand{\cs}{{\cal S}}
\newcommand{\ct}{{\cal T}}
\newcommand{\cu}{{\cal U}}
\newcommand{\cv}{{\cal V}}
\newcommand{\cw}{{\cal W}}
\newcommand{\cx}{{\cal X}}



%Arrows
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\arr}[1]{\xrightarrow{#1}}
\newcommand{\longarr}[1]{\stackrel{#1}{\longrightarrow}}
\newcommand{\longlarr}[1]{\stackrel{#1}{\longleftarrow}}
\newcommand{\iso}{\stackrel{_\sim}{\rightarrow}}
\newcommand{\liso}{\stackrel{_\sim}{\leftarrow}}
\newcommand{\larr}[1]{\stackrel{#1}{\leftarrow}}
\newcommand{\da}{\downarrow}
\newcommand{\ua}{\uparrow}
\newcommand{\pl}{\parallel}



%French terminology
\newcommand{\tg}{\mbox{tg}\,}
\newcommand{\arctg}{\mbox{arctg}\,}


%\renewcommand{\arraystretch}{2}

\renewcommand{\vec}[1]{\stackrel{\longrightarrow}{#1}}


\begin{document}
\begin{center}
Universit\'e Paris 7  \hfill 6 novembre 2001\\
U.F.R. de Math\'ematiques\hfill \mbox{B.~Keller}\\[0.5cm]
{\bf DEUG MASS Premi\`ere ann\'ee : MT 131 \\[0.5cm]
              Un corrig\'e du Devoir 1}
\end{center}

\tit{Question de cours}
\vspace*{-0.5cm}
\begin{list-of-exercises}
\item Soient $E$ un espace vectoriel sur $\K$. Qu'est-ce qu'un
sous-espace vectoriel de $E$ ?
\solution{Un sous-espace vectoriel de $E$ est une partie $F$ de $E$ telle que
\begin{itemize}
\item[(1)] le vecteur $0$ appartient \`a $F$, et
\item[(2)] pour tous vecteurs $v,w\in F$, le vecteur $v+w$ appartient encore \`a $F$, et
\item[(3)] pour tout vecteur $v\in F$ et tout $\lambda \in \K$, le vecteur
$\lambda v$ appartient encore \`a $F$.
\end{itemize}
}
\item Soient $E$ et $F$ des espaces vectoriels sur $\K$. Qu'est-ce
qu'une application lin\'eaire de $E$ dans $F$ ?
\solution{Une application lin\'eaire de $E$ dans $F$ est une application
$f$ de $E$ dans $F$ telle que, pour tous vecteurs $v,w$ de $E$ et tout $\lambda\in\K$,
on ait
\[
f(v+w)=f(v)+f(w) \mbox{ et } f(\lambda v)= \lambda \, f(v).
\]
}
\item Soit $f$ une application lin\'eaire de $E$ dans $F$. Rappeler
la d\'efinition du noyau de $f$. Montrer que le noyau de $f$ est
un sous-espace vectoriel.
\solution{Le noyau de $f$ est l'ensemble des vecteurs $v\in E$ tels que
$f(v)=0$. En particulier, comme on a $f(0)=0$, le noyau de $f$ contient
le vecteur $0$. Si $v$ et $w$ appartiennent au noyau et $\lambda$ est
un scalaire, on a 
\[
f(v+w)=f(v)+f(w)=0+0=0 \mbox{ et } f(\lambda v)=\lambda f(v) = \lambda 0 = 0.
\]
Donc $v+w$ et $\lambda v$ appartiennent encore au noyau. Donc le noyau
est bien un sous-espace vectoriel.}
\item Montrer que l'application lin\'eaire
$f$ est injective si et seulement si son noyau est r\'eduit \`a $\{0\}$.
\solution{Supposons que $f$ est injective. Soit $v$ un vecteur du noyau de $f$.
On a donc $f(v)=0=f(0)$. Comme $f$ est injective, on doit avoir $v=0$. Donc
le noyau de $f$ est le sous-espace $\{0\}$. R\'eciproquement, supposons que
le noyau de $f$ s'annule. Soient $v$ et $w$ deux vecteurs de $E$ tels que
$f(v)=f(w)$. Alors $f(v-w)=f(v)-f(w)=0$. Donc $v-w$ appartient au noyau
de $f$. Comme le noyau est r\'eduit \`a $\{0\}$, on doit avoir $v-w=0$ et donc $v=w$. 
Donc $f$ est injective.}
\end{list-of-exercises}

\tit{Exercice I}
Soit $E\subset \R^3$ le plan d'\'equation $x+y+z=0$ et $F$ la droite
engendr\'ee par le vecteur $(1,2,1)$. 
\begin{list-of-exercises}

\item Montrer que $E$ et $F$ sont suppl\'ementaires.
\solution{Il s'agit de montrer que $E\cap F=\{0\}$ et que 
$E+F=\R^3$. Notons $v$ le vecteur $(1,2,1)$. Pour $t\in \R$, le vecteur
$tv$ appartient \`a $E$ ssi $t+2t+t=0$ et c'est le cas ssi $t=0$. 
Donc l'intersection de $E$ et $F$ est $\{0\}$. Pour montrer que
$E+F=\R^3$, il suffit de montrer que $\dim(E+F)=3$. Or on sait
que $\dim(E+F)=\dim E + \dim F - \dim(E\cap F)$. La dimension
de l'intersection est nulle, la dimension de la droite $F$ est
$1$ et la dimension de $E$ est $2$ (car $E$ est le noyau d'une
forme lin\'eaire non nulle $\R^3\ra \R$). Donc $E+F$
est bien de dimension $3$ et, par cons\'equent, \'egal \`a $\R^3$.
}

\item Soit $s$ la sym\'etrie par rapport \`a $E$ parall\`element \`a $F$.
Choisir une base $v_1, v_2$ de $E$ et une base $v_3$ de $F$.
D\'eterminer la matrice de $s$ dans la base $(v_1, v_2, v_3)$ de $\R^3$.
Est-ce qu'elle d\'epend du choix de $v_1, v_2, v_3$ ?
\solution{On peut choisir $v_1=(1,-1,0)$ et $v_2=(0,1,-1)$. Ces deux vecteurs
sont clairement lin\'eairement ind\'ependants. Comme $E$ est de dimension $2$,
ils forment une base de $E$. Le vecteur $v_3=(1,2,1)$ est clairement une base
de $F$. Puisque $E$ et $F$ sont suppl\'ementaires, la famille $(v_1, v_2, v_3)$
est bien une base de $\R^3$.

Par d\'efinition, on a $s(v+w)=v-w$ pour tout $v\in E$ et tout $w\in F$.
En particulier, on a $s(v_1)=v_1$, $s(v_2)=v_2$ et $s(v_3)=-v_3$. La matrice
de $s$ dans la base $v_1, v_2, v_3$ est donc
\[
\left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & -1 \end{array} \right] \; .
\]
La matrice ne d\'epend pas du choix de $v_1$, $v_2$, $v_3$; pour la calculer
on a utilis\'e uniquement le fait que $v_1$ et $v_2$ forment une base de $E$ et
$v_3$ une base de $F$.
}

\item D\'eterminer la matrice de $s$ dans la base canonique de $\R^3$.
\solution{Dans le point pr\'ec\'edent, nous avons calcul\'e la matrice
$A'$ de $s$ dans la nouvelle base $(v_1, v_2, v_3)$. Notons $A$ la matrice
de $s$ dans l'ancienne base $(e_1, e_2, e_3)$ et notons $P$ la matrice
de passage de l'ancienne vers la nouvelle base. Nous savons que
\[
A' = P^{-1} A P.
\]
En multipliant \`a gauche par $P$ et \`a droite par $P^{-1}$ nous obtenons
que $A= P A' P^{-1}$. Il reste \`a calculer $P$, $P^{-1}$ et le produit 
$P A' P^{-1}$. La matrice $P$ a pour $j$-i\`eme colonne les coordonn\'ees
du vecteur $v_j$ dans la base $(e_1, e_2, e_3)$,  pour tout $j$. Donc
\[
P = \left[ \begin{array}{ccc} 1 & 0 & 1 \\ -1 & 1 & 2 \\ 0 & -1 & 1 \end{array} \right] \; .
\]
Pour calculer l'inverse de $P$, nous effectuons des op\'erations \'el\'ementaires
sur les lignes de la matrice agrandie (bien s\^ur, le lecteur peut se servir 
d'une autre m\'ethode s'il le souhaite)
\begin{eqnarray*}
\left[
\begin{array}{ccc|ccc} 
1	& 0	& 1	& 1	& 0	& 0	\\
-1	& 1 	& 2	& 0	& 1	& 0	\\
0	& -1	& 1	& 0	& 0	& 1 
\end{array} 
\right]
&
\arr{T_{21}(1)\cdot} 
&
\left[
\begin{array}{ccc|ccc}
1	& 0	& 1	& 1	& 0	& 0	\\
0	& 1 	& 3	& 1	& 1	& 0	\\
0	& -1	& 1	& 0	& 0	& 1  	\\
\end{array} 
\right] \\
& \arr{T_{32}(1)\cdot} & 
\left[
\begin{array}{ccc|ccc}
1	& 0	& 1	& 1	& 0	& 0	\\
0	& 1 	& 3	& 1	& 1	& 0	\\
0	& 0	& 4	& 1	& 1	& 1  	\\
\end{array} 
\right] \\
 & \arr{D_3(1/4)\cdot} & 
\left[
\begin{array}{ccc|ccc}
1	& 0	& 1	& 1	& 0	& 0	\\
0	& 1 	& 3	& 1	& 1	& 0	\\
0	& 0	& 1	& 1/4	& 1/4	& 1/4  	\\
\end{array} 
\right] \\
& \arr{T_{13}(-1)T_{23}(-3)\cdot} & 
\left[
\begin{array}{ccc|ccc}
1	& 0	& 0	& 3/4	& -1/4	& -1/4	\\
0	& 1 	& 0	& 1/4	& 1/4	& -3/4	\\
0	& 0	& 1	& 1/4	& 1/4	& 1/4  	
\end{array} 
\right]
\end{eqnarray*}
Nous avons donc
\[
P^{-1}=\left[\begin{array}{ccc}
3/4	& -1/4	& -1/4	\\
1/4	& 1/4	& -3/4	\\
1/4	& 1/4	& 1/4  	
\end{array}
\right] \; .
\]
Finalement, on trouve
\[
A= P\, A' \, P^{-1} =  \; \frac{1}{2}
\left[
\begin{array}{ccc}
1 	& -1	& -1	\\
-2	& 0	& -2	\\
-1	& -1	& 1	
\end{array}
\right] \; .
\]
}
\end{list-of-exercises}

\tit{Exercice II}
D\'eterminer le rang de la matrice
\[
A=\left[\begin{array}{ccc} a+2 & 1 & a \\ a & a & -a \\ a-2 & -1 & 1 \end{array} \right]
\]
en fonction du nombre r\'eel $a$.
\solution{On sait que les op\'erations \'el\'ementaires sur les colonnes ne changent
pas le sous-espace engendr\'e par les colonnes. En particulier, elles ne changent pas
le rang. Commen\c{c}ons donc par simplifier la matrice donn\'ee en effectuant des
op\'erations \'el\'ementaires sur les colonnes~:
\begin{eqnarray*}
\left[\begin{array}{ccc}
a+2	& 1	& a	\\
a	& a	& -a	\\
a-2	& -1	& 1 
\end{array}\right]
& \arr{\mbox{\'echange $(1,2)$}} &
\left[\begin{array}{ccc}
1	& a+2	& a	\\
a	& a	& -a	\\
-1	& a-2	& 1 
\end{array}\right] \\
& \arr{\cdot T_{12}(-a-2) T_{13}(-a)} & 
\left[\begin{array}{ccc}
1	& 0		& 0		\\
a	& -a^2-a	& -a^2-a	\\
-1	& 2a		& a+1
\end{array}\right] \\
& \arr{\cdot T_{23}(-1)} & 
\left[\begin{array}{ccc}
1	& 0		& 0		\\
a	& -a^2-a	& 0		\\
-1	& 2a		& -a+1
\end{array}\right]
\end{eqnarray*}
Notons $A'$ la derni\`ere matrice.
Les coefficients diagonaux de cette matrice sont $1$, $-a(a+1)$, $(1-a)$.
Si l'on a $a\not\in\{-1,0,1\}$, alors les trois coefficients diagonaux
sont non nuls. Comme la matrice est triangulaire, elle est donc de rang $3$.

Si $a$ prend respectivement les valeurs $-1$, $0$ et $1$, alors la
matrice $A'$ est \'egale, respectivement,~\`a
\[
\left[\begin{array}{ccc}
1	& 0		& 0		\\
-1	& 0		& 0		\\
-1	& -2		& 0
\end{array}\right] \ko
\left[\begin{array}{ccc}
1	& 0		& 0		\\
0	& 0		& 0		\\
-1	& 0		& 1
\end{array}\right] \ko \mbox{ et }
\left[\begin{array}{ccc}
1	& 0		& 0		\\
1	& -2		& 0		\\
-1	& 2		& 0
\end{array}\right]
\]
Dans les trois cas, elle est de rang $2$. Comme $A$ et $A'$ sont de m\^eme rang
quel que soit $a$, on trouve finalement~: la matrice $A$ est de rang $2$ 
si $a\in \{-1,0,1\}$ et de rang $3$ sinon.
}




\tit{Exercice III}
Soient les vecteurs suivants de $\R^4$~:
\[
v_1=(1,1,0,2) \ko v_2=(1,2,0,3) \ko v_3 = (1,1,1,3) \ko v_4=(1,1,2,4).
\]
Soient $F$ le sous-espace de $\R^4$ engendr\'e par $v_1$ et $v_2$ et $G$ 
le sous-espace engendr\'e par $v_3$ et $v_4$.
\begin{list-of-exercises}
\item Montrer que $F$ et $G$ sont de dimension $2$.
\solution{Les vecteurs $v_1$ et $v_2$ ne sont pas proportionnels. Donc
ils sont lin\'eairement ind\'ependants et forment une base du sous-espace
$F$ qu'ils engendrent. Donc $F$ est bien de dimension $2$. De m\^eme,
les vecteurs $v_3$ et $v_4$ sont non proportionnels et $G$ est de
dimension~$2$.}
\item Montrer que $F+G$ est de dimension $3$. Que peut-on dire
de la dimension de $F\cap G$ ?
\solution{La somme $F+G$ est engendr\'ee par les quatre vecteurs $v_1$, $v_2$, $v_3$,
$v_4$. On sait que le sous-espace engendr\'e par les colonnes d'une matrice ne
change pas lorsqu'on effectue des op\'erations \'el\'ementaires sur ces colonnes.
Simplifions donc la famille de vecteurs $v_1, \ldots, v_4$ en effectuant des
op\'erations \'el\'ementaires sur la matrice dont ce sont les colonnes~:
\begin{eqnarray*}
\left[\begin{array}{cccc}
1	& 1	& 1	& 1	\\
1	& 2	& 1	& 1	\\
0	& 0	& 1	& 2	\\
2	& 3	& 3	& 4	
\end{array}\right]
& \arr{\cdot T_{12}(-1)T_{13}(-1) T_{14}(-1)} & 
\left[\begin{array}{cccc}
1	& 0	& 0	& 0	\\
1	& 1	& 0	& 0	\\
0	& 0	& 1	& 2	\\
2	& 1	& 1	& 2	
\end{array}\right] \\
& \arr{\cdot T_{34}(-2) T_{21}(-1)} &
\left[\begin{array}{cccc}
1	& 0	& 0	& 0	\\
0	& 1	& 0	& 0	\\
0	& 0	& 1	& 0	\\
1	& 1	& 1	& 0
\end{array}\right] 
\end{eqnarray*}
Les trois colonnes non nulles de la derni\`ere matrice sont clairement
lin\'eairement ind\'ependantes.
Elle est donc de rang $3$ et $F+G$, le sous-espace
engendr\'e par les colonnes, est de dimension~$3$. On sait qu'on a
\[
\dim(F+G)=\dim F + \dim G - \dim (F\cap G).
\]
Donc $\dim(F\cap G)=1$.}
\item Exhiber une base de $F\cap G$ et des \'equations pour $F+G$.
\solution{Commen\c{c}ons par chercher des \'equations pour $F+G$. 
Soient $w_1, w_2, w_3$ les colonnes non nulles de la derni\`ere matrice du point
pr\'ec\'edent. On sait que $F+G$ est form\'e des combinaisons lin\'eaires
\[
\lambda_1 w_1 + \lambda_2 w_2 + \lambda_3 w_3 = 
\left[\begin{array}{c} \lambda_1 \\ \lambda_2 \\ \lambda_3 \\ \lambda_1+\lambda_2+\lambda_3 
\end{array}\right] \; .
\]
Clairement, un vecteur $v=(x_1, x_2, x_3, x_4)$ est de cette forme si et seulement si
\[
x_1 + x_2 + x_3 - x_4 =0.
\]
Ceci est donc l'\'equation recherch\'ee pour $F+G$. 

L'intersection $F\cap G$ est
form\'ee des vecteurs $\lambda_1 v_1 + \lambda_2 v_2$, $\lambda_1, \lambda_2\in\R$,
qui s'\'ecrivent aussi sous la forme $-\lambda_3 v_3  -\lambda_4 v_4$ pour des
$\lambda_3, \lambda_4\in \R$. Nous allons donc r\'esoudre le syst\`eme
homog\`ene
\[
\lambda_1 v_1 + \lambda_2 v_2 + \lambda_3 v_3 + \lambda_4 v_4=0.
\]
On sait que l'ensemble des solutions du syst\`eme homog\`ene ne change pas
lorsqu'on effectue des op\'erations \'el\'ementaires sur les lignes de sa
matrice. Simplifions donc le syst\`eme par des op\'erations \'el\'ementaires
sur les lignes~:
\begin{eqnarray*}
\left[\begin{array}{cccc}
1	& 1	& 1	& 1	\\
1	& 2	& 1	& 1	\\
0	& 0	& 1	& 2	\\
2	& 3	& 3	& 4 
\end{array} \right] 
& \arr{T_{21}(-1) T_{41}(-2) \cdot} &
\left[\begin{array}{cccc}
1	& 1	& 1	& 1	\\
0	& 1	& 0	& 0	\\
0	& 0	& 1	& 2	\\
0	& 1	& 1	& 2 
\end{array} \right]  \\
& \arr{T_{43}(-1) T_{13}(-1) T_{42}(-1) T_{12}(-1) \cdot} &
\left[\begin{array}{cccc}
1	& 0	& 0	& -1	\\
0	& 1	& 0	& 0	\\
0	& 0	& 1	& 2	\\
0	& 0	& 0	& 0 
\end{array} \right] 
\end{eqnarray*}
L'espace des solutions du syst\`eme est donc de dimension~$1$ (on le savait
d\'ej\`a car $\dim F\cap G=1$) et engendr\'e par le vecteur $(1,0,-2,1)$.
Donc l'intersection $F\cap G$ a pour base le vecteur
\[
v_1 = 2 v_3 - v_4.
\]
}
\end{list-of-exercises}



\tit{Exercice IV} 
Soit $E$ l'espace vectoriel des fonctions polynomiales nulles ou de degr\'e $\leq 6$.
Soit $f$ l'application lin\'eaire de $E$ dans $E$ qui, \`a une fonction
polynomiale $x \mapsto p(x)$, associe la fonction polynomiale $x \mapsto p(x+1)$.
\begin{list-of-exercises}
\item Quelle est la matrice de $A$ de $f$ dans la base $1, x, \ldots, x^6$ ?
\solution{Notons $p_0$ la fonction polynomiale $x\mapsto 1$, 
$p_1$ la fonction polynomiale $x\mapsto x$, et, plus g\'en\'eralement,
$p_j$ la fonction polynomiale $x\mapsto x^j$, pour $0\leq j\leq 6$.
Pour tout $0\leq j\leq 6$, l'application $f$ envoie la fonction polynomiale
$p_j$ sur la fonction $x\mapsto (x+1)^j$. Nous avons donc
\begin{eqnarray*}
(f(p_j))(x)& = & 1+ C^1_j x + C^2_j x^2 + \ldots + C^i_j x^i + \ldots + x^j \\
           & = & p_0 (x) + C^1_j p_1(x) + C^2_j p_2(x) + \ldots + C^i_j p_i(x) + \ldots +p_j(x).
\end{eqnarray*}
Ainsi, nous avons
\[
f(p_j) = p_0 + C^1_j p_1 + \ldots + C^i_j p_i + \ldots + p_j + 0\, p_{j+1} + \ldots + 0\, p_6 \; .
\]
En reportant ces coefficients dans la $(j+1)$-i\`eme colonne de la matrice 
nous obtenons
\[
A= \left[ \begin{array}{ccccccc}
1 & 1 & 1 & 1 & 1 & 1  & 1 \\
0 & 1 & 2 & 3 & 4 & 5  & 6 \\
0 & 0 & 1 & 3 & 6 & 10 & 15 \\
0 & 0 & 0 & 1 & 4 & 10 & 20 \\
0 & 0 & 0 & 0 & 1 & 5  & 15 \\
0 & 0 & 0 & 0 & 0 & 1  & 6  \\
0 & 0 & 0 & 0 & 0 & 0  & 1
\end{array} \right]
\]
}
\item Soit $n$ un entier. Calculer la puissance $A^n$. Indication~:
on pourra commencer par chercher l'application $f^n$.
\solution{Si $p$ est une fonction polynomiale, alors $f(p)$ est la fonction
$x\mapsto p(x+1)$, donc $f(f(p))$ est la fonction $x \mapsto p((x+1)+1)=p(x+2)$.

Plus g\'en\'eralement, pour $n\in \Z$, notons $T_n$ l'application qui, 
\`a la fonction polynomiale $x\mapsto p(x)$, associe $x\mapsto p(x+n)$, pour $n\in \Z$.
Montrons par r\'ecurrence que $f^n=T_n$ pour tout $n\geq 1$.
Nous savons d\'ej\`a que $f=T_1$ et $f^2 = T_2$. Supposons que l'affirmation est vraie 
pour $n$ et montrons-la pour $n+1$. En effet, nous avons
\[
f^{n+1}(p) = f(f^n(p)) = f(x \mapsto p(x+n))= (x \mapsto p((x+1)+n)) = (x\mapsto p(x+(n+1)))
= (T_{n+1}(p))(x).
\]
}
L'application $T_0$ est l'identit\'e, donc $T_0=f^0$. Pour $n\geq 0$, l'application
$T_{-n}$ est la r\'eciproque de $T_n=f^n$. Donc nous avons bien $T_{-n}=(f^n)^{-1}=f^{-n}$.
Nous obtenons finalement que $f^n=T_n$ pour tout $n\in\Z$.

Nous savons que la matrice $A^n$ est la matrice de $f^n=T_n$. Pour calculer la
matrice de $T^n$, nous utilisons le raisonnement du point pr\'ec\'edent et
l'identit\'e
\[
(n+x)^j = n^j + C^1_j n^{j-1} x + C^2_j n^{j-2} x^2 + \ldots + C^i_j n^{j-i} x^i + \ldots + x^j.
\]
Nous obtenons la matrice
\[
A^n = \left[ \begin{array}{ccccccc}
1	& n	& n^2	& n^3	& n^4	& n^5	& n^6 	\\
0	& 1	& 2n	& 3n^2	& 4n^3	& 5n^4	& 6 n^5 	\\
0 	& 0	& 1	& 3n	& 6n^2	& 10n^3	& 15 n^4	\\
0	& 0	& 0	& 1	& 4n	& 10n^2	& 20 n^3	\\
0	& 0	& 0	& 0	& 1	& 5n	& 15 n^2	\\
0	& 0	& 0	& 0	& 0	& 1	& 6 n	\\
0 	& 0 	& 0	& 0	& 0	& 0	& 1
\end{array} \right]
\]

\end{list-of-exercises}



\tit{Exercice V (facultatif)}
On d\'efinit la suite de Fibonacci par
\[
a_0=0\ko a_1=1\ko a_{n+1}=a_n+a_{n-1} \mbox{ pour tout } n\geq 1.
\]
\vspace*{-0.5cm}
\begin{list-of-exercises}
\item Calculer $a_0, \ldots, a_{10}$.
\solution{
On trouve le tableau
\begin{center}
\begin{tabular}{c|ccccccccccccc}
n     & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7  & 8  & 9  & 10 & 11  & 12  \\ \hline
$a_n$ & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89  & 144 
\end{tabular}
\end{center}
}
\item Soit la matrice
\[
A= \left[ \begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array} \right].
\]
Montrer que pour tout $n\geq 1$, on a
\[
A^n = \left[ \begin{array}{cc} a_{n-1} & a_{n} \\ a_{n} & a_{n+1} \end{array} \right].
\]
\solution{Proc\'edons par r\'ecurrence sur $n$. L'affirmation est visiblement
vraie pour $n=1$. Supposons qu'elle est vraie pour $n$ et montrons-la pour $n+1$.
Nous avons
\[
A^{n+1} = A A^{n} = 
\left[\begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array} \right] \,
\left[\begin{array}{cc} a_{n-1} & a_n \\ a_n & a_{n+1} \end{array} \right] =
\left[\begin{array}{cc} a_n & a_{n+1} \\ a_{n-1}+a_n & a_n+a_{n+1} \end{array} \right] =
\left[\begin{array}{cc} a_n & a_{n+1} \\ a_{n+1} & a_{n+2} \end{array} \right] \; .
\]
ce qui montre l'affirmation.
}
\item Calculer la valeur exacte de $A^{128}$ et de $a_{128}$. 
Indication~: le calcul peut se faire par 7 multiplications de matrices. 
\solution{Nous avons $A^{128} = (A^{64})^2$ et $A^{64}=(A^{32})^2$, \ldots , $A^4=(A^2)^2$.
Nous obtenons\footnote{en nous servant d'un logiciel de calcul formel}
\begin{align*}
& A^2 = \left[\begin{array}{cc} 1 & 1  \\ 1 & 2 \end{array} \right] \ko
A^4 = A^2\, A^2 =\left[\begin{array}{cc} 2 & 3 \\ 3 & 5 \end{array} \right] \ko
A^8 = A^4\, A^4 =\left[\begin{array}{cc} 13 & 21 \\ 21 & 34 \end{array} \right]
\\
& A^{16} = (A^8)^2=\left[\begin{array}{cc} 610 & 987 \\ 987 & 1597 \end{array} \right] \ko
A^{32} = (A^{16})^2=
\left[\begin{array}{cc} 
1346269 & 2179309 \\ 
2179309 & 3424578 
\end{array} \right] \ko
\\ &
A^{64} = \left[\begin{array}{cc}
6557470319842 & 10510209857723  \\
10510209857723  & 17167680177565 
\end{array} \right] \ko 
\\
& A^{128} = \left[\begin{array}{cc}
155576970220531065681649693 & 251728825683549488150424261 \\
251728825683549488150424261 & 407305795904080553832073954 
\end{array} \right].
\end{align*}
}

\item Un nombre entier $a$ est {\em divisible} par un nombre entier $b$ s'il existe
un nombre entier $c$ tel que $a=bc$. Soient $n,k\geq 1$ et $B$ une matrice $2\times 2$
\`a coefficients entiers. Montrer, par r\'ecurrence sur $k\geq 1$, que
le coefficient $(2,1)$ de la matrice $B^k$ 
est divisible par le coefficient $(2,1)$ de $B$. 
\solution{Clairement l'affirmation est vraie pour $k=1$. Supposons qu'elle
est vraie pour $k$ et montrons-la pour $k+1$. Notons $c_{ij}$ les coefficients
de la matrice $B^k$. Nous avons
\[
B^{k+1} = B B^k = 
\left[\begin{array}{cc} b_{11} & b_{12} \\ b_{21} & b_{22} \end{array} \right]\,
\left[\begin{array}{cc} c_{11} & c_{12} \\ c_{21} & c_{22} \end{array} \right].
\]
Le coefficient $(2,1)$ de la matrice $B^{k+1}$ est donc \'egal \`a
$b_{21} c_{11} + b_{22} c_{21}$. Par l'hypoth\`ese de r\'ecurrence, nous avons 
$c_{21}=b_{21} d$ pour un entier $d$. Donc le coefficient $(2,1)$ de $B^{k+1}$
est
\[
b_{21} c_{11} + b_{22} b_{21} d = b_{21} (c_{11} + d b_{22}).
\]
}
\item D\'eduire que $a_{kn}$ est
divisible par $a_n$ pour tout $k\geq 1$.
\solution{L'entier $a_{kn}$ est le coefficient $(2,1)$ de la matrice $A^{kn}=(A^n)^k$.
D'apr\`es le point pr\'ec\'edent, $a_{kn}$ est bien divisible par le
coefficient $(2,1)$ de la matrice $A^n$, qui n'est autre que $a_n$.}

\item Montrer que $a_n$ est le nombre de trajets de longueur
$n$ qui, dans le labyrinthe \`a sens uniques ci-dessous, m\`enent de $1$ \`a $2$.
Indication~: Soit $B(n)$ la matrice $2\times 2$ dont le coefficient $b(n)_{ij}$ est le 
nombre de chemins de $i$ \`a $j$ de longueur $n$. On pourra montrer que $B(n)=A^n$.
\[
\epsfbox{labyrinth.eps}
\]
\solution{Nous avons $B(1)=A$ et il est imm\'ediat de voir que le coefficient
$(i,j)$ de $A$ est le nombre de chemins de longueur $1$ de $i$ \`a $j$ dans le
labyrinthe. Supposons l'affirmation vraie pour $n$ et montrons-la pour $n+1$.
Tout chemin de longueur $n+1$ de $i$ vers $j$ est compos\'e d'un chemin de
longueur $n$ vers un sommet $k$ et d'un chemin de longueur $1$ de $k$ vers $j$.
Pour $k$, il n'y a que deux possibilit\'es, \`a savoir $1$ ou $2$. 
Ainsi le nombre de chemins de longueur $n+1$ allant de $i$ \`a $j$ est
\[
b(n)_{i1} a_{1j} + b(n)_{i2} a_{2j}.
\]
Ceci est exactement le coefficient $(i,j)$ de la matrice $B(n) A$.
Donc on a bien 
\[
B(n+1)=B(n) A = A^n A = A^{n+1}.
\]
}

%\item
%Montrer que pour tous $k,l\geq 0$, on a 
%\[
%a_k a_l + a_{k+1} a_{l+1} = a_{k+l}.
%\]
%Indication~: on pourra se servir du fait que $A^k \, A^l = A^{k+l}$.
\end{list-of-exercises}



\end{document}


\vspace*{-1cm}
\tit{Exercice VI}
Soit $E$ l'espace vectoriel des applications de $\N$ dans $\R$. Les
\'el\'ements de $E$ sont donc des suites $(u_n)$ de nombres r\'eels.
Soit $F\subset E$ l'ensemble des suites $(u_n)$ telles que
\[
u_{n+1}= u_{n}+u_{n-1} \mbox{ pour tout } n\geq 1.
\]
\vspace*{-0.5cm}
\begin{list-of-exercises}
\item Montrer que $F$ est un sous-espace vectoriel de $E$.
\item Montrer que l'application de $F$ dans $\R^2$ qui, \`a une
suite $(u_n)$, associe le couple $(u_0, u_1)$ est lin\'eaire
et bijective. Quelle est la dimension de $F$ ?
\item Soit $\lambda$ un nombre r\'eel. Montrer que la suite
$(\lambda^n)$ appartient \`a $F$ si et seulement si l'on
a $\lambda^2 =\lambda +1$. 
\item Montrer que l'\'equation $\lambda^2-\lambda-1=0$ admet
deux solutions r\'eelles distinctes $\lambda_1>\lambda_2$.
Montrer que les vecteurs $(1,\lambda_1)$ et $(1, \lambda_2)$ forment une
base de $\R^2$. D\'eduire que les suites $v_1=(\lambda_1^n)$ et
$v_2=(\lambda_2^n)$ forment une base de $F$.
\item Ecrire la suite de Fibonacci $w=(a_n)$ comme une combinaison lin\'eaire
$w= c_1 v_1 + c_2 v_2$ pour des scalaires $c_1, c_2$. D\'eduire une formule
explicite de la forme
\[
a_n = c_1 \lambda_1^n + c_2 \lambda_2^n.
\]
% \item Montrer que pour $n\geq 1$, $a_n$ est la partie enti\`ere
% du nombre r\'eel $c_1 \lambda_1^n$.







