Mathématiques · term

Raisonnement par récurrence

Ce que tu dois retenir

Chapitre 1 — Comme des dominos

Initialisation + Hérédité = Conclusion universelle.

Chapitre 2 — Somme des n premiers entiers

L'hérédité transforme k(k+1)/2 + (k+1) en (k+1)(k+2)/2.

Chapitre 3 — 2^n > n

L'astuce : 2k ≥ k+1 car k ≥ 1.

Chapitre 4 — Erreurs classiques

Toujours vérifier l'initialisation et l'hérédité.

Teste-toi

1. Quel est le principe du raisonnement par récurrence ?

AA. Vérifier la propriété pour n=0 et n=1
BB. Initialisation et hérédité
CC. Tester tous les entiers un par un
DD. Utiliser un contre-exemple
Voir la réponse

Réponse : B — B. Initialisation et hérédité

Le raisonnement par récurrence repose sur deux étapes : l'initialisation (vraie pour un premier rang) et l'hérédité (si vraie pour k, alors vraie pour k+1).

2. 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. Vérifier pour n=3
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².

3. Dans l'hérédité, on suppose la propriété vraie pour un entier k et on démontre qu'elle est vraie pour :

AA. k-1
BB. k
CC. k+1
DD. 2k
Voir la réponse

Réponse : C — C. k+1

L'hérédité consiste à montrer que si P(k) est vraie, alors P(k+1) est vraie.

4. On veut montrer par récurrence que pour tout n≥1, 2^n ≥ n+1. L'initialisation pour n=1 donne :

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

Réponse : B — B. 2 ≥ 2

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

5. Dans l'hérédité de P(n): 1+2+...+n = n(n+1)/2, on suppose P(k) vraie. Quelle expression doit-on obtenir pour P(k+1) ?

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

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

P(k+1) est la formule avec n=k+1, soit (k+1)(k+2)/2. On part de la somme jusqu'à k+1 = somme jusqu'à k + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2.

6. Laquelle de ces propriétés est vraie pour tout n≥1 ?

AA. n² < n
BB. 2^n < n
CC. n! > 2^n
DD. n² ≥ n
Voir la réponse

Réponse : D — D. n² ≥ n

Pour n≥1, n² ≥ n est toujours vrai (initialisation n=1: 1≥1, hérédité: (k+1)² = k²+2k+1 ≥ k+1 car k²≥k). Les autres sont fausses pour certains n.

7. Pourquoi l'initialisation est-elle indispensable ?

AA. Pour vérifier la propriété pour tous les entiers
BB. Pour avoir un point de départ à l'hérédité
CC. Pour simplifier les calculs
DD. Pour trouver un contre-exemple
Voir la réponse

Réponse : B — B. Pour avoir un point de départ à l'hérédité

Sans initialisation, l'hérédité ne permet pas de conclure, car la propriété pourrait être vraie pour aucun entier (ex: P(n): n=n+1 est héréditaire mais fausse pour tout n).

8. On considère P(n): 'n² - n + 41 est un nombre premier'. Pour n=0,...,40, c'est vrai, mais pour n=41, 41²-41+41=41² non premier. Peut-on prouver P(n) par récurrence pour tout n ?

AA. Oui, car vraie pour beaucoup de n
BB. Non, car l'hérédité est fausse
CC. Oui, car l'initialisation est vraie
DD. Non, car la propriété est fausse pour n=41
Voir la réponse

Réponse : B — B. Non, car l'hérédité est fausse

Pour n=40, P(40) est vraie (1601 premier), mais P(41)=1681=41² n'est pas premier, donc l'hérédité de 40 à 41 échoue. On ne peut pas prouver une propriété fausse par récurrence.

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