Comprendre le raisonnement par récurrence.
|
Principe du raisonnement par récurrence :
On considère une file illimitée de dominos placés côte à côte. La règle veut que lorsqu'un domino tombe, alors il fait tomber le domino suivant et ceci à n'importe quel niveau de la file. Alors, si le premier domino tombe, on est assuré que tous les dominos de la file tombent. |
Définition :
Une propriété est dite héréditaire à partir du rang n0 si lorsque pour un entier k ≥ n0, la propriété est vraie, alors elle est vraie pour l'entier k+1.
Propriété : Si une propriété P est :
♦ Vraie au rang n0 (Initialisation),
♦ Héréditaire à partir du rang n0 (Hérédité),
alors la propriété P est vraie pour tout entier n ≥ n0.
Point Méthode : Prouver une propriété en utilisant le raisonement par récurrence.
Remarque : L'initialisation est indispensable sinon on peut démontrer des propriétés fausses !