Récurrence   ([répertoire])

• lien :
  Raisonnement par récurrence (jaicompris.com)
  avec des exercices corrigés
  modèle de rédaction
   
• Définition par récurrence d'une suite :
  • on donne une valeur de départ : u₀ ( amorçage de la récurrence )
  • relation de récurrence : u_n+1 = f(u_n)
  • u₀   →   u₁ = f(u₀)   →   u₂ = f(u₁)   →   u₃ = f(u₂)   →   . . .
  • pour calculer u_n, il faut calculer toutes les valeurs qui la précèdent.
     
• Raisonnement par récurrence : démonstration de la relation u_n > 0   ∀ n ≥ 0
  • Propriété P(n) : u_n > 0
  • Initialisation : on vérifie que : u₀ > 0 ( amorçage de la récurrence )
  • Hérédité : on suppose que la propriété est vraie de 0 à n fixé :
    hypothèse de récurrence : u_n > 0
  • supposant que u_n > 0   ⇒   . . .   ⇒   u_n+1 > 0
    • exemple de démonstration :
    • Si la fonction f est croissante ( f ' > 0 ) et si f(0) > 0 :
      Comme f est croissante : conservation de l'ordre : a > b   ⇒   f(a) > f(b)
    • on suppose : u_n > 0   ⇒   f(u_n) > f(0)
      Soit : u_n+1 > 0
  • Conclusion :
  • P(0) est vraie, P(n) est héréditaire ∀ n ≥ 0, par récurrence, P(n) est vraie ∀ n ≥ 0
  • La suite (u) est minorée par 0.
     
• Démonstration que la suite (u) est décroissante :
  • Propriété P(n) : u_n > u_n+1
  • Initialisation : on vérifie que : u₀ > u₁ ( amorçage de la récurrence )
  • Hérédité : on suppose que la relation est vraie de 0 à (n−1) (n fixé)
    hypothèse de récurrence : u_n−1 > u_n
    supposant que u_n−1 > u_n   ⇒   . . .   ⇒   u_n > u_n+1
    • exemple de démonstration :
    • Si la fonction f est croissante ( f ' > 0 ) :
    • u_n−1 > u_n   ⇒   f(u_n−1) > f(u_n)
      Soit : u_n > u_n+1
  • Conclusion :
    P(0) est vraie, P(n) est héréditaire ∀ n ≥ 0, par récurrence, P(n) est vraie ∀ n ≥ 0
    la suite (u) est décroissante.
     
• La suite (u) est décroissante et minorée par 0 :
  Donc elle converge vers une limite ≥ 0
  Les seules limites L possibles pour la suite u_n+1 = f(u_n)
    sont les solutions de l'équation : L = f(L)
  Il y a donc au moins une valeur L ≥ 0
   
• Rédaction en 5 points :
  Sujet : sachant que X_n+1 = A X_n, démontrer que X_n = Aⁿ X₀   ∀ n ≥ 0
  1. recopie de l'énoncé
     Soit la propriété P(n) : X_n = Aⁿ X₀ définie pour n dans N
  2. initialisation de la récurrence
     Comme A⁰ = I , on a P(0) : X₀ = A⁰ X₀
  3. énoncé intermédiaire
     Montrons que pour un n ≥ 0 donné on a P(n) ⇒ P(n+1)
  4. hérédité
     Soit n ≥ 0, supposons P(n) : X_n = Aⁿ X₀
     X_n+1 = A X_n   ⇒   X_n+1 = A Aⁿ X₀
     Soit : X_n+1 = Aⁿ⁺¹ X₀   :   P(n+1) est vraie
  5. conclusion
     P(n) est vraie pour n=0 et est héréditaire,
     Le raisonnement par récurrence permet d'affirmer : P(n) est vraie ∀ n ≥ 0
      
• # Programmation en python : u(n+1) = (u(n) + 2/u(n)) / 2
  # (Méthode de Héron d'Alexandrie)
  # ne jamais séparer le n de u :
  import math
  n = 0
  u = 3
  print(f" u({n}) = {u}")
  for i in range(9) :
      n = n + 1
      u = (u + 2/u) / 2
      print(f" u({n}) = {u}")
  print(f"# à comparer à racine de 2 ={math.sqrt(2)}")
   

retour au menu :   Suites