Raisonnement par récurrence
Comment faire pour grimper en haut d'une échelle? Il suffit de savoir remplir deux conditions : atteindre le premier barreau, et être capable de passer d'un barreau au barreau suivant.
Le raisonnement par récurrence, ou par induction, c'est exactement la même chose! Si on souhaite démontrer qu'une propriété $P_n$, dépendant de l'entier $n$, est vraie pour tout entier $n$, il suffit de :
- initialiser : prouver que la propriété $P_0$ est vraie (ou $P_1$ si la propriété ne commence qu'au rang 1).
- hériter : prouver que, pour tout entier $n$, si $P_n$ est vraie, alors $P_{n+1}$ est vraie.
Donnons un exemple. Pour $n\geq 1$, notons $S_n=1+\cdots+n$ la somme des $n$ premiers entiers. Pour $n\geq 1$, on note $P_n$ la propriété : "$S_n=n(n+1)/2$".
- initialisation : On a $S_1=1=1(1+1)/2$ donc $P_1$ est vraie.
- hérédité : soit $n\geq 1$ tel que $P_n$ est vraie, c'est-à-dire tel que $S_n=n(n+1)/2$. Alors on a $$S_{n+1}=\frac{n(n+1)}2+(n+1)=(n+1)\left(\frac n2+1\right)=\frac{(n+1)(n+2)}2.$$ La propriété $P_{n+1}$ est donc vraie.
- conclusion : la propriété $P_n$ est vraie pour tout $n\geq 1$.
Il ne faut pas oublier l'initialisation!
On peut prouver que la propriété $P_n$ : "$3$ divise $4^n+1$" est héréditaire.... mais toujours fausse!
Il existe toute une variété de raisonnement par récurrence :
- les récurrences doubles : on procède 2 par 2, c'est-à-dire que l'on prouve que $P_0$ et $P_1$ sont vraies, et on suppose que $P_n$, $P_{n+1}$ sont vraies pour prouver que $P_{n+1}$ et $P_{n+2}$ sont vraies.
- les récurrences descendantes : on prouve qu'à un certain rang $k$, $P_k$ est vraie, et on montrer que si $P_n$ est vraie, alors $P_{n-1}$ est vraie. Alors les propriétés $P_0,\dots,P_k$ sont vraies!
C'est à Pascal que l'on doit la première utilisation du raisonnement par récurrence, dans le Traité du triangle arithmétique. Ses correspondances permettent même de dater la découverte avec précision, entre le 29 juillet et le 29 aout 1654. Pour Poincaré, le raisonnement par induction est LE raisonnement mathématique par excellence. A l'opposé de la vision intuitionniste de Poincaré, il est parfois possible de faire des raisonnement par récurrence (ou tout comme...) dans des ensembles non dénombrables, en utilisant le lemme de Zorn.