suivant : 1.17 Dénombrement remonter : 1.16 Suites numériques précédent : 1.16.4 Convergence

1.16.5 Raisonnement par récurrence

Ce type de raisonnement ne s'applique que dans des propriétés faisant intervenir des nombres entiers. Par exemple, ``Quel que soit $n \geq 0$, $n^2 - n$ est pair''. Pour prouver qu'une propriété est vérifiée quelle que soit la valeur de $n$, on effectue une preuve par récurrence en procédant en deux temps :

• l'initialisation, On prouve que pour $n = 0$ (ou $1$, ça dépend des cas), la propriété est vérifiée.
• l'hérédité, on prouve que si la propriété est vérifiée au rang $n$, alors elle l'est au rang $n+1$.

Par exemple,

• initialisation : , $0^2 - 0$ est pair, c'est évident.
• hérédité : , supposons que $n^2 - n$ est pair, vérifions si $(n+1)^2 - (n+1)$ est pair lui aussi. Calculons
  
  $$(n+1)^2 - (n+1) = n^2 + 2n + 1 - n - 1 = (n^2 - n) + 2n$$
  
  
  Comme $(n^2 - n)$ et $2n$ sont tous deux pairs, et que la somme de deux nombres pairs est paire, alors $(n+1)^2 - (n+1)$ est pair.

Demandons-nous si $2^2 - 2$ est pair, on sait d'après l'initialisation que $0^2 - 0$ est pair. Posons $n = 0$, comme la propriété est vérifiée au rang $n$, elle est, d'après l'hérédité, nécessairement vérifiée au rang $n+1$, donc $1^2 - 1$ est pair. Posons $n = 1$, comme $1^2 - 1$ est pair, la propriété est vérifiée au rang $n$, elle est, d'après l'hérédité, nécessairement vérifiée au rang $n+1$, donc $2^2 - 2$ est pair. On peut généraliser ce raisonnement à n'importe quelle valeur de $n$.

suivant : 1.17 Dénombrement remonter : 1.16 Suites numériques précédent : 1.16.4 Convergence