Guide de l'enseignant: Raisonnement par récurrence

Apprends à démontrer une propriété pour tout entier naturel avec le raisonnement par récurrence : initialisation, hypothèse de récurrence, hérédité et conclusion.

Présenter la leçonVoir la page élève

Utiliser cette leçon en classe

Gratuit, sans compte élève.

Partager avec les élèves

Les élèves ouvrent la leçon et s'entraînent avec une correction immédiate.

Fiche d'exercices à imprimer

Tous les exercices sur papier, avec un corrigé séparé.

Fiche d'exercices Corrigé

Quiz de classe

10 questions sur Preuves mathématiques. Les élèves participent avec un prénom, vous voyez tous les scores.

Pour les enseignants

Objectifs d'apprentissage

Expliquer l'idée des dominos derrière le raisonnement par récurrence
Rédiger l'initialisation, l'hypothèse de récurrence, l'hérédité et la conclusion d'une démonstration par récurrence
Démontrer par récurrence des formules de sommes, des propriétés de divisibilité et des inégalités
Trouver et corriger les erreurs dans des démonstrations par récurrence fausses

Prérequis

• Introduction aux preuves mathématiques : ce qu'est une démonstration
• Démonstration directe : démontrer à partir des définitions
• Développer et factoriser des expressions comme $(k+1)^2$ et $(k+1)^3$
• Calculer avec des puissances, par exemple $2 \cdot 2^k = 2^{k+1}$

Amorces de discussion

1. Si tu sais que le premier domino tombe et que chaque domino fait tomber le suivant, comment sais-tu que le 1000e domino tombe ?
2. Pourquoi vérifier une formule pour les 40 premières valeurs de n ne suffit-il pas ?
3. Que se passerait-il si on oubliait l'initialisation ?
4. Connais-tu une situation de la vie courante où une étape mène toujours à la suivante ?

Idées reçues courantes

Supposer $P(k)$ , c'est supposer ce que l'on veut démontrer

Remédiation: Insiste sur le fait qu'on suppose $P(k)$ pour UNE seule valeur, afin de montrer le lien entre $k$ et $k+1$ . C'est l'initialisation qui lance la chaîne. Utilise les dominos : on suppose qu'un domino tombe seulement pour vérifier qu'il touche le suivant.

L'initialisation est une formalité qu'on peut sauter

Remédiation: Montre l'affirmation fausse $1 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1$ . Son hérédité fonctionne parfaitement, mais l'initialisation échoue, donc l'affirmation est fausse pour tout $n$ .

Vérifier plusieurs valeurs démontre une formule

Remédiation: Utilise $n^2 + n + 41$ , qui est premier pour $n = 0$ à $39$ mais vaut $41^2$ pour $n = 40$ . Les motifs suggèrent une formule, seule une démonstration la confirme.

Idées de différenciation

Pour les élèves en difficulté:

• Donner un modèle avec quatre cases : initialisation, hypothèse, hérédité, conclusion
• Avant le calcul littéral, vérifier $P(k)$ et $P(k+1)$ avec des nombres, par exemple $k = 4$
• Commencer uniquement par des formules de sommes, où le terme suivant est facile à voir

Pour les élèves au niveau:

• Démontrer la somme des nombres impairs et la somme des puissances de 2 sans modèle
• Trouver l'erreur dans trois démonstrations par récurrence fausses
• Démontrer que $n^3 - n$ est divisible par $3$

Pour les élèves avancés:

• Démontrer $2^n > n^2$ pour $n \ge 5$ et expliquer pourquoi l'initialisation se fait à $5$
• Démontrer $1^2 + 2^2 + \dots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$
• Découvrir la récurrence forte et démontrer que tout entier $n \ge 2$ est un produit de nombres premiers

Alignement aux standards

MP3 (CCSS.MATH.PRACTICE.MP3)
Construire des arguments solides et critiquer le raisonnement des autres
HSA-APR.C.4 (CCSS.MATH.CONTENT.HSA.APR.C.4)
Démontrer des identités polynomiales et les utiliser pour décrire des relations numériques
HSA-SSE.B.4 (CCSS.MATH.CONTENT.HSA.SSE.B.4)
Établir la formule de la somme des termes d'une suite géométrique finie et l'utiliser pour résoudre des problèmes

