Sommes des puissances

Auteur : Maxime Bourrigan, responsable éditorial du site Culture Math.

Cet article est disponible au format pdf.


Sommaire

1. Premiers résultats, premières preuves

  Somme des entiers

  Somme des carrés

  Somme des cubes

2. Il existe une formule...

  Preuve par les sommes télescopiques

  Preuve par intégration discrète

  Les formules !

3. Formule de Bernoulli

  Énoncé

  Preuve


« Dans les années 1780, un instituteur allemand de province donna à sa classe la tâche fastidieuse d'additionner les 100 premiers entiers. Le but de cet enseignant était d'obtenir le silence pendant une demi-heure, mais un jeune élève donna presque immédiatement une réponse : $1 + 2 + 3 + \cdots + 98 + 99 + 100 = 5\,050$. Le monsieur je-sais-tout était Carl Friedrich Gauss, qui deviendrait plus tard un des plus sérieux candidats au titre de plus grand mathématicien de tous les temps. Gauss n'était pas seulement un calculateur prodige et n'avait pas simplement fait cette addition de tête. Il avait eu une idée plus profonde : si vous « pliez » la suite des cent premiers nombres et que vous en faites la somme deux par deux ($1 + 100$, $2 + 99$, $3 + 98$, etc.), toutes ces sommes font 101. Il y a 50 telles sommes, donc le total est simplement $50 \times 101$. La formule générale, pour la somme des nombres entiers de $1$ à $n$, est $\frac{n (n+1)}{2}$. »

Bien que probablement apocryphe, cette anecdote¹ est probablement une des histoires les plus connues concernant un mathématicien. L'une des raisons en est sans doute qu'elle illustre de façon frappante une preuve très élégante d'une formule elle-même très connue.

Le but de cet article est de discuter de cette formule : $$\sum_{k=1}^n k = 1 + 2 + \cdots + n = \frac{n(n+1)}2$$ et de ses généralisations à la somme des puissances $p$-ièmes de $n$ premiers nombres entiers $$F_p(n) = \sum_{k=1}^n k^p = 1^p + 2^p + \cdots + n^p. $$

1. Premiers résultats, premières preuves.

Somme des entiers

Comme le dit l'anecdote concernant Gauss, la formule exprimant $F_1(n) = \sum_{k=1}^n k$ peut se démontrer simplement, en regroupant les termes deux à deux.


On peut également donner une représentation géométrique de cette preuve.

Somme des carrés

On apprend souvent aussi (mais sans doute un peu plus tard) les compagnons de cette formule : $$\begin{align*} F_2(n) &= 1^2 + 2^2 + 3^2 + \cdots + (n-1)^2 + n^2 = \frac{n(n+1)(2n+1)}6\\ F_3(n) &= 1^3 + 2^3 + 3^3 + \cdots + (n-1)^3 + n^3 = \frac{n^2(n+1)^2}4.\end{align*}$$

Pour ces formules, aucune preuve n'est aussi lumineuse que celle attribuée à Gauss par la célèbre anecdote. Mais il existe quand même des preuves éclairantes. Par exemple, on trouve dans le formidable livre Proofs without words² l'image suivante :

Une autre preuve « géométrique » donnée dans le même livre mérite sans doute un peu d'explication.

Dans ces dessins, on a inscrit des entiers dans un triangle, à la manière du triangle de Pascal. Les trois triangles qui sont « ajoutés » sont en fait les mêmes, à une rotation près. Dans celui du milieu, on voit qu'il y a un « 1 » dans la première ligne, deux « 2 » dans la deuxième, etc. La somme des entiers présents dans le triangle vaut donc $1 \times 1 + 2 \times 2 + \cdots + n \times n = F_2(n)$.

Or, on voit que la somme des trois triangles n'affiche qu'une seule valeur : $2n+1$. On a donc l'égalité $$3 F_2(n) = (n+1) \times C,$$ où $C$ est le nombre de cases du triangle. Mais cet entier vaut exactement $1 + 2 + \dots + n = \frac{n(n+1)}2$, et on obtient donc bien $F_2(n) = \frac{n(n+1)(2n+1)}6$.

On trouvera encore d'autres preuves de cette égalité sur le fil de discussion consacré à cette question sur le site Mathematics Stack Exchange. Il ne tient qu'à vous d'en rajouter !

Somme des cubes

