% !TEX TS-program = LuaLaTeX

\renewcommand{\theprop}{(\ensuremath{\fnsymbol{prop}})}

\tgotitle{Raisonnement par récurrence}
%
\section{Une propriété des entiers naturels}
La propriété énoncée dans cette section est parfois présentée comme un axiome. Il n'entre toutefois pas dans nos intentions de construire une ou des axiomatiques, ne serait-ce que parce que cette notion est délicate. On se contentera donc d'un point de vue naïf, selon lequel un axiome est un énoncé dont on admet qu'il est vrai. Le lecteur doit toutefois savoir que les énoncés de la propriété~\ref{propppe} et du théorème~\ref{threc} ont des rôles en quelque sorte interchangeables : dans les axiomatiques classiques permettant de fonder l'arithmétique, prendre l'un comme axiome permet de démontrer l'autre comme théorème. Pour cette raison, le lecteur pourra trouver ailleurs des présentations proposant un axiome (ou parfois un principe) de \emph{récurrence}, la propriété~\ref{propppe} devenant alors un théorème.
\par
\vspace{0.5\baselineskip}\par
Nous supposons donc connu l'ensemble $\N$ des entiers naturels, muni notamment d'une relation d'ordre notée ${≤}$ et nous admettons que cet ensemble  possède la propriété suivante:
%
\begin{prop}
Toute partie non vide de $\N$ possède un plus petit élément.\label{propppe}
\end{prop}

On traduit souvent cette propriété en disant que \N{} est \emph{bien ordonné}.
%x
%\par\noindent{\color{gray}\rule{\linewidth}{5pt}}\par\addvspace{-3pt}\par\nobreak

%Cette propriété peut être considérée comme un des axiomes qui permettent de décrire l'ensemble \N{} des entiers naturels. Elle peut également se démontrer à partir d'un autre système d'axiomes, de portée équivalente (axiomes de Peano, notamment) ou de portée plus générale (Zermelo-Fraenkel, par exemple).

%\par\noindent\hrulefill
\section{Récurrence}
\subsection{Introduction}
\label{secexplerec}
La propriété \ref{propppe} permet de formaliser une méthode consistant à établir la validité d'une assertion \frquote{de proche en proche}. Fixons-nous par exemple un réel $a$ strictement positif et, pour tout entier naturel $n$, considérons la propriété $P(n)$
\[(1+a)^n\geq 1+na.\]

Nous nous proposons de démontrer que cette propriété est vraie pour tout entier naturel~$n$.

Prouvons dans un premier temps que $P(0)$ est vraie (\mbox{c.-à-d.} que si $n=0$ alors $P(n)$ est vraie) : puisqu'il est vrai que $(1+a)^0=1$ et $1+0\times a=1$, il est établi que $(1+a)^0\geq1+0\times a$, donc que $P(0)$ est vraie.

