Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

Récurrence (démonstration)

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 nn à n+1n+1, un peu comme un effet domino. Une fois que la propriété est établie comme vraie pour une valeur initiale (souvent n=1n = 1 ou n=0n = 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 nn, alors elle doit également être vraie pour n+1n+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=1n = 1 ou n=0n = 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 nn 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 nn, alors la propriété est également vraie pour n+1n+1. Cette étape est le cœur de la récurrence, reliant le rang nn au rang n+1n+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 :

P(n):1+2+3++n=n(n+1)2 P(n) : 1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}

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

Première étape : Initialisation

Pour n=1n = 1,

1=1(1+1)2=22=1 1 = \frac{1(1+1)}{2} = \frac{2}{2} = 1

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

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

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

1+2+3++n=n(n+1)2 1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}

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

1+2+3++n+(n+1)=(n+1)(n+2)2 1 + 2 + 3 + \ldots + n + (n+1) = \frac{(n+1)(n+2)}{2}

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

1+2+3++n+(n+1)=n(n+1)2+(n+1) 1 + 2 + 3 + \ldots + n + (n+1) = \frac{n(n+1)}{2} + (n+1)

=(n+1)(n2+1)=(n+1)n+22=(n+1)(n+2)2 = (n+1) \left( \frac{n}{2} + 1 \right) = (n+1) \frac{n+2}{2} = \frac{(n+1)(n+2)}{2}

Troisième étape : Conclusion

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