I- A quoi ça sert ?

Le raisonnement par récurrence est une méthode de démonstration. Elle vise à démontrer des propriétés pour tous les entiers naturels à partir d'un certain entier. Elle s'applique bien quand vous avez des questions du type :

Démontrer que la propriété XXXX est vraie pour tous les entiers naturels.
On raisonne sur N. Montrer qu'à partir du rang X la propriété XXXX est vraie.

II- La méthode

La démonstration par récurrence est, comme tout en mathématiques, quelque chose de très rigoureux donc suivez les étapes !

1) Proposition

Énoncer votre proposition, c'est ce que vous voulez démontrer. Elle a la forme Pn:"votre proposition"

2) Initialisation

Trouver un rang n le plus petit possible où la proposition est vraie. C'est le rang d'initialisation.

3) Hérédité

Concrètement qu'est ce que je fais ?
Vous écrivez : On suppose que la proposition est vraie à partir d'un certain rang n, on va montrer qu'elle est encore vraie au rang suivant n+1.

"On suppose que la proposition est vraie à partir d'un certain rang n" est l'hypothèse de récurrence, sans cette hypothèse vous ne pouvez pas faire l'hérédité.

Puis vous partez de la proposition au rang n+1 et en utilisant l'hypothèse de récurrence, donc en soit la proposition au rang n, vous montrez que la proposition est vraie au rang n+1.

4) Conclusion

Vous écrivez : La proposition vraie au rang n=rang de votre initialisation est héréditaire à partir de ce rang. Donc pour tout n>= votre rang d'initialisation la proposition est vraie.

III- Exemple


Montrez que pour tout n >= 1, 1+2+3+...+n=n(n+1)/2.

Proposition : On pose pour un entier n, P(n):"la somme des n premiers entiers est égale à n(n+1)/2".

Initialisation : Montrons que la proposition est vraie au rang n=1
En remplaçant n par 1 dans n(n+1)/2 on a 1(1+1)/2=1
De plus la somme des entiers de 1 à n avec n=1 est bien 1
Donc la proposition est vraie au rang n=1.

Hérédité : On suppose que la proposition est vraie à partir d'un certain rang n, on va montrer qu'elle est encore vraie au rang suivant n+1.

Soit 1+2+3+...+n+(n+1)=(1+2+3+...+n)+(n+1)
En appliquant l'hypothèse de récurrence, c'est à dire 1+2+3+...+n=n(n+1)/2 on a
(1+2+3+...+n)+(n+1)=n(n+1)/2+(n+1)
=[n(n+1)+2(n+1)]/2
=[(n+1)(n+2)]/2
On a donc
1+2+3+...+n+(n+1)=[(n+1)(n+2)]/2 La proposition est vraie au rang n+1.

Conclusion : La proposition vraie au rang n=1 est héréditaire à partir de ce rang. Donc pour tout n>=1, 1+2+3+...+n=n(n+1)/2.

Merci pour ce cours Luinil