Aller au contenu

Raisonnement par récurrence

Fiche de révision · Mathématiques · Term

L'essentiel du cours

  1. Chapitre 1 : Comprendre la logique

    Comme des dominos : un point de départ et une transmission de proche en proche.

  2. Chapitre 2 : Formalisation

    On passe de k à k+1 grâce à l'hypothèse de récurrence.

  3. Chapitre 3 : Somme des entiers

    L'hypothèse de récurrence permet de remplacer la somme des k premiers termes.

  4. Chapitre 4 : Pièges et bonnes pratiques

    Sans initialisation, la récurrence ne prouve rien.

Teste-toi · 8 questions

  1. 1.Quelle est la première étape d'un raisonnement par récurrence ?

    Voir la réponse

    Réponse : L'initialisation

    On commence toujours par vérifier la propriété au premier rang, c'est l'initialisation.

  2. 2.Dans l'hérédité, on suppose que P(k) est vraie pour :

    1. A.tous les entiers k
    2. B.k quelconque sans condition
    3. C.un certain entier k ≥ n₀
    4. D.k = n₀ seulement
    Voir la réponse

    Réponse C : un certain entier k ≥ n₀

    On fixe un entier k ≥ n₀ et on suppose P(k) vraie pour démontrer P(k+1).

  3. 3.On veut prouver par récurrence que pour tout n ≥ 1, 1+3+5+...+(2n-1) = n². Quelle est l'initialisation ?

    Voir la réponse

    Réponse : Vérifier pour n=1

    Le premier rang est n=1, on vérifie que 1 = 1².

  4. 4.Dans la démonstration de la somme des entiers, après avoir supposé 1+...+k = k(k+1)/2, on ajoute (k+1). L'expression obtenue est :

    1. A.(k+1)²/2
    2. B.(k+1)(k+2)/2
    3. C.k(k+1)/2 + k
    4. D.k(k+3)/2
    Voir la réponse

    Réponse B : (k+1)(k+2)/2

    k(k+1)/2 + (k+1) = (k+1)(k/2+1) = (k+1)(k+2)/2.

  5. 5.Une propriété P(n) est héréditaire mais P(0) est fausse. Que peut-on conclure ?

    Voir la réponse

    Réponse : On ne peut rien conclure sans initialisation vraie

    Sans initialisation vraie, la récurrence ne permet pas de conclure que P(n) est vraie pour n≥0.

  6. 6.Quelle erreur est commise si on écrit : « Supposons que pour tout k, P(k) est vraie » ?

    Voir la réponse

    Réponse : On suppose ce qu'on veut démontrer

    C'est une pétition de principe : on suppose la propriété vraie pour tous les entiers, ce qui est exactement ce qu'on cherche à prouver.

  7. 7.Pour démontrer par récurrence que 2^n ≥ n+1 pour tout n ≥ 0, l'initialisation vérifie :

    1. A.2^0 ≥ 0
    2. B.2^1 ≥ 1
    3. C.2^1 ≥ 2
    4. D.2^0 ≥ 1
    Voir la réponse

    Réponse D : 2^0 ≥ 1

    Pour n=0, 2^0=1 et 0+1=1, donc 1≥1, vrai.

  8. 8.Dans l'hérédité de la propriété 2^n ≥ n+1, on suppose 2^k ≥ k+1. Que doit-on montrer ?

    Voir la réponse

    Réponse : 2^{k+1} ≥ k+2

    On remplace n par k+1 : 2^{k+1} ≥ (k+1)+1 = k+2.