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.

Ressources enseignants

Raisonnement par récurrence

Q: 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é.

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.

Avancé30 minLeçon

Fiche d'exercices à imprimer

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.

Essaie tout de suite

Quelles sont les deux parties que doit contenir toute démonstration par récurrence ?

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$ .

Visuel interactif

Explorateur de suites

Premier terme (a₁ = 1)

Raison (d = 2)

11,

13,

, ...

Formule

a_n = 1 + 2(n - 1) = 2n - 1

Formule de somme: S_8 = 8/2 × (2×1 + 7×2) = 64

Sommes partielles

S₁ = 1S₂ = 4S₃ = 9S₄ = 16S₅ = 25S₆ = 36S₇ = 49S₈ = 64

a_1

a_5

a_10

a_20

Explorateur de suites

Premier terme (a₁ = 1)

Raison (r = 2)

16,

32,

64,

128

, ...

Formule

a_n = 1 × 2^(n-1)

Formule de somme: S_8 = 1 × (1 - 2^8) / (1 - 2) = 255

Sommes partielles

S₁ = 1S₂ = 3S₃ = 7S₄ = 15S₅ = 31S₆ = 63S₇ = 127S₈ = 255

|r| ≥ 1 : les sommes partielles ne se rapprochent d'aucune valeur, la série infinie n'a pas de somme.

a_1

a_5

a_10

512

a_20

524 288

Bac à sable interactif

Calculatrice d'expressions

Essaie ceux-ci :

Historique

Aucun calcul pour l'instant

Exercices pratiques

18 exercices

Problème 1 sur 18

Facile

Quelles sont les deux parties que doit contenir toute démonstration par récurrence ?

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

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é.

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

Définition

Exemples résolus

Erreurs courantes

Visuel interactif

Explorateur de suites

Formule

Sommes partielles

Explorateur de suites

Formule

Sommes partielles

Bac à sable interactif

Calculatrice d'expressions

Historique

Exercices pratiques

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