%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[a4paper]{article}
\usepackage[a4paper, textwidth=17cm,textheight=24cm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\title{}
\author{}
\date{}

%%------------------------------------------------------------------------------
%% Packages

\usepackage{amsmath,amsfonts}
\usepackage{mathtools}
\usepackage[matha,mathb]{mathabx} % french mathematical symbols and more
\usepackage{amsthm}
\usepackage{geometry}
\usepackage[svgnames]{xcolor}
\usepackage{fancyhdr}
\usepackage{lastpage}
\usepackage{enumitem}

\usepackage{mdwlist}
\usepackage{hyperref}
\hypersetup{colorlinks=true,
  citecolor=DarkBlue,
  linkcolor=DarkBlue,
  linktoc=page,
  urlcolor=black,
}

\usepackage{tikz,tkz-tab,tkz-fct}
\usepackage[framemethod=tikz]{mdframed}
\usetikzlibrary{shadows,shadings}
\usepackage{calc}
\usetikzlibrary{shapes}
\usetikzlibrary{automata, positioning}

\usepackage[french]{babel}

%% ------------------------------------------------------------------------------
%% Packages setup

% enumitem
\setlist{itemsep=0pt, topsep=0pt} % vertical spacing for all lists
  
\newlist{pbenum}{enumerate}{10} % enumerate for problems (nested like so : 1., 1.1., 1.1.1., etc)
\setlist[pbenum]{label*=\arabic*.}
\setlist[pbenum, 1]{itemsep=4pt plus 2pt minus 1pt, topsep=8pt plus 2pt minus 4pt} % default enumerate spacing

\setlist[enumerate, 1]{label = \arabic*.} % standard enumerate labels 
\setlist[enumerate, 2]{label = \alph*.}

% geometry
%defaults : textwidth = 0.7\paperwidth = 1675.8pt, textheight = 0.7\paperheight = 4788pt

% hyperref
\hypersetup{colorlinks=true,
  citecolor=DarkBlue,
  linkcolor=DarkBlue,
  linktoc=page,
  urlcolor=black}

% fancyhdr
%% BUG: Do not issue \fancypagestyle{fancy}{<fancyhdr commands>}, the LaTeX compiler will hang at the first \pagestyle{fancy} call since it will enter in an infinite recursive loop.

%% \fancypagestyle{fancy}{%
%%   \fancyhf{} % clear all header and footer fields
%%   \lhead{École Normale Supérieure de Lyon\\Département de mathématiques}
%%   \rhead{2021--2022\\Option B pour l'agrégation}
%%   \rfoot{\thepage /\pageref{LastPage}}
%%   \renewcommand{\footrulewidth}{0.5pt}
%%   \setlength{\headheight}{24.2pt}} % required for headers spanning two lines

\fancypagestyle{plain}{%
  \fancyhf{}
  \rfoot{\thepage /\pageref{LastPage}}
  \renewcommand{\headrulewidth}{0pt}}

\pagestyle{fancy} % sets page style for the whole document
\fancyhf{} % clear all header and footer fields
\lhead{ENS de Lyon\\CPES Sciences}
\rhead{2022--2023\\Mathématiques}
\rfoot{\thepage /\pageref{LastPage}}
\renewcommand{\footrulewidth}{0.5pt}
\setlength{\headheight}{24.2pt} % required for headers spanning two lines

%%------------------------------------------------------------------------------
%% Custom environments/macros

\theoremstyle{definition}
\newtheorem*{defi}{Définition}

\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\e}{\mathrm{e}}
\newcommand{\mc}{\mathcal}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\I}[2]{\Io{#1,#2}\If}
\newcommand{\M}{\mathcal{M}}
\newcommand{\Io}{[\![}
\newcommand{\If}{]\!]}
\DeclareMathOperator{\0}{\mathbb{O}}
\newcommand{\ds}{\displaystyle}

\newcommand{\et}{\quad\text{et}\quad}
\newcommand{\ogfg}[1]{\og #1\fg}

\DeclarePairedDelimiter{\norm}{\lVert}{\rVert} %% requires mathtools
\DeclarePairedDelimiter{\abs}{\lvert}{\rvert}
\DeclarePairedDelimiter{\sbra}{[}{]}
\DeclarePairedDelimiter{\pare}{(}{)}
\DeclarePairedDelimiter{\osbral}{]}{]}
\DeclarePairedDelimiter{\osbra}{]}{[}
\DeclarePairedDelimiter{\osbrar}{[}{[}

\newcounter{exercice}

\newcommand{\ex}{\refstepcounter{exercice}\paragraph{Exercice \theexercice.}}
\newtheorem{exo}{Exercice}
\newcommand{\staritem}{\refstepcounter{enumi}\item[$(\star)~$\theenumi]}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Header

\begin{center}
  {\LARGE \bf Devoir en temps libre 8 : correction}
\end{center}
\bigskip

\begin{exo}\mbox{}
\begin{enumerate}[leftmargin=*]
\item \begin{enumerate}[leftmargin=4ex]
    \item 
\begin{verbatim}
def P(x):
    return x**3-6*x**2+3*x+1
\end{verbatim}
\item $P'= 3X^2-12X+3$. En posant la division de $P$ par $P'$ on obtient un reste $\boxed{R= -6X+3}$ et un quotient \framebox{$Q=\frac13X-\frac23$.}
\item On a $\forall x \in \R$, $P'(x) = 3x^2-12x +3 = 3(x^2-4x+1)$. Pour déterminer le signe de $P'$, on calcule ses racines à l'aide du discriminant ($\Delta = 4^2-4 = 12$): $f'$ admet deux racines réelles
$$x_1 = \frac{4 - \sqrt{12}}2 = 2-\sqrt{3}\quad \et \quad x_2 = \frac{4 + \sqrt{12}}2 = 2 + \sqrt{3}.$$
La fonction $P'$ est positive en dehors de ses racines (car son coefficient dominant est positif) et négative entre ses racines, on en déduit donc le tableau de variations suivant:
\begin{center}    
\begin{tikzpicture}
\tkzTab{ $x$ / 0.8, $P'(x)$ / 0.9, $P(x)$ / 1.4}
{$-\infty$, $x_1$, $x_2$, $+\infty$}{ ,+,z,-,z,+, }
{-/ $-\infty$ , +/$P(x_1)$, -/$P(x_2)$, + / $+\infty$}
\end{tikzpicture}
\end{center}
Les limites en $+\infty$ et $-\infty$ s'obtiennent avec $f(x) = x^3(1+ \cdots)$ où les termes $\cdots$ tendent vers $0$ en $\pm \infty$.

De plus $P(x_1) = Q(x_1)P'(x_1) + R(x_1) = R(x_1)$ car $x_1$ est une racine de $P'$, et de même pour $x_2$.

On obtient ainsi $P(x_1) = 6\sqrt{3}-9 = \sqrt{108}-\sqrt{81}>0$ et $P(x_2) = -6\sqrt{3}-9<0$.
\item 
D'après les questions précédentes, la fonction $P$ est \underline{strictement croissante} et \underline{continue} sur $]-\infty,x_1[$, donc elle réalise une \underline{bijection} de $]-\infty,x_1[$ vers l'intervalle $ ]-\infty, 6\sqrt{3}-9[$.

Comme $0\in \, ]-\infty,6 \sqrt{3}-9[$ (car $6\sqrt{3} = \sqrt{108}>\sqrt{81}=9$), \underline{il existe un unique antécédent de $0$ par $P$} dans l'intervalle $]-\infty, x_1[$ que l'on note $\alpha$. On a $P(\alpha)= 0$, c'est à dire $\alpha$ est une racine de $P$.

On fait le même raisonnement sur les deux autres intervalles pour montrer que $P$ admet une racine $\beta \in\, ]x_1,x_2[$ et une racine $\gamma\in\,]x_2,+\infty[$.

\end{enumerate}
\item \begin{enumerate}[leftmargin=4ex]
\item Comme $P$ tend vers $-\infty$ en $\-infty$ et $P(0)=1 >0$, $P$ admet au moins une racine strictement négative d'après le TVI, donc $\alpha<0$. Comme $P(0)=1>0$ et $P(1) = -1 <0$, et d'après le TVI, $P$ admet une racine entre $0$ et $1$ qui ne peut être que $\beta$, puisque $\gamma$ n'est pas dans l'intervalle $]0,1[$ (car $\gamma > x_2 > 1$). 
\item On part de l'encadrement donné à la question précédente.
On pose $a_0=0$ et $b_0=1$, et on a $f(a_0)>0$ et $f(b_0) <0$. On calcule l'image par $f$ du milieu de l'intervalle (pour avoir son signe) afin d'affiner l'encadrement:
\begin{itemize}
    \item $f\big(\frac{a_0+b_0}2\big) = f(\frac12) = \frac98 >0$. On pose donc $a_1=\frac{a_0+b_0}2 = \frac12$ et $b_1 = b_0=1$.
    \item $f\big(\frac{a_1+b_1}2\big) = f(\frac34) = \frac{19}{64} >0$. On pose donc $a_2 = \frac34$ et $b_2=b_1=1$.
\end{itemize}
On a $b_2-a_2 = \frac14$, donc on a atteint la précision souhaitée avec l'encadrement \framebox{$\frac34<\beta < 1$}.
\item La fonction $P$ a été définie pour \texttt{Python} à la question 1, on peut donc l'utiliser dans le code.
\begin{verbatim}
def dicho(epsilon):
    a=0;b=1
    while b-a > epsilon:
       c=(b+a)/2
        if P(a)*P(c)>0:
            a=c
        else:
        b=c
    return b
\end{verbatim}
\end{enumerate}
\item
\begin{enumerate}[leftmargin=4ex]
\item Soit $n\in \N$. On a
$$X_{n+1} = \begin{pmatrix} u_{n+3}\\u_{n+2}\\u_{n+1}\end{pmatrix}= \begin{pmatrix} 6u_{n+2}-3 u_{n+1}-u_n\\u_{n+2}\\u_{n+1}\end{pmatrix} = \begin{pmatrix}6&-3&-1\\1&0&0\\0&1&0\end{pmatrix} \begin{pmatrix} u_{n+2}\\u_{n+1}\\u_n\end{pmatrix} = A X_n \quad\text{ avec } \boxed{A = \begin{pmatrix}6&-3&-1\\1&0&0\\0&1&0\end{pmatrix}.}$$
\item ... par récurrence $X_n = A^n X_0$. Ensuite, comme $X_0= \begin{pmatrix}1\\0\\0\end{pmatrix}$, le produit $A^n X_0$ est la première colonne de $A^n$, et le coefficient de la troisième ligne de $X_n$, qui est donc la première colonne de $A^n$ est $u_n$.
\item On effectue les calculs matriciels $A^2 = A\times A$ et $A^3 = A^2 \times A$ ce qui donne
$$A^2= \begin{pmatrix}33&-19&-6\\6&-3&-1\\1&0&0\end{pmatrix} \qquad A^3= \begin{pmatrix}179&-105&-33\\33&-19&-6\\6&-3&-1\end{pmatrix} \qquad \et P(A) = A^3-6.A^2+3.A+I_3 = \0_3$$
\item Notons $R_n$ le reste de la division euclidienne de $X^n$ par $P$. On a $\deg(R_n) < \deg(P) = 3$, donc $R_n$ est de degré au plus 2, c'est à dire qu'il existe des réels $a_n$, $b_n$ et $c_n$ tels que $R_n = a_nX^2 + b_nX+c_n$.

En notant $Q$ le reste de cette division euclidienne puis en évaluant l'égalité entre polynômes $X^n = PQ+ R_n$ en $\alpha$, $\beta$ et $\gamma$, on obtient le système suivant :
$$\begin{cases}
\alpha^2 a_n+ \alpha b_n+c_n= \alpha^n\\ 
\beta^2 a_n + \beta b_n+c_n = \beta^n\\ 
\gamma^2 a_n+\gamma b_n+c_n = \gamma^n
\end{cases}$$
\item 
Maintenant, comme \underline{$P$ est un polynôme annulateur de $A$}, en évaluant l'égalité polynomiale $X^n = PQ +R_n$ en $X=A$, on obtient 
$$A^n = \underbrace{P(A)}_{=\0_3}Q(A) + R_n(A) = R_n(A) = a_n A^2+b_nA+c_n I_3.$$
Les coefficients de la 3ième ligne 1ère colonne de $A$ et $I_3$ sont nuls, donc
$A^n = \begin{pmatrix}*&*&*\\ *&*&*\\a_n&*&*\end{pmatrix}$ et ainsi $u_n = a_n$.
\item Pour tout $n\geqslant 1$,
$$\frac{u_{n+1}}{u_n} = \frac{\gamma^{n+1}(\beta-\alpha)+\beta^{n+1}(\alpha-\gamma)+\alpha^{n+1}(\gamma-\beta)}{\gamma^n(\beta-\alpha)+\beta^n(\alpha-\gamma)+\alpha^n(\gamma-\beta)} = \frac{\gamma(\beta-\alpha)+\beta\big(\frac{\beta}{\gamma}\big)^n(\alpha-\gamma)+\alpha\big(\frac{\alpha}{\gamma}\big)^n(\gamma-\beta)}{(\beta-\alpha)+\big(\frac{\beta}{\gamma}\big)^n(\alpha-\gamma)+\big(\frac{\alpha}{\gamma}\big)^n(\gamma-\beta)},$$
et $\lim\limits_{n\to + \infty} \big(\frac{\alpha}{\gamma}\big)^n = \lim\limits_{n\to + \infty} \big(\frac{\beta}{\gamma}\big)^n = 0$ car $\big|\frac{\alpha}{\gamma}\big| < 1 $ et $\big|\frac{\beta}{\gamma}\big| < 1 $. Ainsi, par opération sur les limites, on obtient
$$\lim_{n \to + \infty} \frac{u_{n+1}}{u_n} = \frac{\gamma(\beta-\alpha)}{\beta-\alpha} = \gamma.$$
\item
\begin{verbatim}
U=[0,0,1]
for k in range(2,20):
    U.append(6*U[k]-3*U[k-1]-U[k-2])
print(U[20]/U[19])
\end{verbatim}
\end{enumerate}
\item Le polynôme $P$ est unitaire de degré 3, et on a justifié à la question 1 qu'il admet trois racines réelles distinctes $\alpha < \beta < \gamma$. Ces racines sont de multiplicité 1 (car la somme des multiplicités de ne doit pas dépasser 3), et on en déduit donc la forme factorisée suivante:
$$\boxed{P=(X-\alpha)(X-\beta)(X-\gamma).}$$
En redéveloppant, on obtient $P= X^3 - (\alpha+\beta+\gamma)X^2 + (\alpha\beta+\alpha\gamma+\beta\gamma)X - \alpha\beta\gamma$, puis en identifiant les coefficients devant $X^2$ avec la définition de $P$, on obtient $\alpha+\beta+\gamma = 6$.

{\small \emph{Remarque.} D'une manière général, lorsqu'on écrit la forme factorisée d'un polynôme à l'aide de ses racines (et de leur multiplicité) et que l'on développe, on obtient des relations entre les coefficients du polynômes et les racines du polynômes. Par exemple, le terme constant d'un polynôme est, au signe près, le produit de toutes ses racines.}
\item On a donc 
$$\alpha = 6-\beta - \gamma \approx 6 -0,81521-5,41147 = 6 - 6,22668 \;\boxed{= -0,22668.}$$
\end{enumerate}
\end{exo}

\end{document}

\end{document}