Ressources de la leçon

visualVisualiseur de suites
Règle le premier terme sur 1 et la raison sur 2 : la ligne de la somme montre que les 8 premiers nombres impairs ont pour somme 64, soit 8 au carré
activityDémonstration avec des dominos
Les élèves alignent des dominos et testent ce qui se passe sans première poussée ou avec un trou dans la rangée
worksheetCompléter des démonstrations par récurrence
Cinq démonstrations par récurrence où il manque l'initialisation, l'hypothèse ou des étapes de calcul

Contenu de la leçon

Tout ce que voient les élèves : définition, exemples, erreurs fréquentes, applications. Touchez pour ouvrir.

Définition

Le raisonnement par récurrence est une méthode de démonstration pour les propriétés qui portent sur tout entier

n \ge 1

(ou tout entier à partir d'une valeur de départ). On note la propriété

P(n)

. Au lieu de vérifier une infinité de cas un par un, tu démontres seulement deux choses :

1.Initialisation : $P(1)$ est vraie.
2.Hérédité : pour tout $k \ge 1$ , si $P(k)$ est vraie, alors $P(k+1)$ est vraie aussi. La supposition " $P(k)$ est vraie" s'appelle l'hypothèse de récurrence.

Ensemble, elles donnent la conclusion :

P(n)

est vraie pour tout

n \ge 1

P(1) \ \text{et} \ \big(P(k) \Rightarrow P(k+1)\big) \ \Longrightarrow \ P(n) \text{ pour tout } n \ge 1

Imagine une rangée infinie de dominos. L'initialisation fait tomber le premier domino. L'hérédité garantit que chaque domino qui tombe fait tomber le suivant. Donc tous les dominos tombent :

P(1)

, puis

P(2)

, puis

P(3)

, et ainsi de suite sans fin.

Exemples résolus

Démontre que $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$ pour tout $n \ge 1$ .

Initialisation : vérifie $n = 1$

Membre de gauche : $1$ . Membre de droite : $\dfrac{1 \cdot 2}{2} = 1$ → $P(1)$ est vraie

Hypothèse de récurrence : suppose $P(k)$ pour un $k \ge 1$

Supposons $1 + 2 + \dots + k = \dfrac{k(k+1)}{2}$ → On peut utiliser cette égalité

Hérédité : ajoute le terme suivant $k+1$ aux deux membres

$1 + \dots + k + (k+1) = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{k(k+1) + 2(k+1)}{2}$ → $= \dfrac{(k+1)(k+2)}{2}$

Compare avec $P(k+1)$

$P(k+1)$ affirme que la somme vaut $\dfrac{(k+1)\big((k+1)+1\big)}{2} = \dfrac{(k+1)(k+2)}{2}$ → $P(k+1)$ est vraie

Réponse: Par récurrence, $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ pour tout $n \ge 1$ . Par exemple, $1 + 2 + \dots + 100 = \dfrac{100 \cdot 101}{2} = 5050$ .

Erreurs courantes

Oublier l'initialisation

Pourquoi c'est faux: L'hérédité seule ne démontre rien : elle dit seulement que SI un domino tombe, le suivant tombe aussi. Exemple : l'affirmation fausse $1 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1$ a une hérédité qui fonctionne, mais pour $n = 1$ le membre de gauche vaut $1$ et celui de droite vaut $2$ .

Correct: Vérifie toujours le premier cas explicitement. Sans premier domino qui tombe, rien ne tombe.

Supposer ce que l'on veut démontrer

Pourquoi c'est faux: Écrire "supposons $P(n)$ vraie pour tout $n$ " ou "supposons $P(k+1)$ " est un raisonnement circulaire : on suppose la conclusion.

Correct: Suppose $P(k)$ pour UNE valeur $k$ (l'hypothèse de récurrence) et démontre $P(k+1)$ à partir d'elle.

Une erreur de calcul dans l'hérédité

Pourquoi c'est faux: Une erreur courante consiste à ajouter le mauvais terme suivant, par exemple $2k - 1$ au lieu de $2k + 1$ dans la somme des nombres impairs, ou à oublier d'ajouter le nouveau terme d'un côté.

Correct: Écris d'abord $P(k+1)$ en entier (remplace chaque $n$ par $k+1$ ), puis travaille pour arriver exactement à cette expression.

Croire que vérifier beaucoup de cas est une démonstration

Pourquoi c'est faux: L'expression $n^2 + n + 41$ donne des nombres premiers pour $n = 0, 1, \dots, 39$ , mais pour $n = 40$ elle donne $1681 = 41^2$ , qui n'est pas premier.

Correct: Les exemples aident à deviner une formule. Seules l'initialisation et l'hérédité la démontrent pour tout $n$ .

Pourquoi c'est important

La récurrence est l'outil principal pour démontrer des résultats sur une infinité de cas :

Formules de sommes : tu peux démontrer que $1 + 2 + \dots + 100 = 5050$ découle d'une formule générale et non du hasard
Informatique : les programmeurs démontrent que les boucles et les fonctions récursives donnent le bon résultat pour toute taille de données
Des motifs qui semblent vrais : un motif vérifié dans 40 cas peut échouer au 41e ; la récurrence indique quand un motif est vraiment vrai pour toujours
Énigmes et jeux : les tours de Hanoï, les problèmes de pavage et beaucoup d'exercices de concours se résolvent par récurrence
Mathématiques supérieures : presque tous les domaines des mathématiques utilisent la récurrence quelque part

Dans les leçons précédentes, tu as appris les démonstrations directes. La récurrence ajoute une idée nouvelle et puissante : démontrer une seule étape, puis la laisser se répéter à l'infini.

Applications dans le monde réel

Vérifier des programmes informatiques

Les programmeurs utilisent la récurrence pour démontrer qu'une boucle donne la bonne réponse après n'importe quel nombre de tours : si c'est juste après $k$ tours, c'est juste après $k+1$ tours.

Exemple:

Une boucle ajoute $1, 2, 3, \dots$ à un total. La récurrence démontre qu'après $n$ tours, le total vaut $\dfrac{n(n+1)}{2}$ .

1Essaie par toi-même

Un programme additionne les nombres de $1$ à $100$ dans une boucle.

Quel total le programme affiche-t-il ?

Étape 1 : Écris l'expression mathématique

Utilise $\dfrac{n(n+1)}{2}$ avec $n = 100$ :

Les tours de Hanoï

Dans ce casse-tête, tu déplaces une pile de disques sur une autre tige, un disque à la fois, sans jamais poser un grand disque sur un plus petit. La récurrence démontre qu'il faut $2^n - 1$ coups pour $n$ disques.

Exemple:

Pour déplacer $k+1$ disques, on déplace les $k$ disques du haut, puis le plus grand disque, puis on remet les $k$ disques par-dessus : $2(2^k - 1) + 1 = 2^{k+1} - 1$ coups.

2Essaie par toi-même

Une tour a $6$ disques. Déplacer $5$ disques demande $31$ coups.

Combien de coups faut-il pour $6$ disques ?

Étape 1 : Écris l'expression mathématique

Utilise coups pour 6 disques $= 2 \cdot$ (coups pour 5 disques) $+ 1$ :

Les grains de riz sur l'échiquier

Une vieille légende : on pose $1$ grain de riz sur la première case, $2$ sur la deuxième, $4$ sur la troisième, en doublant à chaque fois. La somme des puissances de 2 donne le total.

Exemple:

Sur les $3$ premières cases, il y a $1 + 2 + 4 = 7 = 2^3 - 1$ grains.

3Essaie par toi-même

Tu remplis les $10$ premières cases. La case $10$ contient $2^9$ grains.

Combien de grains y a-t-il en tout sur les $10$ premières cases ?

Étape 1 : Écris l'expression mathématique

Utilise $1 + 2 + \dots + 2^n = 2^{n+1} - 1$ avec $n = 9$ :

Points clés

1Le raisonnement par récurrence démontre une propriété $P(n)$ pour tout entier $n$ à partir d'une valeur de départ
2Initialisation : montre que le premier cas, souvent $P(1)$ , est vrai
3Hypothèse de récurrence : suppose que $P(k)$ est vraie pour un $k$ quelconque
4Hérédité : utilise l'hypothèse pour démontrer $P(k+1)$
5Conclusion : comme une rangée de dominos, la propriété est vraie pour tout $n$
6Les deux parties sont nécessaires : une hérédité sans initialisation, ou quelques cas vérifiés sans hérédité, ne démontrent rien

Questions fréquentes

Pourquoi la récurrence démontre-t-elle vraiment la propriété pour TOUT n ?

L'initialisation donne

P(1)

. L'hérédité avec

k = 1

donne

P(2)

, avec

k = 2

elle donne

P(3)

, et ainsi de suite. Chaque entier strictement positif est atteint après un nombre fini d'étapes, donc aucun

n

n'est oublié.

L'initialisation se fait-elle toujours pour n = 1 ?

Non. Commence à la première valeur à partir de laquelle la propriété doit être vraie. La somme des puissances de 2 commence à

n = 0

. La propriété

2^n > n^2

est fausse pour

n = 2, 3, 4

(par exemple

2^4 = 16 = 4^2

) et vraie pour tout

n \ge 5

, donc cette démonstration fait l'initialisation pour

n = 5

Le raisonnement par récurrence est-il la même chose que l'induction en sciences ?

Non. L'induction en sciences devine une règle générale à partir d'exemples et peut se tromper. Le raisonnement par récurrence est une démonstration déductive : une fois l'initialisation et l'hérédité démontrées, le résultat est certain.

Qu'est-ce que la récurrence forte ?

Dans la récurrence forte, l'hypothèse suppose que

P(1), P(2), \dots, P(k)

sont toutes vraies, pas seulement

P(k)

. C'est utile quand

P(k+1)

dépend de plusieurs cas précédents, par exemple dans les démonstrations sur la décomposition en facteurs premiers.

Glossaire

Raisonnement par récurrence: Une méthode de démonstration qui prouve $P(n)$ pour tout entier $n$ à partir d'une valeur de départ, grâce à une initialisation et une hérédité
Initialisation: Le premier cas de la propriété, souvent $P(1)$ , vérifié directement
Hypothèse de récurrence: La supposition que $P(k)$ est vraie pour un entier $k$ quelconque
Hérédité: La démonstration que $P(k)$ implique $P(k+1)$ pour tout $k$ à partir de la valeur de départ
P(n): La propriété que l'on veut démontrer, écrite en fonction de l'entier $n$
Conclusion: La dernière phrase d'une démonstration par récurrence : $P(n)$ est vraie pour tout $n$ à partir de la valeur de départ

Carte des formules

Principe de récurrence

P(1) \text{ et } \big(P(k) \Rightarrow P(k+1)\big) \Rightarrow P(n) \text{ pour tout } n \ge 1

Initialisation plus hérédité démontrent la propriété pour tout $n$

Somme des n premiers entiers

1 + 2 + \dots + n = \dfrac{n(n+1)}{2}

Pour $n = 5$ : $15$

Somme des n premiers nombres impairs

1 + 3 + \dots + (2n-1) = n^2

Pour $n = 5$ : $25$

Somme des puissances de 2

1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1

Pour $n = 6$ : $127$

Plus sur ce sujet

Guide de l'enseignant: Raisonnement par récurrence

Utiliser cette leçon en classe

Pour les enseignants

Pour les élèves en difficulté:

Pour les élèves au niveau:

Pour les élèves avancés:

Contenu de la leçon

Définition

Exemples résolus

Erreurs courantes

Pourquoi c'est important

Applications dans le monde réel

Vérifier des programmes informatiques

Les tours de Hanoï

Les grains de riz sur l'échiquier

Points clés

Questions fréquentes

Glossaire

Carte des formules

Principe de récurrence

Somme des n premiers entiers

Somme des n premiers nombres impairs

Somme des puissances de 2

Plus sur ce sujet

Introduction aux preuves mathématiques

Démonstration directe

Démonstrations en deux colonnes

Démonstrations rédigées