Partager |

Démonstration par récurrence

Théorème

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

  • Si P(n_(0)) 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_(0)

Remarques

  • La démonstration par récurrence s'apparente au "principe des dominos" :
    Récurrence et 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_(0)=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+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.

Partager |

Copyright 2007-2012 - Maths-cours.fr