MetMat
← Retour aux méthodes

Comment démontrer une propriété dépendant d'un entier par récurrence ?

En menant une récurrence forte ou à deux pas lorsque P(n+1)P(n+1) dépend de plusieurs rangs antérieurs

L'objectif

Démontrer une propriété P(n)P(n) dont l'hérédité nécessite de connaître PP à plusieurs rangs antérieurs, typiquement pour les suites récurrentes d'ordre 2.

Le principe

Principe de récurrence forte : si P(n0)P(n_0) est vraie et si ∀n≥n0,(∀k∈{n0,…,n},P(k))⇒P(n+1)\forall n \geq n_0, \bigl(\forall k \in \{n_0, \dots, n\}, P(k)\bigr) \Rightarrow P(n+1), alors ∀n≥n0,P(n)\forall n \geq n_0, P(n). Variante « à deux pas » : on initialise P(n0)P(n_0) et P(n0+1)P(n_0 + 1) puis on suppose P(n)P(n) et P(n+1)P(n+1) pour démontrer P(n+2)P(n+2).

La méthode
  1. 1
    J'énonce P(n)P(n) et je choisis le type de récurrence (forte ou à deux pas) selon le nombre de rangs antérieurs intervenant dans la formule de récurrence.
  2. 2
    Initialisation : je vérifie P(n0)P(n_0), et si besoin P(n0+1)P(n_0 + 1), par calcul direct.
  3. 3
    Hérédité renforcée : je suppose P(k)P(k) vraie pour tout kk entre n0n_0 et nn (ou pour P(n)P(n) et P(n+1)P(n+1) à deux pas), puis j'en déduis P(n+1)P(n+1) (respectivement P(n+2)P(n+2)).
  4. 4
    Je conclus par le principe de récurrence forte (ou à deux pas) que P(n)P(n) est vraie pour tout n≥n0n \geq n_0.

Exemple corrigé

Difficulté croissante de 1 à 3

Exercices aujourd'hui0 / 3

Prêt à t'entraîner ?

Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.