Récurrence : somme des entiers
Énoncé
Montrer par récurrence que pour tout n ≥ 1 : 1 + 2 + ⋯ + n = (n(n+1))/2.
Indice : Pose P(n) : « 1 + 2 + ⋯ + n = (n(n+1))/2 ». Vérifie P(1), puis suppose P(n) et montre P(n+1).
Correction
- Étape 1 : La récurrence est le seul moyen de démontrer une propriété pour une infinité d'entiers en un nombre fini de lignes. Elle suit toujours le même plan.
Les quatre temps d'une récurrence :
1. Énoncer P(n) — la phrase que l'on démontre, écrite proprement ;
2. initialisation : vérifier P au premier rang ;
3. hérédité : supposer P(n) pour un n fixé, en déduire P(n+1) ;
4. conclure en invoquant le principe de récurrence.
👉 L'image des dominos éclaire le mécanisme : l'initialisation fait tomber le premier, l'hérédité garantit que chacun fait tomber le suivant. Sans le premier, rien ne tombe ; sans la propagation, un seul tombe. Il faut les deux.
⚠️ Le geste technique de l'hérédité est toujours le même : faire apparaître le membre de gauche de P(n) dans celui de P(n+1), pour pouvoir y substituer l'hypothèse.
- Étape 2 : L'énoncé de la propriété. Posons, pour n ≥ 1 :
P(n) : 1 + 2 + ⋯ + n = (n(n+1))/2
Initialisation (n = 1). On calcule séparément les deux membres :
à gauche, la somme se réduit à 1 ; à droite, (1 × 2)/2 = 1.
Les deux valent 1, donc P(1) est vraie.
P(1) : 1 = (1 × 2)/2 = 1 ✓
- Étape 3 : Hérédité. Soit n ≥ 1 fixé, et supposons P(n) vraie :
1 + 2 + ⋯ + n = (n(n+1))/2 (hypothèse de récurrence)
Montrons P(n+1). Le geste décisif : isoler le dernier terme pour faire apparaître la somme de rang n.
1 + 2 + ⋯ + (n+1) = 1 + 2 + ⋯ + nₒₙ y ₐₚₚₗᵢqᵤₑ ₗ'ₕyₚₒₜₕèₛₑ + (n+1)
1 + 2 + ⋯ + (n+1) = (1 + 2 + ⋯ + n) + (n+1)
- Étape 4 : On substitue l'hypothèse, puis on met au même dénominateur :
1 + 2 + ⋯ + (n+1) = (n(n+1))/2 + (n+1) = (n(n+1) + 2(n+1))/2
On factorise par (n+1), qui est présent dans les deux termes :
= ((n+1)(n+2))/2
👉 C'est exactement P(n+1) : la formule au rang n+1 s'écrit ((n+1)((n+1)+1))/2 = ((n+1)(n+2))/2. On a bien obtenu ce qu'il fallait.
Conclusion. P(1) est vraie et P est héréditaire, donc par le principe de récurrence :
1 + 2 + ⋯ + n = (n(n+1))/2 pour tout n ≥ 1
1 + 2 + ⋯ + n = (n(n+1))/2
- Étape 5 : L'erreur classique :
Écrire l'hérédité en partant de P(n+1) et en « arrivant » à P(n).
C'est raisonner à l'envers : on suppose ce qu'on veut démontrer. La bonne direction est hypothèse → conclusion, et elle s'écrit en partant du membre de gauche de P(n+1) pour le transformer.
👉 Second piège : oublier de dire « pour un n fixé ». Sans cela, on aurait l'air de supposer la propriété pour tous les n — c'est-à-dire de supposer ce qu'on démontre.
À retenir :
Isoler le dernier terme est le geste standard d'une récurrence sur une somme : la somme jusqu'au rang n+1 est la somme jusqu'au rang n, plus le terme de rang n+1 (ici n+1 ; pour la somme des carrés, (n+1)²).
👉 Et la factorisation vient ensuite naturellement : le terme ajouté partage presque toujours un facteur avec la formule.