Récurrence : somme des entiers

Énoncé

Montrer par récurrence que pour tout n 1 : _{k=1}^{n} k = 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 : [formule] Initialisation (n = 1). On calcule séparément les deux membres : à gauche _{k=1}^{1} k = 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 : [formule] Montrons P(n+1). Le geste décisif : isoler le dernier terme pour faire apparaître la somme de rang n. [formule]

   _{k=1}^{n+1} k = _{k=1}^{n} k + (n+1)

4. Étape 4 : On substitue l'hypothèse, puis on met au même dénominateur : _{k=1}^{n+1} k = 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 : [formule]

   _{k=1}^{n} k = 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 : _{k=1}^{n+1} = _{k=1}^{n} + \ (n+1). 👉 Et la factorisation vient ensuite naturellement : le terme ajouté partage presque toujours un facteur avec la formule.