Donnons-nous alors un entier naturel $n$ et supposons que $P(n)$ est vraie. Prouvons alors que nécessairement $P(n+1)$ est vraie :
\begin{align*}
(1+a)^n&\geq1+na,\\
\intertext{soit, en multipliant les deux membres par $1+a$, qui est strictement positif,}
(1+a)^{n+1}&\geq(1+a)(1+na),\\
\intertext{d'où}
(1+a)^{n+1}&\geq 1+(n+1)a+na^2,\\
\intertext{et enfin}
(1+a)^{n+1}&\geq 1+(n+1)a,\quad \text{car $na^2\geq0$.}
\end{align*}

Nous venons d'établir que, pour tout entier naturel $n$, si $P(n)$ est vraie alors $P(n+1)$ est vraie. En termes plus formels :
\begin{equation}
\forall n\in\N,\; P(n)\implies P(n+1).
\label{eqhered}
\end{equation}

Nous notons maintenant $\symcal{A}$ l'ensemble des valeurs de l'entier naturel $n$ pour lesquelles $P(n)$ \emph{est fausse}. Nous allons prouver \emph{par l'absurde} que $\symcal{A}$ est vide, autrement dit que $P(n)$ est vraie pour tout entier naturel $n$. 

Supposons donc que $\symcal{A}$ est non vide. En vertu de la propriété \ref{propppe}, $\symcal{A}$ possède un plus petit élément que nous notons $m$. Puisque $P(0)$ est vraie, on peut affirmer que $0\notin\symcal{A}$ donc que $m>0$, ce qui nous assure que $m-1\in\N$. Le fait que $m-1<m$ nous prouve maintenant que $m-1\notin\symcal{A}$, puisque $m$ est le plus petit élément de $\symcal{A}$. Alors $P(m-1)$ est vraie, ce qui entraîne, d'après la proposition \eqref{eqhered}, que $P(m)$ est vraie également. L'entier $m$ étant élément de $\symcal{A}$ on aboutit à une contradiction. Finalement $\symcal{A}$ est vide et la propriété $P(n)$ est vraie pour tout entier $n$.

\begin{remark}
On traduit la proposition \eqref{eqhered} en disant que la propriété $P$ est \emph{héréditaire} à partir du rang $0$.
\end{remark}

\subsection{Un théorème}
Nous souhaitons maintenant nous éviter le recours direct à la propriété \ref{propppe}, et en particulier un raisonnement par l'absurde nécessitant l'introduction un peu lourde d'une partie telle que $\symcal{A}$. Nous souhaitons également pouvoir facilement établir qu'une propriété est vraie non pas sur \N{} tout entier, mais plutôt pour tout entier supérieur à un entier $n_0$ donné. À cet effet nous formulons maintenant le \emph{théorème de récurrence}, dont la démonstration ne sera pas très différente de celle qui a été faite sur l'exemple de la section \ref{secexplerec}.
\begin{thm}
Soit un entier $n_0$ fixé et une propriété $P(n)$ dont l'énoncé dépend d'un entier $n$. Si $P(n_0)$ est vraie et si pour tout entier $n$ supérieur à $n_0$ l'implication
\[P(n)\implies P(n+1)\]
est vraie, alors la propriété $P(n)$ est vraie pour tout entier $n$ supérieur à $n_0$.
\label{threc}
\end{thm}
\begin{proof}Considérons une propriété $P(n)$ vérifiant les hypothèses de notre théorème et montrons alors que $P(n)$ est vraie pour tout entier $n\geq n_0$. 
Nous noterons $\symcal{A}$ l'ensemble des entiers naturels $k$ pour lesquels que $P(n_0+k)$ est fausse. Le fait que $P(n_0)$ est vrai se traduit par 
\[
0\notin\symcal{A}
\]
 et plus généralement, pour $n≥n_0$, en remarquant que $n$ peut s'écrire $n_0+(n-n_0)$,
  \frquote{$P(n)$ est vrai} se traduit par $(n-n_0)\notin\symcal{A}$. 
 En posant $k=n-n_0$, l'hypothèse 
 \begin{align}
 \forall n≥n_0,\; P(n)&\implies P(n+1)\notag\\
 \intertext{nous assure donc que}
 \forall k\in\N,\;k\notin\symcal{A}&\implies(k+1)\notin\symcal{A}. \label{eqheredA}
 \end{align}
 
Prouver que la propriété $P(n)$ est vraie pour tout entier $n$ supérieur à $n_0$ revient à prouver que $\symcal{A}$ est vide. Raisonnons par l'absurde et supposons que $\symcal{A}$ est non vide : en vertu de la propriété \ref{propppe}, $\symcal{A}$ possède alors un plus petit élément que nous notons~$m$. Nous savons que $m>0$, puisque $0\notin\symcal{A}$, et cela nous assure que $m-1\in\N$. Le fait que $m-1<m$ nous prouve maintenant que $m-1\notin\symcal{A}$, puisque $m$ est le plus petit élément de $\symcal{A}$. Alors d'après la proposition \eqref{eqheredA}, $m\notin\symcal{A}$, ce qui est en contradiction avec le fait que $m$ est le plus petit élément de $\symcal{A}$. Il est alors établi que la propriété $P(n)$ est vraie pour tout $n≥n_0$.
 \end{proof}
%
\begin{remark}
Un raisonnement par récurrence consiste donc à appliquer le théorème \ref{threc} pour démontrer qu'une propriété $P(n)$ est vraie pour tout entier $n$ supérieur à un certain entier $n_0$. Il se fait en trois étapes qui doivent, pour la clarté du propos, être suffisamment mises en évidence.
\begin{enumerate}
\item \textit{Initialisation :} on établit que $P(n_0)$ est vraie.
\item \textit{Preuve du caractère héréditaire de la propriété :} on démontre que 
\[
\forall n≥n_0,\; P(n)\implies P(n+1).
\]
\item \textit{Conclusion :} on a ainsi établi par récurrence que $P(n)$ est vraie pour tout $n≥n_0$.
\end{enumerate}
\end{remark}

\subsection{Applications et exemples}

\subsubsection{Une somme}
On se propose de démontrer par récurrence que la somme $S_n$ des $n$ premiers entiers non nuls est égale à $n(n+1)/2$. Par définition on a donc
\[
S_n=\sum_{k=1}^n k\;\text{ ou si l'on préfère }\;  S_n=1+2+\cdots+n-1+n.
\]
On veut démontrer par récurrence que la propriété $P(n)$, définie par 
\[
S_n=\frac{n(n+1)}{2}\;,
\]
est vraie pour tout $n≥1$.
\begin{enumerate}
\item \textit{Initialisation :} on a $S_1=1$ et pour $n=1$, $n(n+1)/2=2/2=1$. Donc $P(1)$ est vraie.
\item \textit{Hérédité :} donnons nous un entier $n≥1$ et supposons que $P(n)$ est vraie. 
Montrons alors que $P(n+1)$ est vraie c'est à dire que $S_{n+1}=((n+1)(n+2))/2$.
On sait que $S_{n+1}=S_{n}+n+1$, donc
\begin{align*}
S_{n+1}&=\frac{n(n+1)}{2}+n+1,\\
&=\frac{n(n+1)+2(n+1)}{2}\;,\\
&=\frac{(n+1)(n+2)}{2}\:.
\end{align*}
On vient d'établir que $\forall n≥1,\;P(n)\implies P(n+1)$. La propriété $P(n)$ est donc héréditaire à partir du rang $1$.
\item \textit{Conclusion :} la propriété $P(n)$ est vraie pour tout $n≥1$.
\[
\forall n≥1,\;S_n=\frac{n(n+1)}{2}\:.
\]
\end{enumerate}

\subsubsection{Une autre somme}
On se propose cette fois de démontrer par récurrence que la somme $T_n$ des carrés des $n$ premiers entiers non nuls est égale à $\bigl(n(n+1)(2n+1)\bigr)/6$. Par définition on a donc
\[
T_n=\sum_{k=1}^n k^2\;\text{ ou si l'on préfère }\;  T_n=1^2+2^2+\cdots+(n-1)^2+n^2.
\]
On veut démontrer par récurrence que la propriété $P(n)$, définie par
\[
T_n=\frac{n(n+1)(2n+1)}{6}\;,
\]
est vraie pour tout $n≥1$.
\begin{enumerate}
\item \textit{Initialisation :} on a $T_1=1$ et pour $n=1$, 
\[\frac{n(n+1)(2n+1)}{6}=\frac{2\times3}{6}=1.\]
 Donc $P(1)$ est vraie.
\item \textit{Hérédité :} donnons nous un entier $n≥1$ et supposons que $P(n)$ est vraie. 
Montrons alors que $P(n+1)$ est vraie c'est à dire que 
\begin{align*}
T_{n+1}&=\frac{(n+1)\bigl((n+1)+1)(2(n+1)+1\bigr)}{6}\;,\\
&=\frac{(n+1)(n+2)(2n+3)}{6}\:.
\end{align*}
On sait que $T_{n+1}=T_{n}+(n+1)^2$, donc
\begin{align*}
T_{n+1}&=\frac{n(n+1)(2n+1)}{6}+(n+1)^2,\\
&=\frac{n(n+1)(2n+1)+6(n+1)(n+1)}{6}\;,\\
\intertext{soit, en factorisant $n+1$}
T_{n+1}&=\frac{(n+1)\bigl(n(2n+1)+6(n+1)\bigr)}{6}\;,\\
&=\frac{(n+1)(2n^2+n+6n+6)}{6}\;.\\
\intertext{On remarque alors que $n+6n=7n$, que l'on peut aussi écrire $3n+4n$ d'où}
T_{n+1}&=\frac{(n+1)(2n^2+3n+4n+6)}{6}\;,\\
&=\frac{(n+1)\bigl(n(2n+3)+2(2n+3)\bigr)}{6}\;,\\
&=\frac{(n+1)(n+2)(2n+3)}{6}\:.
\end{align*}
On vient d'établir que $\forall n≥1,\;P(n)\implies P(n+1)$. La propriété $P(n)$ est donc héréditaire à partir du rang $1$.
\item \textit{Conclusion :} la propriété $P(n)$ est vraie pour tout $n≥1$.
\[
\forall n≥1,\;T_n=\frac{n(n+1)(2n+1)}{6}\:.
\]
\end{enumerate}

\subsubsection{Divisibilité}
Démontrer par récurrence que, pour tout entier naturel $n$, $n^3+2n$ est un multiple de $3$.
On veut démontrer par récurrence que la propriété $P(n)$, définie par
\[
\exists\, k\in\N \text{ tel que }n^3+2n=3k,
\]
est vraie pour tout $n≥0$.
\begin{enumerate}
\item \textit{Initialisation :} Si $n=0$, $n^3+2n=0$ qui s'écrit aussi $3\times0$. Donc $P(0)$ est vraie.
\item \textit{Hérédité :} Donnons nous un entier naturel $n$ et supposons que $P(n)$ est vraie. Montrons alors que $P(n+1)$ est vraie, c.-à-d. que $(n+1)^3+2(n+1)$ est divisible par~$3$.
\begin{align*}
(n+1)^3+2(n+1)&=n^3+3n^2+3n+1+2n+2,\\
&=(n^3+2n)+3(n^2+n+1).
\end{align*}
L'hypothèse de récurrence nous dit que $P(n)$ est vraie, donc qu'il existe un entier $k$ tel que \mbox{$n^3+2n=3k$}. Alors
\[(n+1)^3+2(n+1)=3(k+n^2+n+1),\]
Ce qui prouve que $(n+1)^3+2(n+1)$ est un multiple de 3.

On vient d'établir que $\forall n\in\N,\;P(n)\implies P(n+1)$. La propriété $P(n)$ est donc héréditaire à partir du rang $0$.
\item \textit{Conclusion :} la propriété $P(n)$ est vraie pour tout $n\in\N$. 
\[
\forall n\in\N,\; n^3+2n \text{ est divisible par $3$.}
\]
\end{enumerate}

\endinput