Problème — Anatomie logique d'une démonstration par récurrence

• $P(n)$ est la proposition « $\sum _{i=1}^{n}i=\frac{n(n+1)}{2}$ ». Prise isolément, $P(n)$ n'est ni vraie ni fausse : elle dépend de la variable $n$. L'énoncé à démontrer, « pour tout $n\ge 1$, $P(n)$ », est une quantification universelle : c'est une infinité de propositions à établir d'un seul geste — d'où la nécessité d'un raisonnement particulier.

• L'hérédité s'écrit : « pour tout entier $k\ge 1$, $P(k)⟹P(k+1)$ ». C'est donc elle aussi une quantification universelle, mais portant sur une implication.

Ce qu'elle démontre : que la vérité se transmet d'un rang au suivant. Ce qu'elle ne démontre pas : aucune des propositions $P(n)$. Une implication ne dit rien de la vérité de son hypothèse ; elle dit seulement ce qui se passerait si l'hypothèse était vraie.

• Rédaction annotée :

• Initialisation — on établit une proposition unique, $P(1)$ : pour $n=1$, $S_1=1$ et $\frac{1\times 2}{2}=1$, donc $P(1)$ est vraie.
• Hérédité — on fixe un entier $k\ge 1$ quelconque et on suppose $P(k)$ vraie ; c'est l'hypothèse de récurrence, et non une affirmation. On calcule alors

$$S_{k+1}=S_k+(k+1)\underset{\text{hyp. de reˊcurrence}}{=}\frac{k(k+1)}{2}+(k+1)=(k+1)\left(\frac{k}{2}+1\right)=\frac{(k+1)(k+2)}{2},$$

ce qui est exactement $P(k+1)$. On a donc établi $P(k)⟹P(k+1)$, et comme $k$ était quelconque, cela vaut pour tout $k\ge 1$.

• Conclusion — l'initialisation amorce la chaîne, l'hérédité la propage : pour tout $n\ge 1$, $P(n)$ est vraie.

Remarquons le statut du « soit $k$ quelconque » : c'est ainsi que l'on démontre une proposition universelle. On ne traite pas tous les cas un par un, on en traite un seul en n'utilisant rien qui lui soit propre.

• Supposons $Q(k)$ vraie pour un entier $k\ge 0$ : il existe $a\in \mathbb{Z}$ tel que $4^k+1=3a$, donc $4^k=3a-1$. Alors

$$4^{k+1}+1=4\times 4^k+1=4(3a-1)+1=12a-3=3(4a-1),$$

et $4a-1$ est un entier : $Q(k+1)$ est vraie. La propriété $Q$ est donc héréditaire.

Pourtant elle est fausse partout : $4^0+1=2$, $4^1+1=5$, $4^2+1=17$, aucun n'est multiple de $3$. L'étape omise est l'initialisation — et elle est ici impossible à établir, précisément parce que la propriété est fausse. La chaîne d'implications est intacte, mais rien ne l'amorce. C'est le domino parfaitement aligné que personne ne pousse.

• Non : le symbole $\Sigma$ n'est qu'une abréviation de $1+2+\cdots +n$. Il rend l'énoncé plus court et plus net, mais toute la démonstration s'est faite sur l'égalité $S_{k+1}=S_k+(k+1)$, c'est-à-dire sur la signification de la somme et non sur une manipulation du symbole. C'est exactement l'usage attendu : $\Sigma$ sert à écrire.