<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">% !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 Ã&nbsp; 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 Ã&nbsp; Ã©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.-Ã&nbsp;-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&amp;\geq1+na,\\
\intertext{soit, en multipliant les deux membres par $1+a$, qui est strictement positif,}
(1+a)^{n+1}&amp;\geq(1+a)(1+na),\\
\intertext{d'oÃ¹}
(1+a)^{n+1}&amp;\geq 1+(n+1)a+na^2,\\
\intertext{et enfin}
(1+a)^{n+1}&amp;\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Ã©Â&nbsp;\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&gt;0$, ce qui nous assure que $m-1\in\N$. Le fait que $m-1&lt;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Â&nbsp;\eqref{eqhered}, que $P(m)$ est vraie Ã©galement. L'entier $m$ Ã©tant Ã©lÃ©ment de $\symcal{A}$ on aboutit Ã&nbsp; 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Â&nbsp;\eqref{eqhered} en disant que la propriÃ©tÃ© $P$ est \emph{hÃ©rÃ©ditaire} Ã&nbsp; partir du rang $0$.
\end{remark}

\subsection{Un thÃ©orÃ¨me}
Nous souhaitons maintenant nous Ã©viter le recours direct Ã&nbsp; 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 Ã&nbsp; 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Â&nbsp;\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 Ã&nbsp; $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 Ã&nbsp; $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)&amp;\implies P(n+1)\notag\\
 \intertext{nous assure donc que}
 \forall k\in\N,\;k\notin\symcal{A}&amp;\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 Ã&nbsp; $n_0$ revient Ã&nbsp; prouver que $\symcal{A}$ est vide. Raisonnons par l'absurde et supposons que $\symcal{A}$ est non vide : en vertu de la propriÃ©tÃ©Â&nbsp;\ref{propppe}, $\symcal{A}$ possÃ¨de alors un plus petit Ã©lÃ©ment que nous notons~$m$. Nous savons que $m&gt;0$, puisque $0\notin\symcal{A}$, et cela nous assure que $m-1\in\N$. Le fait que $m-1&lt;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Â&nbsp;\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 Ã&nbsp; appliquer le thÃ©orÃ¨meÂ&nbsp;\ref{threc} pour dÃ©montrer qu'une propriÃ©tÃ© $P(n)$ est vraie pour tout entier $n$ supÃ©rieur Ã&nbsp; 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 Ã&nbsp; $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 Ã&nbsp; 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}&amp;=\frac{n(n+1)}{2}+n+1,\\
&amp;=\frac{n(n+1)+2(n+1)}{2}\;,\\
&amp;=\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 Ã&nbsp; 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 Ã&nbsp; $\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 Ã&nbsp; dire que 
\begin{align*}
T_{n+1}&amp;=\frac{(n+1)\bigl((n+1)+1)(2(n+1)+1\bigr)}{6}\;,\\
&amp;=\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}&amp;=\frac{n(n+1)(2n+1)}{6}+(n+1)^2,\\
&amp;=\frac{n(n+1)(2n+1)+6(n+1)(n+1)}{6}\;,\\
\intertext{soit, en factorisant $n+1$}
T_{n+1}&amp;=\frac{(n+1)\bigl(n(2n+1)+6(n+1)\bigr)}{6}\;,\\
&amp;=\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}&amp;=\frac{(n+1)(2n^2+3n+4n+6)}{6}\;,\\
&amp;=\frac{(n+1)\bigl(n(2n+3)+2(2n+3)\bigr)}{6}\;,\\
&amp;=\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 Ã&nbsp; 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.-Ã&nbsp;-d. que $(n+1)^3+2(n+1)$ est divisible par~$3$.
\begin{align*}
(n+1)^3+2(n+1)&amp;=n^3+3n^2+3n+1+2n+2,\\
&amp;=(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 Ã&nbsp; 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
</pre></body></html>