%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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[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{\Io}{[\![}
\newcommand{\If}{]\!]}

\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

\renewcommand\labelitemi{$\bullet$}
\begin{center}
  {\LARGE \bf Corrigé du devoir en temps libre 2}\\[4pt]
\end{center}



\begin{exo}
\begin{enumerate}
\item Pour $p\in\N$, la négation de ${\cal P}(p)$ est \underline{\ogfg{$\forall k\in \N$, $2^p-2 \neq kp$}}, autrement dit \ogfg{$2^p-2$ n'est pas un multiple de $p$}.
\item Pour $p=2$, $2^p-2 = 2 = kp$ avec $k=1$ donc il existe $k\in \N$ tel que $2^p-2=kp$ et \underline{${\cal P}(2)$ est vraie}.

Pour $p=3$, $2^p-2 = 6 = kp$ avec $k=2$ donc il existe $k\in \N$ tel que $2^p-2=kp$ et \underline{${\cal P}(3)$ est vraie}.

Pour $p=5$, $2^p-2 = 30 = kp$ avec $k=6$ donc il existe $k\in \N$ tel que $2^p-2=kp$ et \underline{${\cal P}(5)$ est vraie}.

Pour $p=4$, $2^p-2=14$ n'est pas un multiple de $4$, donc \underline{${\cal P}(4)$ est fausse}.

\item Si $p=7$, $2^p-2=126=kp$ avec $k=18$, donc \underline{${\cal P}(7)$ est vraie}.

\item Pour $p\in \N$, on considère l'implication : $  $\ogfg{$p$ est un nombre premier $\Longrightarrow$ ${\cal P}(p)$ }. \begin{itemize}
    \item La négation de cette implication est \underline{\ogfg{$p$ est un nombre premier et ${\cal P}(p)$ est fausse.}}.
    \item La contraposée de cette implication est \underline{\ogfg{ non(${\cal P}(p)$)  $\Longrightarrow$ $p$ n'est pas un nombre premier}}.
    \item La réciproque de cette implication est \underline{\ogfg{ ${\cal P}(p)$  $\Longrightarrow$ $p$ est un nombre premier}}.
\end{itemize}
\item L'implication est supposée vraie, donc sa contraposée est également vraie. 
\begin{itemize}
    \item En écrivant la contraposée pour $p=143$, de \ogfg{${\cal P}(143)$ est fausse} on déduit que \underline{$143$ n'est pas premier}.
    \item De \ogfg{$137$ est un nombre premier}, on déduit \underline{${\cal P}(137)$} en appliquant l'implication à $p=137$.
    \item De \ogfg{${\cal P}(163)$ est vraie}, \underline{on ne peut rien déduire}.
\end{itemize}
\item  Soit $p\in\N$. L'implication peut se lire :\begin{itemize}
    \item \ogfg{Si $p$ est un nombre premier, alors ${\cal P}(p)$ est vérifiée}.
    \item \ogfg{Il est nécessaire que ${\cal P}(p)$ soit vérifiée pour que $p$ soit un nombre premier}.
    \item \ogfg{Il suffit que $p$ soit un nombre premier pour que ${\cal P}(p)$ soit vérifiée}. 
\end{itemize}
\end{enumerate}
\end{exo}
\begin{exo} 
\begin{enumerate}
    \item \begin{itemize}
        \item Le couple d'entiers naturels \underline{$(1,2)$ appartient à $A$} car $(1,2)$ s'écrit $(k,2k)$ pour l'entier $k=1 \in \N$.
        \item Le couple d'entiers naturels \underline{$(3,5)$ appartient à $B$} car ses coordonnées vérifient l'inéquation $3+5 \leq 10$.
        \item Le couple d'entiers naturels \underline{$(3,9)$ appartient à $C$} car  $10\times 3 +9=39 =3n$ avec $n=13 \in \N$.
    \end{itemize}
        \item Le couple d'entiers naturels $(3,6)$ appartient aux trois ensembles : en effet $(3,6)=(k,2k)$ pour $k=3$, $3+6 \leq 10$ et $10 \times 3 + 6 = 3n$ avec $n=12$. Donc
        \framebox{$\ds (3,6) \in A \cap B \cap C$}.\\
        Le couple d'entiers naturels $(10,20)$ appartient à $A$ (avec $k=10$) mais pas à $B$ (car $10 + 20 > 10$), donc \framebox{$\ds (10,20) \in A \cap \overline{B}$}.
    \item Soit $k\in \N$. Un élément $(k,2k)$ de $A$ est dans $B$ si et seulement si $k+ 2k \leq 10$, c'est-à-dire si et seulement si $k\leq 10/3$.
 On a donc
    \[\boxed{A \cap B = \big\{(k,2k)\,;\,k\in \I{0}{3}\big\}=\{(0,0), (1,2), (2,4), (3,6)\} \subset \N^2}\]
     \item Montrons que $A \subset C$. Soit $a \in A$. Il existe $k\in \N$ tel que $a=(k,2k)$. Alors comme $10\times k + 2k = 12k=3n$, avec $n=4k\in \N$, $a$ appartient aussi à $C$. On a donc montré que \underline{$A \subset C$}.
    
    On a vu que le couple $(3,9)$ est dans $C$, et il n'est pas dans $A$ puisque $9\neq 2\times 3$ ;\\ \underline{l'inclusion réciproque $C \subset A$ est donc fausse}.
\end{enumerate}
\end{exo}
\begin{exo}
[Suite de Sylvester] On définit la suite $(s_n)_{n\in \N}$ par $s_0=2$ et pour tout $n\in \N$, $\ds s_{n+1}= 1+ \prod_{k=0}^n s_k$.
\begin{enumerate}
    \item \begin{enumerate}
    \item On calcule
    \[s_1= 1 + \prod_{k=0}^0 s_k=1+ s_0 = \boxed{3},\,\; s_2 =1+\prod_{k=0}^1 s_k=1 + s_0s_1=\boxed{7},\,\; s_3= 1+\prod_{k=0}^2 s_k=1+s_0s_1s_2=\boxed{43}. \]
    \item Montrons que pour $n\in \N$, $s_{n+1} = 1+(s_n-1)s_n$. Pour $n=0$, on a $s_1=3=1+(2-1)\times 2$. Soit $n\geq 1$, on peut écrire
    \[s_{n+1}= 1 + \prod_{k=0}^n s_k = 1+ s_n\prod_{k=0}^{n-1}s_k,\]
    or comme $n\geq 1$, $\ds s_n=1 + \prod_{k=0}^{n-1}s_k$ donc $\ds \prod_{k=0}^{n-1}s_k=s_n-1$, et en injectant dans ce qui précède on obtient le résultat voulu : 
    $\boxed{s_{n+1}= 1+s_n(s_n-1)}$.
    \item Pour tout $n\in \N$, on note ${\cal P}(n)$ la proposition \ogfg{$s_n \geqslant n! +1$}. 
    
    \emph{Initialisation :} pour $n=0$, on a bien $s_0= 2 \geq 0!+1 =2$, donc \underline{${\cal P}(0)$ est vérifiée}.
    
    \emph{Hérédité :} \underline{on suppose que ${\cal P}(n)$ est vraie} pour un certain $n\in \N$ et on va montrer que ${\cal P}(n+1)$ est alors aussi vraie. Comme ${\cal P}(n)$ est vraie, en particulier on a $s_n -1 \geq n!$, et par ailleurs $s_n$ est strictement positif. On en déduit donc les inégalités suivantes, en appliquant l'hypothèse de récurrence successivement à chacun des deux termes $s_n$, avec des facteurs strictement positifs : 
    \[s_{n+1} \underset{\textrm{1.b.}}{=} 1 + (s_n-1)s_n\underset{(HR)}{\geq} 1 + n!s_n\underset{(HR)}{\geq}1 + n!(n!+1) \geq  1 + n!(n+1) = 1+(n+1)! \]
    La dernière inégalité vient du fait que $n! \geq n$ pour tout $n\in \N$.
    On a donc démontré $\underline{{\cal P}(n+1)}$.

	\emph{Conclusion :} On a montré que ${\cal P}(0)$ est vraie et que $\left({\cal P}(n) \implies {\cal P}(n+1)\right)$ pour tout $n\in \N$. Par récurrence, \underline{la proposition ${\cal P}(n)$ est donc vraie pour tout $n\in \N$}.
    \item Montrons d'abord que pour tout $n\geq 4$, on a $2^n\leq n!$. On procède par une récurrence express : 
    \begin{itemize}
        \item c'est vrai en $n=4$.
        \item si $2^n \leq n!$ pour un certain $n\geq 2$, alors $2^{n+1}=2\times 2^n \leq 2 n! \leq (n+1)n! \leq (n+1)!$ puisque $n+1\geq 5 \geq 2$.
    \end{itemize}
    On a donc prouvé par récurrence que  $2^n\leq n!$ pour tout $n\geq 4$.
    
    La question précédente nous donne que pour tout $n\in \N$, $s_n \geq n!+1$, et comme ces quantités sont strictement positives on a l'inégalité renversée pour les inverses : $\frac1{s_n}\leq \frac1{n!+1}$.
    Par conséquent, étant donné que $2^n >0$ pour tout $n\in \N$, on obtient grâce à ce qui précède (et au fait que $n!+1 >0$) que 
    \[\forall n \geq 4,a \quad \frac{2^n}{s_n} \leq \frac{2^n}{n!+1}\leq \frac{n!}{n!+1} \leq 1. \]
    La suite $\left(\frac{2^n}{s_n}\right)_{n\in\N}$ est strictement positive donc minorée par $0$, et majorée à partir du cinquième terme, donc elle est \underline{bornée}.
    \emph{On pourrait remarquer que la suite est majorée par $1$ en calculant ses premiers termes mais ça n'est pas nécessaire, car les suites bornées à partir d'un certain rang sont bornées.}
    \end{enumerate}
    \item Pour $n\in \N$, on note $\ds T_n= \sum_{k=0}^n \frac1{s_k}$.
    \begin{enumerate}
        \item Comme $\left(\frac{2^n}{s_n}\right)$ est bornée, en particulier il existe un majorant réel $M$, forcément positif, tel que pour tout $n\in \N$, $\ds \frac{2^n}{s_n} \leq M$, autrement dit $\ds \frac{1}{s_n}\leq \frac M {2^n}$. On peut majorer la somme $T_n$ terme à terme : pour tout $n\in \N$,
        \[ T_n= \sum_{k=0}^n \frac1{s_k} \leq \sum_{k=0}^n \frac{M}{2^k}= M \sum_{k=0}^n \left(\frac12\right)^k= M\frac{1-\left(\frac12\right)^{n+1}}{1-\frac12}=\frac M2-\frac M2 \left(\frac12\right)^{n+1} \leq \frac M2. \]
        Comme $\frac M2$ est indépendant de $n$, on a montré que \underline{$(T_n)_{n\in \N}$ est une suite majorée}.
        \item D'après la question 1.b., pour $k\in \N$, on a $s_{k+1}-1 = s_k(s_k-1)$.
        Donc en divisant par $(s_{k+1}-1 )(s_k-1)$ (c'est non nul !), on obtient
        \[ \frac{1}{s_k-1} = \frac{s_k}{s_{k+1}-1} = \frac{1}{s_{k+1}-1} + \frac{s_k-1}{s_{k+1}-1},\]
        et par conséquent, on trouve en appliquant à nouveau la question 1.b. :
        \[ \frac{1}{s_k-1}-\frac{1}{s_{k+1}-1}  = \frac{s_k-1}{s_{k+1}-1} = \boxed{\frac1{s_k}}.\]

        \item On fait donc apparaître une somme télescopique : si $n\in \N$,
        \[T_n = \sum_{k=0}^n \frac1{s_k} = \sum_{k=0}^n \frac{1}{s_k-1}-\frac{1}{s_{k+1}-1} = \frac{1}{s_0-1} -\frac{1}{s_{n+1}-1}=\boxed{1 - \frac1{s_{n+1}-1}}. \]
    \end{enumerate}
        \staritem Comme pour tout $n\in \N$, $s_n\geq n!+1$, par croissance comparée $(s_n)$ tend vers $+\infty$ et par conséquent $\ds \frac1{s_{n+1}-1} \underset{n\to +\infty}{\to} 0$. On montre donc, en sommant les limites dans l'expression précédente, que \underline{$(T_n)$ converge vers $1$}.
\end{enumerate}
\end{exo}\bigskip

\end{document}