Somme des n premiers entiers strictement positifs

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

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

Somme des n premiers nombres impairs

Démontre que $1 + 3 + 5 + \dots + (2n-1) = n^2$ pour tout $n \ge 1$.

Initialisation : vérifie $n = 1$: Membre de gauche : $1$. Membre de droite : $1^2 = 1$ = $P(1)$ est vraie

Hypothèse de récurrence: Supposons $1 + 3 + \dots + (2k-1) = k^2$ pour un $k \ge 1$ = On peut utiliser cette égalité

Trouve le nombre impair suivant: Le nombre impair après $2k-1$ est $2(k+1) - 1 = 2k + 1$ = On ajoute $2k + 1$

Hérédité: $1 + 3 + \dots + (2k-1) + (2k+1) = k^2 + 2k + 1$ = $= (k+1)^2$, donc $P(k+1)$ est vraie

Answer: Par récurrence, la somme des $n$ premiers nombres impairs vaut $n^2$. Vérification : $1 + 3 + 5 + 7 + 9 = 25 = 5^2$.

Somme des puissances de 2

Démontre que $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ pour tout $n \ge 0$.

Initialisation : ici la première valeur est $n = 0$: Membre de gauche : $2^0 = 1$. Membre de droite : $2^{1} - 1 = 1$ = $P(0)$ est vraie

Hypothèse de récurrence: Supposons $1 + 2 + \dots + 2^k = 2^{k+1} - 1$ pour un $k \ge 0$ = On peut utiliser cette égalité

Hérédité : ajoute le terme suivant $2^{k+1}$: $1 + 2 + \dots + 2^k + 2^{k+1} = 2^{k+1} - 1 + 2^{k+1}$ = $= 2 \cdot 2^{k+1} - 1$

Simplifie et compare avec $P(k+1)$: $2 \cdot 2^{k+1} - 1 = 2^{k+2} - 1 = 2^{(k+1)+1} - 1$ = $P(k+1)$ est vraie

Answer: Par récurrence, $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ pour tout $n \ge 0$. Vérification pour $n = 6$ : $1 + 2 + 4 + 8 + 16 + 32 + 64 = 127 = 2^7 - 1$.

Une démonstration de divisibilité

Démontre que $n^3 - n$ est divisible par $3$ pour tout $n \ge 1$. (La leçon Démonstration directe l'a montré en factorisant ; ici, on utilise la récurrence.)

Initialisation : vérifie $n = 1$: $1^3 - 1 = 0 = 3 \cdot 0$ = $P(1)$ est vraie

Hypothèse de récurrence: Supposons $k^3 - k = 3m$ pour un entier $m$ = $k^3 - k$ est un multiple de $3$

Développe l'expression pour $k+1$: $(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1$ = $= (k^3 - k) + 3k^2 + 3k$

Utilise l'hypothèse de récurrence: $(k^3 - k) + 3k^2 + 3k = 3m + 3(k^2 + k)$ = $= 3(m + k^2 + k)$

Conclus: $m + k^2 + k$ est un entier, donc l'expression est un multiple de $3$ = $P(k+1)$ est vraie

Answer: Par récurrence, $3$ divise $n^3 - n$ pour tout $n \ge 1$. Vérification pour $n = 5$ : $125 - 5 = 120 = 3 \cdot 40$.

Une inégalité : 2 puissance n est plus grand que n

Démontre que $2^n > n$ pour tout $n \ge 1$.

Initialisation : vérifie $n = 1$: $2^1 = 2$ et $2 > 1$ = $P(1)$ est vraie

Hypothèse de récurrence: Supposons $2^k > k$ pour un $k \ge 1$ = On peut utiliser cette inégalité

Écris $2^{k+1}$ à l'aide de $2^k$: $2^{k+1} = 2 \cdot 2^k > 2 \cdot k$ = $2^{k+1} > 2k$

Compare $2k$ et $k+1$: $2k = k + k \ge k + 1$, car $k \ge 1$ = $2k \ge k + 1$

Enchaîne les inégalités: $2^{k+1} > 2k \ge k + 1$ = $2^{k+1} > k + 1$, donc $P(k+1)$ est vraie

Answer: Par récurrence, $2^n > n$ pour tout $n \ge 1$. Par exemple, $2^{10} = 1024 > 10$.

Mistake: Oublier l'initialisation

Why: 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.

Mistake: Supposer ce que l'on veut démontrer

Why: É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.

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

Why: 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.

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

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

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.

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

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.

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.

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.

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

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

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

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

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

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

A: 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.

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

A: 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.