cours : Initiation au raisonnement par récurrence

² 1. Initiation au raisonnement par récurrence Il s'agit d'un raisonnement inductif, c'est-à-dire un raisonnement visant à produire des connaissances par des conclusions plus générales que les prémisses. A partir du constat de la validité d'une propriété dépendant d'un entier naturel n sur des cas particuliers, on la valide par une démonstration pour une situation générale. Cette démonstration est donc réalisée en enchaînant trois étapes : La phase 1 consiste à vérifier la propriété proposée sur un cas particulier. Elle correspondra à la plus petite valeur n du naturel n à partir de laquelle la propriété proposée à la odémonstration sera vraie (en général pour n = 0 ou n = 1). Cette phase est celle de l'initialisation, on contrôle qu'il existe bien une première valeur qui enclenche le processus. La phase 2 consiste à démontrer que si la propriété est vraie pour une valeur p indéfinie supérieure ou égale à la valeur particulière n , elle est alors vraie pour la valeur suivante p + 1. oCette étape est celle de l'hérédité, tout successeur reçoit la propriété de son prédécesseur. La phase 3 consiste à formuler la procédure et sa conclusion : la propriété est vraie pour la valeur n . oSi elle est vraie pour p, alors elle est vraie pour p + 1, on peut donc en conclure qu'elle s'étend à tout entier n  n . La propriété est vraie pour toute valeur de n supérieure ou égale à n .o o Cette dernière phase, en s'appuyant sur les phases 1 et 2, ...