Raisonnement par récurrence

Lessons and exercises follow the school system and stay in its language.Les leçons et les exercices suivent le système scolaire et restent dans sa langue.Lektionen und Übungen folgen dem Schulsystem und bleiben in seiner Sprache.

À propos de cette leçon

Terminale, spécialité › Suites

Pour obtenir un PDF, choisis « Enregistrer au format PDF » dans la fenêtre d'impression.

Sources et crédits

Leçon originale de sedifier.

Rédigé avec l'aide d'une IA ; chaque réponse est vérifiée par notre moteur de calcul. Pas encore relu par un enseignant.

Cette leçon : CC BY-SA 4.0, © sedifier · Tous les crédits

Raisonnement par récurrence

Suites. récurrence, limite de suite, gendarmes, suite géométrique, suite monotone, convergence

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. u1=3u_1 = 3 et un+1=2un−1u_{n+1} = 2u_n - 1. Calcule u3u_3.
  2. Écris une formule pour unu_n, à partir de n=1n = 1 : 2,5,8,11,…2, 5, 8, 11, \dots
  3. un=n2+5u_n = n^2 + 5. Complète le tableau.
    nnunu_n
    11
    22
    33
    44

Découvrir

On aligne des dominos. Le premier tombe, et chaque domino qui tombe fait tomber le suivant. Que se passe-t-il ?

  1. Tous les dominos tombent
  2. On ne peut rien dire

L'idée clé

Pour démontrer qu'une propriété PnP_n est vraie pour tout entier n≥n0n \geq n_0, on procède en deux temps.

Initialisation : on vérifie que Pn0P_{n_0} est vraie.

Hérédité : on suppose PnP_n vraie pour un entier n≥n0n \geq n_0 (hypothèse de récurrence), et on démontre Pn+1P_{n+1}.

Conclusion : PnP_n est vraie pour tout n≥n0n \geq n_0.

Exemple corrigé

Soit u0=1u_0 = 1 et un+1=2unu_{n+1} = 2u_n. Démontre que un=2nu_n = 2^n pour tout n∈Nn \in \mathbb{N}.

u0=1=20u_0 = 1 = 2^0 : vrai.
Initialisation : on vérifie au rang 0.
Supposons un=2nu_n = 2^n pour un entier nn.
Hérédité : on suppose la propriété au rang n.
un+1=2un=2×2n=2n+1u_{n+1} = 2u_n = 2 \times 2^n = 2^{n+1}.
On utilise la relation, puis l'hypothèse.
Donc un=2nu_n = 2^n pour tout nn.
Les deux étapes sont faites.

À toi, guidé

À toi : avec u0=3u_0 = 3 et un+1=un+2u_{n+1} = u_n + 2, on veut montrer que un=3+2nu_n = 3 + 2n. Au rang n=0n = 0, que vaut 3+2n3 + 2n ?

3+2×03 + 2 \times 0
On remplace n par 0.
33
L'initialisation est vérifiée : c'est bien u₀.

Entraînement ★

  1. Conclure pour tout nn
  2. Démontrer la propriété au rang n+1n + 1 à l'aide de l'hypothèse
  3. Supposer la propriété vraie à un rang nn
  4. Vérifier la propriété au premier rang

Attention !