Une assez belle preuve de la formule $$F_3(n) = 1^3 + 2^3 + 3^3 + \cdots + (n-1)^3 + n^3 = \frac{n^2(n+1)^2}4 = F_1(n)^2$$ date de 1854 et est due à Charles Wheatstone³. Elle part de la figure où l'on inscrit les premiers nombres impairs dans un triangle de taille $n$.

On observe alors que la $k$-ième ligne du triangle porte $k$ nombres, dont la moyenne est précisément $k^2$. Ainsi, la somme de ces valeurs est $k^3$, et la somme des valeurs du triangle vaut $F_3(n)$. Comme le triangle a $F_1(n) = \frac{n(n+1)}2$ cases, on a bien $$\begin{align*} F_3(n) &= \sum_{k=1}^{F_1(n)} (2k-1) \\ &= 2 \left( \sum_{k=1}^{F_1(n)} k \right) - F_1(n) \\ &= 2 F_1(F_1(n)) - F_1(n) \\ &= F_1(n)^2 + F_1(n) - F_1(n) = F_1(n)^2. \end{align*}$$

Avant de passer à la suite, remarquons qu'une fois que l'on connaît ces trois formules, les démontrer par récurrence est facile. Ce qui l'est moins, c'est de retrouver la formule quand on l'a oubliée !

2. Il existe une formule...

Les trois formules pour $F_1(n)$, $F_2(n)$ et $F_3(n)$ soulèvent naturellement la question de savoir si une formule existe plus généralement pour les $F_p(n)$. Contentons-nous pour l'instant de montrer qu'il existe une telle formule et de donner quelques renseignements sur elle, sans véritablement l'exhiber.

Théorème. $F_p(n)$ est un polynôme de degré $p+1$ en $n$.

On va en fait donner deux preuves différentes de ce résultat.

Preuve par les sommes télescopiques

On a déjà vu des cas particuliers de ce théorème pour $p = 1$, $2$ ou $3$ (ou même pour $p=0$, où $F_0(n) = n$, si on aime la zérologie). Cela permet d'envisager une preuve par récurrence. Supposons donc le résultat démontré pour tous les polynômes $F_{q}(n)$, avec $q < p$. L'astuce consiste alors à considérer la somme $$Q_p(n) = \sum_{k=1}^{n} \left[(k+1)^{p+1} - k^{p+1}\right].$$

D'un côté, cette somme est télescopique : la première partie du $k$-ième terme se simplifie avec la seconde du $(k+1)$-ième. Il ne reste donc que les termes extrêmes, c'est-à-dire que $Q_p(n) = (n+1)^{p+1} - 1^{p+1} = (n+1)^{p+1} - 1$. En particulier, on voit que $Q_p$ est un polynôme unitaire de degré $p+1$.

D'un autre côté, on peut développer le terme $(k+1)^{p+1} - k^{p+1}$ en utilisant la formule du binôme de Newton. En prenant son courage à deux mains, on obtient $$\begin{align*} Q_p(n) &= \sum_{k=1}^n \left[ \sum_{q=0}^{p} \binom{p+1}{q} k^q\right]\\ &= \sum_{q=0}^p \binom{p+1}{q} \sum_{k=1}^n k^q \\ &= \sum_{q=0}^p \binom{p+1} q F_q(n).\end{align*}$$

Puisque par hypothèse de récurrence chaque polynôme $F_q$ $(q<p)$ est de degré $q+1\leq p$, on voit que $\deg F_p = \deg Q_p = p+1$, ce qui conclut la démonstration.

