GRATUIT!
Cours de maths - Exercices - Méthodes - QCM - Sujets du bac

Récurrence

maths-cours

24/09/2008 - 10:15

Théorème

Soit P(n) une proposition qui dépend d'un entier naturel n.

Si P(n₀) est vraie (initialisation)
Et si P(n) vraie entraîne P(n+1) vraie (hérédité)

alors la propriété P(n) est vraie pour tout entier n n₀

Remarques

La démonstration par récurrence s'apparente au "principe des dominos" :

L'étape d'initialisation est souvent facile à démontrer; toutefois, faites attention à ne pas l'oublier!
Pour prouver l'hérédité, on suppose que la propriété est vraie pour un certain entier n (cette supposition est appelée hypothèse de récurrence) et on démontre qu'elle est alors vraie pour l'entier n+1. Pour cela, il est conseillé d'écrire ce que signifie P(n+1), en remplacant n par n+1 dans la propriété P(n)

Exemple

Montrons pour pour tout entier n strictement positif 1+2+. . .+n=(n(n+1))/2 .

Initialisation

On commence à n₀=1 car l'énoncé précise "strictement positif".
La proposition devient :
1=(1*2)/2
ce qui est vrai.

Hérédité

On suppose que pour un certain entier n:
1+2+. . .+n=(n(n+1))/2 (Hypothèse de récurrence)
et on va montrer qu'alors :
1+2+. . .+n+1=((n+1)(n+2))/2 (on a remplacé n par n+1 dans la formule que l'on souhaite prouver).

Isolons le dernier terme de notre somme
1+2+. . .+n+1 = (1+2+. . . +n) + n+1
On applique maintenant notre hypothèse de récurrence à :
1+2+. . .+n+1=(n(n+1))/2+n+1=(n(n+1))/2+(2(n+1))/2= (n(n+1)+2(n+1))/2
1+2+. . .+n+1=((n+1)(n+2))/2
ce qui correspond bien à ce que nous voulions montrer.
En conclusion nous avons bien prouvé que pour pour tout entier n strictement positif :
1+2+. . .+n=(n(n+1))/2 .