Entraînement ★★

  1. Soit u0=2u_0 = 2 et un+1=3unu_{n+1} = 3u_n. On suppose que un=2×3nu_n = 2 \times 3^n pour un entier nn. Avec cette hypothèse, quelle valeur obtient-on pour un+1u_{n+1} lorsque n=2n = 2 ?
  2. Soit u0=7u_0 = 7 et un+1=7unu_{n+1} = 7u_n. On suppose que un=7×7nu_n = 7 \times 7^n pour un entier nn. Avec cette hypothèse, quelle valeur obtient-on pour un+1u_{n+1} lorsque n=2n = 2 ?
  3. Soit u0=8u_0 = 8 et un+1=3unu_{n+1} = 3u_n. On suppose que un=8×3nu_n = 8 \times 3^n pour un entier nn. Avec cette hypothèse, quelle valeur obtient-on pour un+1u_{n+1} lorsque n=2n = 2 ?
  1. Pour démontrer par récurrence que un=7nu_n = 7^n, avec u0=1u_0 = 1 et un+1=7unu_{n+1} = 7u_n, qu'écrit-on au début de l'hérédité ?
    1. Supposons que un=7nu_n = 7^n pour un certain entier nn.
    2. Supposons que un+1=7n+1u_{n+1} = 7^{n+1}.
    3. Supposons que un=7nu_n = 7^n pour tout entier nn.
    4. On vérifie que u0=1u_0 = 1.
  2. Pour démontrer par récurrence que un=5nu_n = 5^n, avec u0=1u_0 = 1 et un+1=5unu_{n+1} = 5u_n, qu'écrit-on au début de l'hérédité ?
    1. Supposons que un=5nu_n = 5^n pour un certain entier nn.
    2. Supposons que un+1=5n+1u_{n+1} = 5^{n+1}.
    3. Supposons que un=5nu_n = 5^n pour tout entier nn.
    4. On vérifie que u0=1u_0 = 1.
  1. On démontre par récurrence que 1+2+⋯+n=n(n+1)21 + 2 + \dots + n = \dfrac{n(n + 1)}{2}. Pour passer du rang 5 au rang 66, quel nombre ajoute-t-on à la somme ?
  1. Pour démontrer une propriété P(n)P(n) pour tout n≥0n \geq 0, on a prouvé : si P(n)P(n) est vraie, alors P(n+1)P(n + 1) est vraie. Que manque-t-il ?
    1. L'initialisation : prouver P(0)P(0)
    2. Rien : la démonstration est complète
    3. Vérifier P(n)P(n) pour quelques valeurs de plus

Bilan

Trois questions pour vérifier que c'est acquis.

  1. Pour démontrer par récurrence que un=7nu_n = 7^n, avec u0=1u_0 = 1 et un+1=7unu_{n+1} = 7u_n, qu'écrit-on au début de l'hérédité ?
    1. Supposons que un=7nu_n = 7^n pour un certain entier nn.
    2. Supposons que un+1=7n+1u_{n+1} = 7^{n+1}.
    3. Supposons que un=7nu_n = 7^n pour tout entier nn.
    4. On vérifie que u0=1u_0 = 1.
  2. Pour démontrer par récurrence que un=5nu_n = 5^n, avec u0=1u_0 = 1 et un+1=5unu_{n+1} = 5u_n, qu'écrit-on au début de l'hérédité ?
    1. Supposons que un=5nu_n = 5^n pour un certain entier nn.
    2. Supposons que un+1=5n+1u_{n+1} = 5^{n+1}.
    3. Supposons que un=5nu_n = 5^n pour tout entier nn.
    4. On vérifie que u0=1u_0 = 1.
  3. Pour démontrer par récurrence que un=3nu_n = 3^n, avec u0=1u_0 = 1 et un+1=3unu_{n+1} = 3u_n, qu'écrit-on au début de l'hérédité ?
    1. Supposons que un=3nu_n = 3^n pour un certain entier nn.
    2. Supposons que un+1=3n+1u_{n+1} = 3^{n+1}.
    3. Supposons que un=3nu_n = 3^n pour tout entier nn.
    4. On vérifie que u0=1u_0 = 1.

Fiche résumé

Récurrence

  • Initialisation : Pn0P_{n_0} est vraie.
  • Hérédité : si PnP_n est vraie, alors Pn+1P_{n+1} est vraie.

Attention : sans initialisation, il n'y a pas de démonstration, même si l'hérédité marche.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. u0=1u_0 = 1 et un+1=2un+1u_{n+1} = 2u_n + 1. On démontre par récurrence que un=2n+1−1u_n = 2^{n+1} - 1. Calcule u9u_{ 9 }.
Sources et crédits

Leçon originale de sedifier.

Rédigé avec l'aide d'une IA ; chaque réponse est vérifiée par notre moteur de calcul. Pas encore relu par un enseignant.

Cette leçon : CC BY-SA 4.0, © sedifier · Tous les crédits