Par ailleurs, on voit même que le coefficient dominant de $F_p$ est celui de $Q_p$ (c'est-à-dire $1$) divisé par $\binom{p+1}{p} = p+1$.

Preuve par intégration discrète

Une autre manière de démontrer cette formule est de constater que l'opération permettant de passer de $n^p$ à $F_p(n)$ s'apparente à la prise d'une primitive. Détaillons cela.

Pour les suites ou les fonctions définies sur les entiers, l'opération de dérivation a une cousine, que l'on appelle parfois dérivée discrète ou opérateur aux différences finies. Si $f$ est une fonction, on définit simplement $\Delta f$ par la formule $(\Delta f)(n) = f(n+1) - f(n)$. D'une certaine façon, on a « discrétisé » la dérivée : au lieu de regarder ce que fait le quotient $\frac{f(x+\epsilon) - f(x)}{\epsilon}$ quand $\epsilon \to 0$, on a simplement remplacé $\epsilon$ par $1$.

Cet opérateur garde certaines des propriétés de la différentiation des fonctions, et une habitude en mathématiques discrètes est de filer cette métaphore. Par exemple, $\Delta$ abaisse strictement le degré des polynômes : à cause du binôme de Newton, les termes de degré $m$ de  $\Delta x^m = (x+1)^m - x^m$ s'annulent, donc $\deg(\Delta x^m) < m$. Cette propriété va nous permettre de démontrer le résultat : considérons la restriction $\Delta_m$ de l'opérateur $\Delta$ à l'espace vectoriel $\mathbb R[X]_{\leq m}$ des polynômes de degré $\leq m$. Une manière de reformuler ce que l'on vient de dire est $\textrm{im}(\Delta_m) \subseteq \mathbb R[X]_{\leq m-1}$.

En fait, on doit même avoir $\textrm{im}(\Delta_m) = \mathbb R[X]_{\leq m-1}$ : en effet, les seuls polynômes $P$ tels que $\Delta P = 0$ sont les polynômes constants (un polynôme périodique est nécessairement constant). On a donc $\dim \ker(\Delta_m) = 1$, ce qui entraîne $$\dim \textrm{im}(\Delta_m) = \dim \mathbb R[X]_{\leq m} - 1 = \mathbb R[X]_{\leq m-1}.$$

Ainsi, tout polynôme de degré $p$ a une « primitive discrète » de degré $p+1$, unique à l'addition près d'une constante. Cela démontre le théorème, car par définition, $\Delta F_p(n) = (n+1)^p$.

Les formules !

Une fois que l'on a démontré le résultat, on peut facilement obtenir les formules, à condition d'avoir du courage ou un ordinateur sous la main ! Pour s'en convaincre, déterminons la formule pour $F_4(n)$. On sait qu'il s'agit d'un polynôme $a_5 n^5 + a_4 n^4 + a_3 n^3 + a_2 n^2 + a_1 n + a_0$ de degré $5$ tel que les six premières valeurs $F_5(1)$, $F_5(2)$, $\ldots$, $F_5(6)$ sont les sommes des premières puissances quatrièmes, c'est-à-dire $1$, $17$, $98$, $354$, $979$ et $2\,275$, respectivement. Comme six valeurs déterminent uniquement un polynôme de degré $5$, il n'y a plus qu'à résoudre un système linéaire (un peu pénible) pour obtenir la formule.

$$F_4(n) = \frac 15 n^5 + \frac 12 n^4 + \frac 13 n^3 - \frac{1}{30}n.$$

On peut ainsi obtenir les premières formules pour les $F_n$. Notons que les deux preuves que l'on a données permettent également de trouver ces formules : dans le premier cas, on a obtenu une formule de récurrence exprimant $F_p$ en fonction des $F_q$, $q < p$ et dans l'autre, on peut mettre sur pied un « calcul intégral » suffisant pour obtenir des formules explicites.

Nous allons voir dans la section suivante qu'il existe en fait une formule générale pour exprimer la somme $F_p(n) = 1^p + 2^p + \cdots + n^p$, mettant en jeu une famille de nombres remarquables.

3. Formule de Bernoulli

Les formules que nous venons d'indiquer présentent beaucoup de phénomènes réguliers : $F_p(n)$ est un polynôme dont le terme dominant est $\frac{1}{p+1} n^{p+1}$, on l'a vu, mais c'est loin d'être la seule chose à remarquer :

En fait, toutes ces expressions sont des manifestations d'une unique formule, que l'on peut énoncer comme suit.

Théorème. Pour tout $p$, on a $$F_p(n) = \sum_{k=1}^n n^k = \frac{1}{p+1} \sum_{q=0}^{p} \binom{p+1}{q} B_q n^{p+1-k},$$ où les nombres $B_q$, appelés nombres de Bernoulli, sont définis par $B_0 = 1$ et la relation de récurrence $\sum_{i=0}^m (-1)^i \binom m i B_i = 0$ pour tout $m > 0$.

Cette formule a été en substance énoncée par Jakob Bernoulli dans son ouvrage Ars Conjectandi. Bernoulli y donne en particulier les formules pour les $F_n$ que nous avons données à la section précédente. Il affirme d'ailleurs avoir été capable de calculer la somme des mille premières puissances dixièmes intra semi-quadrantem horæ, c'est-à-dire en moins d'un demi-quart d'heure. Comme on le voit sur ces images, il donne même la valeur...

Vérifions les premiers cas de la formule de Bernoulli :

De manière générale, on voit que $B_n$ est le coefficient devant $n$ dans l'expression de $F_n$. À partir de $B_3$, tous les nombres de Bernoulli impairs sont nuls et les signes des pairs alternent, ce qui explique une bonne partie de nos remarques sur les expressions de $F_n$. Les premiers nombres de Bernoulli non nuls sont donnés dans le tableau suivant.

Depuis leur apparition dans ce contexte, les nombres de Bernoulli sont devenus une suite célèbre de nombres rationnels. Ils interviennent dans des contextes qui ont l'air très différents de ceux pourquoi ils ont été découverts (par exemple dans les développents de Taylor des fonctions $\tan$ et $\mathrm{th}$), et très différents entre eux. Pour donner deux exemples qui dépassent de loin le cadre de cet article, la suite des numérateurs des nombres de Bernoulli apparaît dans une caractérisation des nombres premiers réguliers, introduits par Kummer lors de sa preuve partielle du grand théorème de Fermat et la suite de leurs dénominateurs est un élément essentiel de la classification des sphères exotiques, un des joyaux de la topologie en grande dimension dont la découverte a valu à John Milnor la médaille Fields en 1962.

Preuve de la formule de Bernoulli

Pour les plus courageux, vérifions la formule !

On suppose donc les nombres de Bernoulli définis par la relation de récurrence et $B_0 = 1$, ce que l'on peut encore réécrire $$\sum_{j=0}^m (-1)^i \binom{m+1}i B_i = [m =0],$$ où l'expression $[m=0]$ signifie le nombre valant $1$ si $m = 0$ et $1$ sinon (c'est un crochet d'Iverson).

D'après ce que l'on a dit à la section 2, il suffit en fait de vérifier que l'expression $$\psi_p(n) = \sum_{q=0}^p \binom{p+1}q B_q n^{p-q+1},$$ vérifie $\psi_p(n) - \psi_p(n-1) = (p+1) n^p.$ Cela entraînerait en effet que $\frac{1}{p+1} \psi_p(n)$, qui est l'expression du théorème de Bernoulli, serait un antécédant de la fonction $n \mapsto n^p$ par l'opérateur aux différences finies, comme la somme $F_p$. Mais on a vu qu'un tel antécédant est unique à une constante additive près. Or, puisque $\psi_p(n) = \psi_p(n-1) + (p+1) n^p$ et que manifestement, $\psi_p(0) = 0$, on a bien $\psi_p(1) = p+1$, ce qui implique que $\frac 1{p+1} \psi_p$ et $F_p$ coïncident pour au moins une valeur de $n$. Ils sont donc égaux.

Lançons-nous dans le calcul !

$$\begin{align*} \psi_p(n) - \psi_p(n-1) &= \sum_{q=0}^p \binom{p+1}q B_q \left[ n^{p-q+1} - (n-1)^{p-q+1}\right] \\ &= \sum_{q=0}^p \binom{p+1}q B_q \left[ n^{p-q+1} - \sum_{i=0}^{p-q+1} \binom{p-q+1}{i} n^i (-1)^{p-q-i+1}  \right] \\ &= \sum_{q=0}^p \binom{p+1}q B_q \sum_{i=0}^{p-q} \binom{p-q+1}{i} n^i (-1)^{p-q-i} \\ &= \sum_{\substack{0 \leq q, i \\ i+q \leq p}} (-1)^{p-q-i} \binom{p+1}q \binom{p-q+1}i B_q n^i \\ &= \sum_{\substack{0 \leq q, i \\ i+q \leq p}} (-1)^{p-q-i} \binom{p+1}i \binom{p-i+1}q B_q n^i \\ &= \sum_{i=0}^p (-1)^{p-i} \binom{p+1} i \left[ \sum_{q=0}^{p-i} (-1)^q \binom{p-i+1}{q} B_q \right] n^i \\ &= \sum_{i=0}^p (-1)^{p-i} \binom{p+1} i [p-i=0] n^i \\ &= \binom{p+1}p n^p = (p+1) n^p.\end{align*}$$

Cela conclut la preuve. Remarquez qu'on a utilisé l'identité $\binom n a \binom{n-a} b = \binom n b \binom{n-b} a$. Cette dernière est facile à vérifier à partir de l'expression des coefficients binomiaux, mais on peut également la démontrer combinatoirement : si on a $n$ boules numérotées, de combien de façon peut-on en colorier $a$ en bleu et $b$ en rouge ?

Pour finir, signalons une manière étonnante de noter le théorème de Bernoulli et la définition par récurrence des nombres $B_n$. Dans The Book of Numbers, John H. Conway et Richard Guy notent les nombres de Bernoulli $B^k$. Bien sûr, cette expression ne signifie pas que $B^k$ est la $k$-ième puissance d'un nombre $B$. Cependant, si l'on développe l'expression $\frac{(n+B)^{p+1} - n^{p+1}}{p+1}$ selon le binôme de Newton et que l'on interprète après coup $B^k$ comme le $k$-ième nombre de Bernoulli, on retombe sur l'expression de $F_p(n)$ ! De même, la définition par récurrence des nombres de Bernoulli s'écrit dans ce « formalisme » $(B-1)^k = B^k$. Nous laisserons au lecteur interloqué le soin de juger sur pièces l'utilisation que Conway et Guy font de cette « notation » dans The Book of Numbers, mais on ne peut en tout cas pas nier l'intérêt mnémotechnique de cette notation un peu cavalière...


NOTES :

[1] La version citée ici est (ma propre traduction de) celle utilisée dans l'article « Gauss's Day of Reckoning » de Brian Hayes, dans laquelle l'auteur revient sur les origines historiques de cette anecdote. Cette autre page recense plus d'une centaine de versions de ladite anecdote.

[2] Roger B. Nelsen, Proofs without words: Exercises in visual thinking, Mathematical Association of America, 1993. Dans ce livre, la preuve précédente est attribuée à Man-Keung Siu et la prochaine à Sidney H. Kung.

[3] Charles Wheatstone, On the Formation of Powers from Arithmetical Progressions, Proceedings of the Royal Society of London 7 (1854), p. 145-151.

[4] Il est en fait possible d'être un peu plus malin et de prolonger $F_p$ sur les nombres négatifs ou nuls pour pouvoir utiliser des équations avec des coefficients moins élevés (tels que $F_p(0)$). Pour cela, il faut que les preuves précédentes s'appliquent, c'est-à-dire qu'il faut prolonger $F_p$ de telle sorte que $\forall n \in \mathbb Z, F_p(n+1) - F_p(n) = (n+1)^p$. Mais cette astuce n'empêche pas les systèmes linéaires de devenir pénible très vite.

[5] La « star » dans ce domaine est la fonction $x^{\underline m} = x (x-1) \cdots (x-m+1)$. Cette fonction vérifie $\Delta x^{\underline m} = m x^{\underline{m-1}}$ et joue donc pour l'opérateur $\Delta$ un rôle similaire à celui que jouent les fonctions puissances dans le calcul différentiel classique. D'une certaine façon, travailler avec l'opérateur $\Delta$ revient dans une large mesure à travailler dans la base $(x^{\underline m})_{m \in \mathbb N}$ de $\mathbb R[X]$ plutôt que dans la base canonique.

[6] Il existe une ambiguïté pour $B_1$ : selon certains auteurs, $B_1 = -\frac 1 2$. Cela est dû au fait que ces auteurs considèrent plutôt la somme $S_p(n) = \sum_{k=0}^{p-1} k^p = F_p(n) - n^p$ : puisque le coefficient devant $n^p$ vaut $\frac 12$ pour la somme $F_p(n)$, il vaudra $- \frac 1 2$ pour la somme $S_p$. C'est vraiment une question de choix : si on choisit $B_1 = - \frac 12$, la formule de Bernoulli, sans modification, calcule $S_p(n)$. Cela a au moins deux avantages : les signes dans les expressions de $S_p(n)$ sont vraiment alternants (y compris les tout premiers) et le coefficient $\pm 1$ disparaît dans la définition par récurrence des nombres de Bernoulli. Le choix $B_1 = - \frac 12$ est par exemple fait dans l'excellent Mathématiques concrètes de Graham, Knuth et Patashnik. Dans The Book of Numbers, Conway et Guy font le même choix que nous.

[7] La théorie des séries génératrices est un outil puissant pour démontrer des identités comme celles de Bernoulli. On renvoie par exemple à la section 7.6 de Mathématiques concrètes de Graham, Knuth et Patashnik pour une preuve du théorème de Bernoulli dans ce cadre.