Le raisonnement par récurrence ( ou induction )

1) Quand utiliser le raisonnement par récurrence ?

Lorsqu'on veut démontrer qu'une propriété Pn est vraie pour tout entier n
supérieur ou égal à 0 et que l'on ne dispose pas de méthode directe.

2) Principe du raisonnement par récurrence :

Le principe du raisonnement par récurrence est assez simple et nous pouvons procéder par analogie :

Supposons que nous ayons des dominos placés comme ci-contre : Comment les faire tous tomber ?
Ici aucun domino ne tombera puisque le premier ne tombe pas !
Ici les dominos ne tomberont pas tous puisque pour une certaine valeur de n l'enchaînement Pn -> Pn+1 ne se fera pas !
Donc pour démontrer par récurrence qu'une proposition Pn est vraie pour tout entier naturel n, il faudra procéder en deux étapes et conclure :
Première étape ( condition initiale ) : On vérifie que P0 est vraie.	Le premier domino P0 tombe bien.
Deuxième étape : On vérifie le caractère héréditaire (l'enchaînement Pn -> Pn+1) de la proposition. On suppose que pour un entier naturel n quelconque Pn est vraie, et sous cette hypothèse ( dite hypothèse de récurrence ), on démontre que Pn+1 est encore vraie.	Le domino Pn "entraine" bien le domino Pn+1.
Conclusion : Une fois les deux étapes franchies on conclut que la proposition Pn est vraie pour tout entier naturel n.	Les deux étapes franchies tous les dominos tomberont en "cascade".