Pré-requis
Le raisonnement par récurrence se fait en trois étapes que sont l’initialisation, l’hérédité et la conclusion. Ces trois étapes sont nécessaires pour mener à bien un tel raisonnement que nous allons illustrer à partir d’un exemple.
Etapes
Initialisation
La proposition est vraie car
On conçoit et on admet que si l’on sait démontrer que « vraie » entraîne « vraie », alors la proposition est vraie pour tout entier naturel .
Hérédité
Supposons donc que est vraie pour un entier naturel , c’est-à-dire que pour un entier naturel :
- C’est l’hypothèse de récurrence.
Montrons maintenant que la propriété est vraie au rang supérieur (au rang ), c’est-à-dire que est vraie.
Autrement dit, montrons que :
Comme est vraie, alors dans la somme , on peut remplacer les premiers termes par .
On obtient alors :
En factorisant par , on obtient :
En factorisant par , on obtient :
En réduisant le deuxième facteur au même dénominateur 2, on a :
Ainsi est vraie.
Conclusion
est vraie pour tout entier naturel , c’est-à-dire pour tout entier naturel ,