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

  1. É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.
  2. É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 ✓

  3. É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)

  4. É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

  5. É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.