La démonstration par récurrence est une technique de preuve utilisée pour établir qu'une propriété est vraie pour tous les nombres entiers à partir d'un certain seuil.

Le cœur de la démonstration par récurrence repose sur un mécanisme de "transmission" d'une propriété d'un rang $n$ à $n+1$, un peu comme un effet domino. Une fois que la propriété est établie comme vraie pour une valeur initiale (souvent $n = 1$ ou $n = 0$), on utilise cette vérité comme fondation pour construire la preuve pour le cas suivant, puis le cas encore suivant, etc.

L'aspect crucial ici est l'hypothèse de récurrence, où nous supposons que si la propriété est vraie pour un certain entier naturel $n$, alors elle doit également être vraie pour $n+1$. Ce lien logique est la clé qui permet de prouver, étape par étape, que la propriété se maintient pour tous les nombres suivants jusqu'à l'infini.

La démonstration par récurrence se décompose en trois étapes cruciales :

1. Première étape : Initialisation
   On vérifie que la propriété est vraie pour le premier terme de la séquence, souvent $n = 1$ ou $n = 0$. Cette étape est essentielle pour établir la base solide de la récurrence.

2. Deuxième étape : Hérédité
   On suppose que la propriété est vraie pour un entier $n$ arbitraire mais fixé. Cette supposition est connue sous le nom d'hypothèse de récurrence. On démontre ensuite que si l'hypothèse de récurrence est vraie pour $n$, alors la propriété est également vraie pour $n+1$. Cette étape est le cœur de la récurrence, reliant le rang $n$ au rang $n+1$.

3. Troisième étape : Conclusion
   On conclut que la propriété est vraie pour tout entier naturel à partir de la base de l'initialisation, en utilisant le principe de récurrence.

Exemple

Considérons la proposition suivante pour illustrer la méthode :

Nous allons prouver que cette formule est vraie pour tout entier naturel $n \geqslant 1$.

Première étape : Initialisation

Pour $n = 1$,

La propriété est vérifiée pour $n = 1$.

Deuxième étape : Hérédité

Supposons que la propriété est vraie pour un certain entier $n$, soit :

Nous devons montrer que la propriété est vraie pour $n+1$, c'est-à-dire que :

Utilisant l'hypothèse de récurrence, nous obtenons :

Troisième étape : Conclusion

Par récurrence, nous avons démontré que la formule donnant la somme des $n$ premiers entiers est correcte pour tout entier naturel $n$.