Récurrence
Avec les outils de logique propositionnelle que nous avons développé nous pouvons énoncer la récurrence comme suit :
Théorème [Principe de récurrence]
\[
\Big(\forall n \in \N \ p(n)\Big)
\ \Longleftrightarrow \
\Big(\left(p(0)\right)\et\left(\forall n \in \N \ \left(p(n)\Rightarrow p(n+1)\right)\right)\Big)
\]
Nous passerons la démonstration de ce principe qui s'enfonce profondément dans la théorie des ensembles.
L'idée de ce principe est que pour montrer qu'un prédicat \( p(n)\) est vraie alors il suffit de montrer que \( p(0)\) est vraie et que que la propriété de l'induction est vérifié, c'est à dire que
si \( p(n)\) est vraie
alors \( p(n+1)\) est aussi vraie... C'est étrange de supposer que ce l'on cherche à montrer (\( p(n)\) ) est vraie mais c'est qu'est le principe de la récurrence.
Détaillons sur la somme de Gauss.
Dans cette exemple le prédicat \( p(n)\) est
\[p(n)=\left(0+1+2+\cdots+(n-1)+n = \dfrac{n(n+1)}{2}\right)\]
Nous voulons démontrer que ce prédicat est vraie pour tout \( n\) .
Pour ce faire nous allons vérifier que \( p(0)\) est vraie d'une part et que d'autre par \( p(n)\Rightarrow p(n+1)\) (indépendamment de \( n\) ).
- Initialisation.
- Nous voulons donc vérifier que \( p(0)\) est un prédicat vraie, c'est à dire que \[\dpl{p(0)=\left(0 = \dfrac{0(0+1)}{2}\right)}\]
D'un coté \( \dpl{0=0}\) (oui oui) et d'autre par \( \dfrac{0(0+1)}{2}=0\) et nous observons bien que \( \dpl{0 =0= \dfrac{0(0+1)}{2}}\) ce qui veut dire que la proposition \( p(0)\) (qui demande si l'égalité est juste ou non) est vraie.
- Hérédité.
- C'est la partie difficile du raisonnement par récurrence. On suppose que pour un \( n\in \N\) quelconque \( p(n)\) est vraie (sans chercher à donner une valeur à \( n\) ). Partant de cette vérité, on cherche à vérifier que \( p(n+1)\) est vraie.
L'erreur à ne pas commettre est de dire ben je remplace le \( n\) par un \( n+1\) et voila1. L'idée est en utilisant l'hypothèse que \( p(n)\) est vraie (on parle de l'hypothèse de récurrence) on arrive à montrer que \( p(n+1)\) . Dans notre exemple qu'est-ce que \( p(n+1)\) ?
\[p(n+1)=\left(0+1+2+\cdots+(n-1)+n+(n+1) = \dfrac{(n+1)((n+1)+1)}{2}\right)\]
Soit en faisant une petite addition
\[p(n+1)=\left(0+1+2+\cdots+(n-1)+n+(n+1) = \dfrac{(n+1)(n+2)}{2}\right)\]
L'idée est de montrer que ce prédicat, précisément cette égalité, est bien vraie sachant qu'à tout moment du raisonnement on peut utiliser l'hypothèse de récurrence (\( p(n)\) ) (en fait, si on utilise pas l'hypothèse de récurrence, ce n'est pas un raisonnement par récurrence. C'est d'ailleurs une aide dans le raisonnement : pour avoir une bonne idée, il faut que je m'arrange pour utiliser l'hypothèse de récurrence).
Et là... il faut une idée ! Voici de quoi s'en sortir (dans ce cas ; si nous changeons de prédicat \( p\) , l'idée à avoir est différente) : on veut calculer \( \dpl{0+1+2+\cdots+(n-1)+n+(n+1)}\) . On observe que la somme de tous les nombres entiers jusqu'à \( n+1\) , il faut faire la somme jusqu'à \( n\) puis ajouter \( n+1\) . De manière savante :
\[
0+1+2+\cdots+(n-1)+n+(n+1)=\big(0+1+2+\cdots+(n-1)+n\big) + (n+1)
\]
Ici nous utilisons l'hypothèse de récurrence \( p(n)\) pour ce même \( n\) . Cette somme est égale à \( \dfrac{n(n+1)}{2}\) .
\begin{eqnarray*}
0+1+2+\cdots+(n-1)+n+(n+1)
&=&\big(0+1+2+\cdots+(n-1)+n\big) + (n+1)\\
&=& \dfrac{n(n+1)}{2}+(n+1)\\
&=& \dfrac{n(n+1)}{2}+\dfrac{2(n+1)}{2}\\
&=& \dfrac{(n+1)(n+2)}{2}
\end{eqnarray*}
Ce qui permet de conclure.
- Conclusion de la récurrence.
- En conclusion, nous avons démontrer que pour tout \( n\in\N\) ,
\[0+1+2+\cdots+(n-1)+n=\dfrac{n(n+1)}{2}\]
1Ça serait trop facile pour être mathématiques hein !
