Mathématiques · term

Raisonnement par récurrence

Ce que tu dois retenir

Chapitre 1 — Comprendre la logique

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

Chapitre 2 — Formalisation

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

Chapitre 3 — Somme des entiers

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

Chapitre 4 — Pièges et bonnes pratiques

Sans initialisation, la récurrence ne prouve rien.

Teste-toi

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

AA. L'hérédité
BB. L'initialisation
CC. La conclusion
DD. L'hypothèse
Voir la réponse

Réponse : B — B. L'initialisation

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

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

AA. tous les entiers k
BB. un certain entier k ≥ n₀
CC. k = n₀ seulement
DD. k quelconque sans condition
Voir la réponse

Réponse : B — B. un certain entier k ≥ n₀

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

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

AA. Vérifier pour n=0
BB. Vérifier pour n=1
CC. Vérifier pour n=2
DD. Supposer la formule vraie
Voir la réponse

Réponse : B — B. Vérifier pour n=1

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

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 :

AA. (k+1)(k+2)/2
BB. k(k+1)/2 + k
CC. (k+1)²/2
DD. k(k+3)/2
Voir la réponse

Réponse : A — A. (k+1)(k+2)/2

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

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

AA. P(n) est vraie pour tout n
BB. P(n) est fausse pour tout n
CC. On ne peut rien conclure sans initialisation vraie
DD. P(n) est vraie pour n>0
Voir la réponse

Réponse : C — C. 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. Quelle erreur est commise si on écrit : « Supposons que pour tout k, P(k) est vraie » ?

AA. On suppose ce qu'on veut démontrer
BB. On utilise un mauvais rang
CC. On oublie l'initialisation
DD. C'est correct
Voir la réponse

Réponse : A — A. 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. Pour démontrer par récurrence que 2^n ≥ n+1 pour tout n ≥ 0, l'initialisation vérifie :

AA. 2^0 ≥ 1
BB. 2^1 ≥ 2
CC. 2^0 ≥ 0
DD. 2^1 ≥ 1
Voir la réponse

Réponse : A — A. 2^0 ≥ 1

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

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

AA. 2^{k+1} ≥ k+2
BB. 2^{k+1} ≥ k+1
CC. 2^k ≥ k+2
DD. 2^{k+1} ≥ 2k+2
Voir la réponse

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

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

Retour au cours ruedusavoir.com · Apprendre, c'est avancer.