Éducation Nationale Française · PTSI

Compléments de calcul algébrique

⌚ ~586 min ▢ 71 blocs ✓ 306 exercices PDFCours complet PDFFiche d'exercices PDFCorrections ➣ Prérequis : Logique, Formule du binôme de Newton

Ce chapitre entraîne les outils de calcul dont se servent tous les chapitres suivants. Quatre sections viennent du cours commun. Sommes et produits : les notations $\sum$ et $\prod$, la linéarité, le changement d'indice, la relation de Chasles, la factorielle. Télescopage et sommes classiques : sommes et produits télescopiques, sommes des premiers entiers, de leurs carrés et de leurs cubes, somme géométrique. Sommes doubles : sommes sur un rectangle et sur un triangle, et l'échange de l'ordre de sommation. Coefficients binomiaux : $\binom{n}{p}$, la relation et le triangle de Pascal, et la formule du binôme.
De nombreuses démonstrations se font par récurrence sur $n$ ou par un changement d'indice soigné, les techniques du chapitre sur le raisonnement.
Une cinquième section donne ensuite les bases de l'arithmétique dans $\mathbb{Z}$, la boîte à outils sur les entiers dont on se servira tout au long du cours : la relation de divisibilité $b \mid a$ et la division euclidienne $a = bq + r$ ; le plus grand commun diviseur $a \wedge b$ calculé par l'algorithme d'Euclide, et le plus petit commun multiple $a \vee b$ ; les nombres premiers, l'infinitude de $\mathbb{P}$, et la décomposition d'un entier en produit de nombres premiers.

Signaler une erreur

I Sommes et produits

Sommes et produits comme raccourci

Les symboles $\sum$ et $\prod$ abrègent une somme et un produit qu'il serait pénible d'écrire en extension. Ils sont définis par récurrence sur la borne supérieure puis sur un ensemble fini ; les règles par lesquelles on les manie — comment couper une somme, regrouper ses termes par paquets, changer son indice — sont démontrées ; et la factorielle, le premier produit que rencontre tout calcul, est un produit d'entiers consécutifs.

Signaler une erreur

I.1 Sommes finies

Sommer terme après terme

Le lycée a écrit la somme $a_m + a_{m+1} + \dots + a_n$ avec le symbole $\sum$ et l'a lue comme une boucle qui ajoute un terme après l'autre. La Définition « Notation sigma » fait de cette lecture une définition par récurrence sur la borne supérieure, ce qui permet de démontrer chaque règle de calcul. La Définition « Somme sur un ensemble fini » somme sur un ensemble fini d'indices quelconque, pas nécessairement une liste d'entiers consécutifs : c'est le support des sommes doubles, dont les indices sont des couples, et des paquets, qui sont des parties de l'ensemble des indices.

Signaler une erreur

Définition — Notation sigma

Soient $m, n \in \mathbb{Z}$, et $a_k$ un réel pour chaque entier $k$ tel que $m \le k \le n$. La somme $\sum_{k=m}^{n} a_k$ est définie par récurrence sur $n$ :

somme vide : $\sum_{k=m}^{n} a_k = 0$ lorsque $n < m$ ;
ajout d'un terme : $\sum_{k=m}^{n+1} a_k = \sum_{k=m}^{n} a_k + a_{n+1}$ pour tout $n \ge m - 1$.

Pour $n \ge m$, c'est la forme développée $\sum_{k=m}^{n} a_k = a_m + a_{m+1} + \dots + a_n$, somme de $n - m + 1$ termes. La lettre $k$ est l'indice de la somme, $m$ et $n$ sont ses bornes, et $a_k$ est son terme général.

Définition — Somme sur un ensemble fini

Soient $I$ un ensemble fini et $(a_i)_{i \in I}$ une famille de réels. Une énumération de $I$ est une liste $i_1, \dots, i_p$ dans laquelle chaque élément de $I$ figure exactement une fois, avec $p = 0$ lorsque $I = \emptyset$. La somme de la famille est la somme des termes listés dans une énumération : $$ \sum_{i \in I} a_i = \sum_{j=1}^{p} a_{i_j} = a_{i_1} + a_{i_2} + \dots + a_{i_p}. $$ Elle vaut $0$ lorsque $I = \emptyset$. Pour $I = \llbracket m, n \rrbracket$ et l'énumération croissante, c'est la somme $\sum_{k=m}^{n} a_k$ de la Définition « Notation sigma » : $\sum_{k=m}^{n} a_k = \sum_{k \in \llbracket m, n \rrbracket} a_k$.
Admise ici (hors programme), puis démontrée en fin de section dans le Text « Preuve différée » : la valeur ne dépend pas de l'énumération choisie. C'est la commutativité et l'associativité généralisées de l'addition : une somme finie de réels ne dépend ni de l'ordre ni du parenthésage de ses termes. C'est ce qui donne un sens à la notation $\sum_{i \in I}$, une famille n'ayant pas d'ordre privilégié.

Exemple — Lire une somme

Trois sommes, lues en extension :

$\sum_{k=1}^{5} k = 1 + 2 + 3 + 4 + 5 = 15$ ;
$\sum_{i \in \{1, 4, 9\}} \sqrt{i} = \sqrt{1} + \sqrt{4} + \sqrt{9} = 1 + 2 + 3 = 6$ ;
$\sum_{k=3}^{2} \frac{1}{k} = 0$, car la borne supérieure $2$ est plus petite que la borne inférieure $3$ : la somme est vide, comme $\sum_{i \in \emptyset} a_i$.

Piège — l'indice d'une somme est muet

L'indice d'une somme est une variable muette. Il n'existe qu'à l'intérieur de la somme, entre le symbole $\sum$ et la fin du terme général : $\sum_{k=1}^{n} a_k = \sum_{j=1}^{n} a_j = \sum_{i=1}^{n} a_i$, et la valeur dépend des bornes et du terme général, non de la lettre. Deux conséquences en découlent. L'indice n'est jamais une lettre qui a déjà un sens dans la somme : $\sum_{n=1}^{n} a_n$ n'a pas de sens, puisque $n$ serait à la fois l'indice et la borne. Et une lettre écrite hors de la somme n'est pas l'indice : $\sum_{k=1}^{n} k$ ne dépend pas de $k$, donc elle n'est pas égale à $nk$. En revanche deux sommes voisines peuvent employer la même lettre, comme dans $\sum_{k=1}^{n} k + \sum_{k=1}^{n} k^2$ : chaque $k$ vit dans sa propre somme.

Signaler une erreur

Proposition — Nombre de termes

Soient $m, n \in \mathbb{Z}$ avec $n \ge m - 1$, et $c \in \mathbb{R}$. Alors $$ \textcolor{colorprop}{\sum_{k=m}^{n} c = (n - m + 1)\,c.} $$ En particulier $\sum_{k=m}^{n} 1 = n - m + 1$ : une somme de $m$ à $n$ a $n - m + 1$ termes, et non $n - m$.

Preuve

Première démonstration, par récurrence. Pour $n \ge m - 1$, notons $P_n$ la propriété « $\sum_{k=m}^{n} c = (n - m + 1)\,c$ ».
Initialisation. Pour $n = m - 1$, la somme est vide, donc elle vaut $0$, et $(n - m + 1)\,c = 0 \cdot c = 0$ : $P_{m-1}$ est vraie.
Hérédité. Soit $n \ge m - 1$ et supposons $P_n$. Alors $$ \begin{aligned} \sum_{k=m}^{n+1} c &= \sum_{k=m}^{n} c + c && \text{(définition de $\sum$)} \\ &= (n - m + 1)\,c + c && \text{(hypothèse de récurrence)} \\ &= (n - m + 2)\,c, \end{aligned} $$ la dernière étape en factorisant $c$ dans $(n - m + 1)\,c + 1 \cdot c$. Comme $n - m + 2 = (n + 1) - m + 1$, c'est $P_{n+1}$. Puisque $P_{m-1}$ est vraie et que $P_n \Rightarrow P_{n+1}$ pour tout $n \ge m - 1$, par récurrence à partir du rang $m - 1$, $P_n$ est vraie pour tout $n \ge m - 1$.
Seconde démonstration, par la forme développée. Pour $n = m - 1$, la somme est vide et vaut $0 = (n - m + 1)\,c$. Pour $n \ge m$, la forme développée $c + c + \dots + c$ a un terme pour chacun des entiers $m, m + 1, \dots, n$, soit $n - m + 1$ termes, tous égaux à $c$ : la somme vaut $(n - m + 1)\,c$.

Méthode — Écrire et lire une somme

Pour lire une somme, ou pour en écrire une :

Pour lire une somme, repérer l'indice, les bornes et le terme général. Écrire les premiers termes, puis des points, puis le dernier terme. Compter les termes : il y en a $n - m + 1$, et la somme est vide, égale à $0$, lorsque la borne supérieure est plus petite que la borne inférieure. Une lettre qui n'est ni l'indice ni une borne est un paramètre : c'est une constante pour la somme.
Pour écrire une somme à partir d'une liste de termes, trouver le terme général en fonction de la position du terme dans la liste ; pour des termes dont les signes alternent, un facteur $(-1)^k$ ou $(-1)^{k+1}$ donne le signe. Choisir l'indice et ses bornes de sorte que le premier et le dernier terme de la liste soient les valeurs du terme général aux deux bornes.

Vérifier sur le premier et le dernier terme : la vérification repère un décalage d'indice et un mauvais signe, et le nombre de termes $n - m + 1$ repère une erreur d'une unité sur une borne.

Exemple — Écrire une somme alternée

Écrire $\frac{1}{2} - \frac{1}{4} + \frac{1}{8} - \dots + \frac{(-1)^{n+1}}{2^n}$ avec le symbole $\sum$, pour $n \ge 1$, et donner son nombre de termes. Puis le calculer pour $n = 3$.

Correction

Le terme général. Les dénominateurs sont les puissances $2^1, 2^2, 2^3, \dots, 2^n$, et les signes sont $+, -, +, \dots$ : le signe est $+$ pour la position $k = 1$, donc c'est $(-1)^{k+1}$. Le terme général est $a_k = \frac{(-1)^{k+1}}{2^k}$.
Les bornes. Le premier terme est $a_1 = \frac{(-1)^2}{2^1} = \frac{1}{2}$ et le dernier est $a_n = \frac{(-1)^{n+1}}{2^n}$, comme dans la liste. Donc $$ \frac{1}{2} - \frac{1}{4} + \frac{1}{8} - \dots + \frac{(-1)^{n+1}}{2^n} = \sum_{k=1}^{n} \frac{(-1)^{k+1}}{2^k}, $$ somme de $n - 1 + 1 = n$ termes.
La valeur pour $n = 3$. $$ \begin{aligned} \sum_{k=1}^{3} \frac{(-1)^{k+1}}{2^k} &= \frac{(-1)^2}{2^1} + \frac{(-1)^3}{2^2} + \frac{(-1)^4}{2^3} && \text{(forme développée)} \\ &= \frac{1}{2} - \frac{1}{4} + \frac{1}{8} && \text{(signes)} \\ &= \frac{4 - 2 + 1}{8} && \text{(dénominateur commun $8$)} \\ &= \frac{3}{8}. \end{aligned} $$

Compétences à pratiquer

Lire les bornes et le nombre de termes d'une somme ★
Évaluer une somme écrite avec $\sum$ ★
Compter les termes et écrire une somme avec $\sum$ ★

I.2 Règles de calcul

Calculer avec le symbole

Trois règles manient le symbole $\sum$ : la linéarité, qui sépare une somme de sommes et sort une constante ; la relation de Chasles, qui coupe une somme en deux ; et la sommation par paquets, qui rassemble en groupes les indices d'un ensemble fini. Chacune se démontre à partir de la définition, et chacune se vérifie en écrivant les sommes sous forme développée : les règles se comprennent, elles ne s'apprennent pas par cœur.

Signaler une erreur

Proposition — Linéarité de $\sum$

Soient $\lambda, \mu \in \mathbb{R}$.

Pour $m, n \in \mathbb{Z}$ et des réels $a_k$, $b_k$ ($m \le k \le n$), la seconde ligne étant écrite pour $n \ge m$ : $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=m}^{n} (\lambda a_k + \mu b_k) &= \lambda \sum_{k=m}^{n} a_k + \mu \sum_{k=m}^{n} b_k \\ (\lambda a_m + \mu b_m) + \dots + (\lambda a_n + \mu b_n) &= \lambda (a_m + \dots + a_n) + \mu (b_m + \dots + b_n) \end{aligned}} $$
Pour un ensemble fini $I$ et des familles $(a_i)_{i \in I}$ et $(b_i)_{i \in I}$ de réels, $\sum_{i \in I} (\lambda a_i + \mu b_i) = \lambda \sum_{i \in I} a_i + \mu \sum_{i \in I} b_i$.

En particulier $\sum (a_k + b_k) = \sum a_k + \sum b_k$, $\sum (a_k - b_k) = \sum a_k - \sum b_k$ et $\sum \lambda a_k = \lambda \sum a_k$.

Preuve

Première démonstration, par récurrence. Si $n < m - 1$, les trois sommes sont vides et les deux membres valent $0 = \lambda \cdot 0 + \mu \cdot 0$. Pour $n \ge m - 1$, notons $P_n$ la propriété « $\sum_{k=m}^{n} (\lambda a_k + \mu b_k) = \lambda \sum_{k=m}^{n} a_k + \mu \sum_{k=m}^{n} b_k$ ».
Initialisation. Pour $n = m - 1$ les trois sommes sont vides, donc les deux membres valent $0$ : $P_{m-1}$ est vraie.
Hérédité. Soit $n \ge m - 1$ et supposons $P_n$. Alors $$ \begin{aligned} \sum_{k=m}^{n+1} (\lambda a_k + \mu b_k) &= \sum_{k=m}^{n} (\lambda a_k + \mu b_k) + (\lambda a_{n+1} + \mu b_{n+1}) && \text{(définition de $\sum$)} \\ &= \lambda \sum_{k=m}^{n} a_k + \mu \sum_{k=m}^{n} b_k + \lambda a_{n+1} + \mu b_{n+1} && \text{(hypothèse de récurrence)} \\ &= \lambda \Bigl( \sum_{k=m}^{n} a_k + a_{n+1} \Bigr) + \mu \Bigl( \sum_{k=m}^{n} b_k + b_{n+1} \Bigr) && \text{(distributivité)} \\ &= \lambda \sum_{k=m}^{n+1} a_k + \mu \sum_{k=m}^{n+1} b_k, \end{aligned} $$ la dernière étape étant la définition de $\sum$, lue de droite à gauche. C'est $P_{n+1}$, et la récurrence donne $P_n$ pour tout $n \ge m - 1$. Pour un ensemble fini $I$, soit $i_1, \dots, i_p$ une énumération de $I$ : $$ \begin{aligned} \sum_{i \in I} (\lambda a_i + \mu b_i) &= \sum_{j=1}^{p} (\lambda a_{i_j} + \mu b_{i_j}) && \text{(définition de la somme sur $I$)} \\ &= \lambda \sum_{j=1}^{p} a_{i_j} + \mu \sum_{j=1}^{p} b_{i_j} && \text{(le cas d'un intervalle d'entiers)} \\ &= \lambda \sum_{i \in I} a_i + \mu \sum_{i \in I} b_i, \end{aligned} $$ la dernière étape étant la définition de la somme sur $I$, pour les deux familles.
Seconde démonstration, par la forme développée. Pour $n \ge m$, la commutativité et l'associativité de l'addition regroupent les termes de $(\lambda a_m + \mu b_m) + \dots + (\lambda a_n + \mu b_n)$ en $(\lambda a_m + \dots + \lambda a_n) + (\mu b_m + \dots + \mu b_n)$, et la distributivité de la multiplication sur l'addition sort $\lambda$ et $\mu$ des deux parenthèses.

Proposition — Découpage et relation de Chasles

Soient $m, p, n \in \mathbb{Z}$ avec $m - 1 \le p \le n$, et $a_k$ un réel pour $m \le k \le n$. Alors, la seconde ligne étant écrite pour $m \le p < n$ : $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=m}^{n} a_k &= \sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k \\ a_m + \dots + a_p + a_{p+1} + \dots + a_n &= (a_m + \dots + a_p) + (a_{p+1} + \dots + a_n) \end{aligned}} $$ Pour $p = m - 1$ la première somme du second membre est vide, et pour $p = n$ c'est la seconde : la relation s'écrit alors $\sum_{k=m}^{n} a_k = 0 + \sum_{k=m}^{n} a_k$ et $\sum_{k=m}^{n} a_k = \sum_{k=m}^{n} a_k + 0$.

Preuve

Première démonstration, par récurrence sur $n$, avec $m$ et $p$ fixés. Pour $n \ge p$, notons $P_n$ la propriété « $\sum_{k=m}^{n} a_k = \sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k$ ».
Initialisation. Pour $n = p$, la somme de $p + 1$ à $p$ est vide, donc elle vaut $0$, et le second membre est $\sum_{k=m}^{p} a_k$, qui est le premier membre : $P_p$ est vraie.
Hérédité. Soit $n \ge p$ et supposons $P_n$. Alors $$ \begin{aligned} \sum_{k=m}^{n+1} a_k &= \sum_{k=m}^{n} a_k + a_{n+1} && \text{(définition de $\sum$)} \\ &= \sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k + a_{n+1} && \text{(hypothèse de récurrence)} \\ &= \sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n+1} a_k, \end{aligned} $$ la dernière étape étant la définition de $\sum$ de $p + 1$ à $n + 1$, valable car $n \ge p$. C'est $P_{n+1}$ : le pas de récurrence est la définition de $\sum$. Puisque $P_p$ est vraie et que $P_n \Rightarrow P_{n+1}$ pour tout $n \ge p$, par récurrence à partir du rang $p$, $P_n$ est vraie pour tout $n \ge p$.
Seconde démonstration, par la forme développée. Pour $m \le p < n$, la forme développée $a_m + \dots + a_p + a_{p+1} + \dots + a_n$ est une somme de $n - m + 1$ termes ; l'associativité de l'addition permet d'insérer une parenthèse autour des $p - m + 1$ premiers termes et une autre autour des derniers, ce qui est la seconde ligne. Pour $p = m - 1$ et pour $p = n$, l'une des deux sommes est vide, égale à $0$.

Proposition — Sommation par paquets

Soient $I$ un ensemble fini et $(a_i)_{i \in I}$ une famille de réels.

Si $I = I_1 \sqcup I_2$ est une réunion disjointe, alors $\sum_{i \in I} a_i = \sum_{i \in I_1} a_i + \sum_{i \in I_2} a_i$.
Si $I = I_1 \sqcup \dots \sqcup I_r$ est un recouvrement disjoint de $I$ en $r \ge 1$ morceaux, dont certains peuvent être vides, alors $$ \textcolor{colorprop}{\sum_{i \in I} a_i = \sum_{j=1}^{r} \ \sum_{i \in I_j} a_i.} $$

La somme sur $I$ est la somme, sur les paquets, des sommes sur chaque paquet.

Preuve

Deux paquets. Soit $i_1, \dots, i_p$ une énumération de $I_1$ et $i'_1, \dots, i'_q$ une énumération de $I_2$, avec $p, q \ge 0$. La liste $i_1, \dots, i_p, i'_1, \dots, i'_q$ est une énumération de $I$ : tout élément de $I = I_1 \cup I_2$ y figure, et exactement une fois, car les $i_j$ sont deux à deux distincts, les $i'_j$ sont deux à deux distincts, et aucun $i_j$ n'est un $i'_{j'}$ puisque $I_1 \cap I_2 = \emptyset$. Posons $b_j = a_{i_j}$ pour $1 \le j \le p$ et $b_{p+j} = a_{i'_j}$ pour $1 \le j \le q$. Comme la Définition « Somme sur un ensemble fini » autorise n'importe quelle énumération, $$ \begin{aligned} \sum_{i \in I} a_i &= \sum_{j=1}^{p+q} b_j && \text{(énumération de $I$ formée de celles de $I_1$ et de $I_2$)} \\ &= \sum_{j=1}^{p} b_j + \sum_{j=p+1}^{p+q} b_j && \text{(relation de Chasles, $0 \le p \le p + q$)} \\ &= \sum_{i \in I_1} a_i + \sum_{i \in I_2} a_i, \end{aligned} $$ la dernière étape parce que $b_j = a_{i_j}$ pour $j \le p$, et parce que la forme développée $b_{p+1} + \dots + b_{p+q}$ est $a_{i'_1} + \dots + a_{i'_q}$.
$r$ paquets, par récurrence sur $r$. Notons $P_r$ la propriété « la formule vaut pour tout ensemble fini $I$, toute famille $(a_i)_{i \in I}$ et tout recouvrement disjoint de $I$ par $r$ morceaux ».
Initialisation. Pour $r = 1$, $I = I_1$ et $\sum_{j=1}^{1} \sum_{i \in I_j} a_i = 0 + \sum_{i \in I_1} a_i = \sum_{i \in I} a_i$ : $P_1$ est vraie.
Hérédité. Soit $r \ge 1$ et supposons $P_r$. Soit $I = I_1 \sqcup \dots \sqcup I_{r+1}$, et $I' = I_1 \cup \dots \cup I_r$, une partie de $I$, donc un ensemble fini. Les morceaux $I_1, \dots, I_r$ forment un recouvrement disjoint de $I'$, et $I = I' \sqcup I_{r+1}$, car $I_{r+1}$ est disjoint de chaque $I_j$, donc de leur réunion. Alors $$ \begin{aligned} \sum_{i \in I} a_i &= \sum_{i \in I'} a_i + \sum_{i \in I_{r+1}} a_i && \text{(deux paquets)} \\ &= \sum_{j=1}^{r} \sum_{i \in I_j} a_i + \sum_{i \in I_{r+1}} a_i && \text{(hypothèse de récurrence sur $I'$)} \\ &= \sum_{j=1}^{r+1} \sum_{i \in I_j} a_i, \end{aligned} $$ la dernière étape étant la définition de $\sum$, qui ajoute le terme d'indice $r + 1$. C'est $P_{r+1}$, et la récurrence donne $P_r$ pour tout $r \ge 1$.

Piège — ce qu'une somme ne fait pas

Une somme est linéaire, et rien de plus. La somme de produits n'est pas le produit des sommes : $\sum_{k=1}^{2} k \cdot k = 1 + 4 = 5$, alors que $\bigl( \sum_{k=1}^{2} k \bigr) \bigl( \sum_{k=1}^{2} k \bigr) = 3 \cdot 3 = 9$. De même $\bigl( \sum a_k \bigr)^p$ n'est pas $\sum a_k^p$ : pour $p = 2$ et les termes $1$ et $2$, $(1 + 2)^2 = 9$ alors que $1^2 + 2^2 = 5$, les termes croisés manquant. Un facteur qui dépend de l'indice ne se sort pas de la somme, seule une constante le peut. L'inégalité triangulaire donne $\bigl\lvert \sum a_k \bigr\rvert \le \sum \lvert a_k \rvert$, et ce n'est une égalité que dans des cas particuliers : $\lvert 1 + (-1) \rvert = 0 < 2 = \lvert 1 \rvert + \lvert -1 \rvert$.

Signaler une erreur

Méthode — Appliquer les règles de $\sum$

Pour transformer une somme donnée avec les règles de $\sum$ :

Séparer et sortir les constantes. La linéarité sépare $\sum (\lambda a_k + \mu b_k)$ en $\lambda \sum a_k + \mu \sum b_k$. Un facteur qui ne contient pas l'indice sort de la somme, et une somme de constantes est le nombre de termes fois la constante : $\sum_{k=m}^{n} c = (n - m + 1)\,c$.
Isoler un terme ou couper. La relation de Chasles avec $p = m$ isole le premier terme, $\sum_{k=m}^{n} a_k = a_m + \sum_{k=m+1}^{n} a_k$, et la définition de $\sum$ isole le dernier, $\sum_{k=m}^{n} a_k = \sum_{k=m}^{n-1} a_k + a_n$ ; tout autre $p$ coupe la somme en deux.
Vérifier en forme développée. Écrire les premiers termes, des points et le dernier terme de chaque côté, et voir si les deux membres listent les mêmes termes : cela repère un terme perdu, une mauvaise borne et un facteur sorti qui dépendait de l'indice.

Seule une constante sort de la somme.

Exemple — Isoler un terme et sortir une constante

Pour $n \ge 1$ et des réels $a_0, \dots, a_n$, écrire $\sum_{k=0}^{n} (a_k + 2)$ comme $a_0$ plus un nombre plus une somme qui commence à $k = 1$.

Correction

$$ \begin{aligned} \sum_{k=0}^{n} (a_k + 2) &= \sum_{k=0}^{n} a_k + \sum_{k=0}^{n} 2 && \text{(linéarité)} \\ &= \sum_{k=0}^{n} a_k + 2 (n + 1) && \text{(nombre de termes : $n - 0 + 1$)} \\ &= a_0 + \sum_{k=1}^{n} a_k + 2 (n + 1) && \text{(relation de Chasles avec $p = 0$)} \\ &= a_0 + 2n + 2 + \sum_{k=1}^{n} a_k, \end{aligned} $$ la dernière étape réordonnant les termes. Vérification pour $n = 1$ : le premier membre est $(a_0 + 2) + (a_1 + 2) = a_0 + a_1 + 4$, et le second membre est $a_0 + 2 + 2 + a_1$.

Compétences à pratiquer

Distinguer les règles de $\sum$ des règles fausses ★
Évaluer une somme par linéarité ★
Isoler des termes avec la relation de Chasles ★
Combiner linéarité et relation de Chasles ★★
Sommer par paquets ★★★

I.3 Changement d'indice

Renuméroter les termes

L'indice d'une somme peut être renuméroté : les mêmes termes sont listés sous d'autres indices. Deux changements d'indice se rencontrent partout, le décalage, qui ajoute une constante à l'indice, et la réflexion, qui compte les termes à l'envers. Quel que soit le changement, une chose doit être garantie : aucun terme n'est supprimé et aucun terme n'est ajouté, de sorte que chaque terme de l'ancienne somme figure exactement une fois dans la nouvelle.

Signaler une erreur

Proposition — Changement d'indice par une bijection

Soient $I$ et $J$ des ensembles finis, $\varphi \colon J \to I$ une bijection, et $(a_i)_{i \in I}$ une famille de réels. Alors $$ \textcolor{colorprop}{\sum_{i \in I} a_i = \sum_{j \in J} a_{\varphi(j)}.} $$

Preuve

Soit $j_1, \dots, j_p$ une énumération de $J$. La liste $\varphi(j_1), \dots, \varphi(j_p)$ est une énumération de $I$ : tout élément de $I$ est de la forme $\varphi(j)$ car $\varphi$ est surjective, donc figure dans la liste, et il y figure une seule fois car $\varphi$ est injective et les $j_s$ sont deux à deux distincts. Donc $$ \begin{aligned} \sum_{i \in I} a_i &= a_{\varphi(j_1)} + \dots + a_{\varphi(j_p)} && \text{(énumération $\varphi(j_1), \dots, \varphi(j_p)$ de $I$)} \\ &= \sum_{j \in J} a_{\varphi(j)}, \end{aligned} $$ la dernière étape étant la définition de la somme de la famille $(a_{\varphi(j)})_{j \in J}$ avec l'énumération $j_1, \dots, j_p$ de $J$.

Proposition — Décalage et réflexion

Soient $m, n, p \in \mathbb{Z}$ et $a_k$ un réel pour $m \le k \le n$.

Décalage, avec $j = k + p$ : $$ \textcolor{colorprop}{\sum_{k=m}^{n} a_k = \sum_{j=m+p}^{n+p} a_{j-p}.} $$
Réflexion, avec $j = m + n - k$, qui garde les bornes et lit les termes à l'envers : $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=m}^{n} a_k &= \sum_{j=m}^{n} a_{m+n-j} \\ a_m + a_{m+1} + \dots + a_n &= a_n + a_{n-1} + \dots + a_m \end{aligned}} $$

Preuve

Si $n < m$, toutes les sommes sont vides et valent $0$. Supposons $n \ge m$.
Première démonstration, par la bijection. L'application $\varphi \colon \llbracket m + p, n + p \rrbracket \to \llbracket m, n \rrbracket$, $j \mapsto j - p$, est une bijection, de réciproque $k \mapsto k + p$, car $m + p \le j \le n + p$ si et seulement si $m \le j - p \le n$. La Proposition « Changement d'indice par une bijection » donne $\sum_{k \in \llbracket m, n \rrbracket} a_k = \sum_{j \in \llbracket m+p, n+p \rrbracket} a_{j-p}$, qui est le décalage. L'application $\psi \colon \llbracket m, n \rrbracket \to \llbracket m, n \rrbracket$, $j \mapsto m + n - j$, est une bijection, égale à sa propre réciproque, car $m + n - (m + n - j) = j$ et $m \le j \le n$ si et seulement si $m \le m + n - j \le n$. La même Proposition donne $\sum_{k \in \llbracket m, n \rrbracket} a_k = \sum_{j \in \llbracket m, n \rrbracket} a_{m+n-j}$, qui est la réflexion.
Seconde démonstration, par la forme développée. Pour $j$ allant de $m + p$ à $n + p$, les termes $a_{j-p}$ sont $a_m, a_{m+1}, \dots, a_n$, dans le même ordre que dans la somme de départ. Pour $j$ allant de $m$ à $n$, les termes $a_{m+n-j}$ sont $a_n, a_{n-1}, \dots, a_m$ : la liste des termes de départ lue à l'envers, qui a la même somme car l'ordre des termes n'importe pas.

Exemple — Décaler l'indice pour partir de zéro

Réécrire $\sum_{k=3}^{n+3} k^2$, pour $n \ge 0$, avec un indice qui commence à $0$.

Correction

Posons $j = k - 3$, c'est-à-dire $k = j + 3$ : la borne $k = 3$ devient $j = 0$, et la borne $k = n + 3$ devient $j = n$. C'est le décalage de la Proposition « Décalage et réflexion » avec $p = -3$, pour le terme général $a_k = k^2$, d'où $a_{j-p} = a_{j+3} = (j + 3)^2$. $$ \begin{aligned} \sum_{k=3}^{n+3} k^2 &= \sum_{j=0}^{n} (j + 3)^2 && \text{(décalage $j = k - 3$)} \\ &= \sum_{j=0}^{n} (j^2 + 6j + 9), \end{aligned} $$ la dernière étape développant le carré. Vérification sur le premier et le dernier terme : $k = 3$ donne $3^2 = 9$ et $j = 0$ donne $(0 + 3)^2 = 9$ ; $k = n + 3$ donne $(n + 3)^2$ et $j = n$ donne $(n + 3)^2$.

Exemple — Lire une somme à l'envers

Montrer que $\sum_{k=0}^{n} a_k = \sum_{k=0}^{n} a_{n-k}$ pour tout entier $n \ge 0$ et tous réels $a_0, \dots, a_n$.

Correction

$$ \begin{aligned} \sum_{k=0}^{n} a_k &= \sum_{j=0}^{n} a_{n-j} && \text{(réflexion avec $m = 0$ : $m + n - j = n - j$)} \\ &= \sum_{k=0}^{n} a_{n-k}, \end{aligned} $$ la dernière étape renommant l'indice muet $j$ en $k$. Donc les deux sommes sont égales pour tout $n \ge 0$. Vérification pour $n = 2$ : $a_0 + a_1 + a_2 = a_2 + a_1 + a_0$.

Méthode — Changer l'indice d'une somme

Pour changer l'indice de $\sum_{k=m}^{n} a_k$ en un nouvel indice $j$, par un décalage $j = k + p$ ou une réflexion $j = c - k$ ($c$ une constante) :

Poser $j$ en fonction de $k$, et exprimer $k$ en fonction de $j$ : $k = j - p$, respectivement $k = c - j$.
Transformer les bornes. Les nouvelles bornes sont les valeurs de $j$ aux anciennes bornes : $m + p$ et $n + p$ pour le décalage. Pour la réflexion les bornes sont échangées : $k = n$ donne la borne inférieure $j = c - n$, et $k = m$ donne la borne supérieure $j = c - m$.
Réécrire le terme général en remplaçant $k$ par son expression en $j$ : $\sum_{k=m}^{n} a_k = \sum_{j=m+p}^{n+p} a_{j-p}$, respectivement $\sum_{k=m}^{n} a_k = \sum_{j=c-n}^{c-m} a_{c-j}$.
Vérifier sur le premier et le dernier terme que la nouvelle somme liste les mêmes termes : aucun terme n'a été supprimé ni ajouté.

Les deux bornes changent, et le terme général aussi.

Méthode — Couper une somme selon la parité de l'indice

Pour couper $\sum_{k=1}^{n} a_k$ en les termes d'indice pair et les termes d'indice impair :

Écrire les indices sous la forme $k = 2j$ pour les pairs et $k = 2j + 1$ pour les impairs, et trouver les bornes de $j$ à partir de $1 \le 2j \le n$ et $1 \le 2j + 1 \le n$ : $1 \le j \le \lfloor \frac{n}{2} \rfloor$ pour les indices pairs, $0 \le j \le \lfloor \frac{n-1}{2} \rfloor$ pour les impairs. Le résultat est $$ \sum_{k=1}^{n} a_k = \sum_{j=0}^{\lfloor (n-1)/2 \rfloor} a_{2j+1} + \sum_{j=1}^{\lfloor n/2 \rfloor} a_{2j}. $$
Justifier la coupure : les entiers impairs et les entiers pairs de $\llbracket 1, n \rrbracket$ forment un recouvrement disjoint, l'une des deux parties étant vide lorsque $n = 1$, donc la somme est la somme des deux paquets, et $j \mapsto 2j + 1$ et $j \mapsto 2j$ sont des bijections des ensembles de valeurs de $j$ sur les deux paquets.
Associer les termes lorsque $n = 2N$ est pair : $\sum_{k=1}^{2N} a_k = \sum_{j=1}^{N} (a_{2j-1} + a_{2j})$ ; les paires $\{2j-1, 2j\}$, $1 \le j \le N$, forment un recouvrement disjoint de $\llbracket 1, 2N \rrbracket$, et la Proposition « Sommation par paquets » s'applique.

Les bornes de $j$ ne sont pas celles de $k$ : on les trouve en résolvant $1 \le 2j \le n$ et $1 \le 2j + 1 \le n$ pour l'entier $j$, ce qui fait intervenir la partie entière.

Exemple — Couper une somme selon la parité

Couper $\sum_{k=1}^{n} a_k$ en les termes d'indice impair et les termes d'indice pair, pour $n = 5$ et pour $n = 6$, et écrire chaque partie en extension.

Correction

Le cas $n = 5$. $$ \begin{aligned} \sum_{k=1}^{5} a_k &= \sum_{j=0}^{\lfloor 4/2 \rfloor} a_{2j+1} + \sum_{j=1}^{\lfloor 5/2 \rfloor} a_{2j} && \text{(coupure selon la parité)} \\ &= \sum_{j=0}^{2} a_{2j+1} + \sum_{j=1}^{2} a_{2j} && \text{(parties entières : $\lfloor 4/2 \rfloor = 2$, $\lfloor 5/2 \rfloor = 2$)} \\ &= (a_1 + a_3 + a_5) + (a_2 + a_4). \end{aligned} $$ Le cas $n = 6$. $$ \begin{aligned} \sum_{k=1}^{6} a_k &= \sum_{j=0}^{\lfloor 5/2 \rfloor} a_{2j+1} + \sum_{j=1}^{\lfloor 6/2 \rfloor} a_{2j} && \text{(coupure selon la parité)} \\ &= \sum_{j=0}^{2} a_{2j+1} + \sum_{j=1}^{3} a_{2j} && \text{(parties entières : $\lfloor 5/2 \rfloor = 2$, $\lfloor 6/2 \rfloor = 3$)} \\ &= (a_1 + a_3 + a_5) + (a_2 + a_4 + a_6). \end{aligned} $$ Les deux parties ont autant de termes qu'il y a d'entiers impairs, respectivement pairs, entre $1$ et $n$ : trois et deux pour $n = 5$, trois et trois pour $n = 6$.

Compétences à pratiquer

Réécrire une somme après un décalage ou une réflexion ★
Utiliser un changement d'indice pour calculer une somme ★★
Couper une somme selon la parité de l'indice ★★
Trouver le changement d'indice qui simplifie une somme ★★★

I.4 Le symbole produit

Le jumeau multiplicatif de la somme

Le symbole $\prod$ est le jumeau multiplicatif de $\sum$ : le même indice muet, les mêmes bornes, les mêmes règles de calcul, avec la multiplication à la place de l'addition. La seule différence de structure est le produit vide, qui vaut $1$, l'élément neutre de la multiplication, et non $0$. Les définitions sont données par récurrence sur la borne supérieure, et sur un ensemble fini.

Signaler une erreur

Définition — Notation produit

Soient $m, n \in \mathbb{Z}$, et $a_k$ un réel pour chaque entier $k$ tel que $m \le k \le n$. Le produit $\prod_{k=m}^{n} a_k$ est défini par récurrence sur $n$ :

produit vide : $\prod_{k=m}^{n} a_k = 1$ lorsque $n < m$ ;
ajout d'un facteur : $\prod_{k=m}^{n+1} a_k = \Bigl( \prod_{k=m}^{n} a_k \Bigr) a_{n+1}$ pour tout $n \ge m - 1$.

Pour $n \ge m$, c'est la forme développée $\prod_{k=m}^{n} a_k = a_m \cdot a_{m+1} \cdots a_n$, produit de $n - m + 1$ facteurs. La lettre $k$ est l'indice, $m$ et $n$ sont les bornes, et $a_k$ est le facteur général.

Définition — Produit sur un ensemble fini

Soient $I$ un ensemble fini et $(a_i)_{i \in I}$ une famille de réels. Avec une énumération $i_1, \dots, i_p$ de $I$, le produit de la famille est $$ \prod_{i \in I} a_i = \prod_{j=1}^{p} a_{i_j} = a_{i_1} \cdot a_{i_2} \cdots a_{i_p}, $$ et il vaut $1$ lorsque $I = \emptyset$. Comme pour la somme, la valeur ne dépend pas de l'énumération choisie : c'est la commutativité et l'associativité généralisées, ici de la multiplication, admises puis démontrées avec celles de l'addition (Text « Preuve différée »). Pour $I = \llbracket m, n \rrbracket$ et l'énumération croissante, $\prod_{k \in \llbracket m, n \rrbracket} a_k = \prod_{k=m}^{n} a_k$.

Exemple — Produits de constantes

Trois produits, lus en extension :

$\prod_{k=1}^{4} k = 1 \cdot 2 \cdot 3 \cdot 4 = 24$ ;
$\prod_{k=2}^{5} 3 = 3 \cdot 3 \cdot 3 \cdot 3 = 3^4 = 81$, et en général $\prod_{k=m}^{n} a = a^{n-m+1}$ : un produit de $n - m + 1$ facteurs égaux ;
$\prod_{k=3}^{2} k = 1$, car la borne supérieure est plus petite que la borne inférieure : le produit est vide.

Proposition — Règles de calcul sur les produits

Soient $m, n \in \mathbb{Z}$ avec $n \ge m - 1$, $\lambda \in \mathbb{R}$, $p \in \mathbb{N}$, et des réels $a_k$, $b_k$ pour $m \le k \le n$.

Produit, constante et puissance : $$ \textcolor{colorprop}{\prod_{k=m}^{n} (a_k b_k) = \Bigl( \prod_{k=m}^{n} a_k \Bigr) \Bigl( \prod_{k=m}^{n} b_k \Bigr), \qquad \prod_{k=m}^{n} (\lambda a_k) = \lambda^{n-m+1} \prod_{k=m}^{n} a_k, \qquad \prod_{k=m}^{n} a_k^{\,p} = \Bigl( \prod_{k=m}^{n} a_k \Bigr)^{p}.} $$
Quotient : si $b_k \ne 0$ pour tout $k$, alors $\prod_{k=m}^{n} \frac{a_k}{b_k} = \frac{\prod_{k=m}^{n} a_k}{\prod_{k=m}^{n} b_k}$.
Relation de Chasles : pour $m - 1 \le q \le n$, $\prod_{k=m}^{n} a_k = \Bigl( \prod_{k=m}^{q} a_k \Bigr) \Bigl( \prod_{k=q+1}^{n} a_k \Bigr)$.
Décalage et réflexion : pour $r \in \mathbb{Z}$, $\prod_{k=m}^{n} a_k = \prod_{j=m+r}^{n+r} a_{j-r} = \prod_{j=m}^{n} a_{m+n-j}$.

Preuve

Produit de deux familles, par récurrence sur $n$. Pour $n \ge m - 1$, notons $P_n$ la propriété « $\prod_{k=m}^{n} (a_k b_k) = \bigl( \prod_{k=m}^{n} a_k \bigr) \bigl( \prod_{k=m}^{n} b_k \bigr)$ ».
Initialisation. Pour $n = m - 1$ les produits sont vides, égaux à $1$, et l'égalité s'écrit $1 = 1 \cdot 1$ : $P_{m-1}$ est vraie.
Hérédité. Soit $n \ge m - 1$ et supposons $P_n$. Alors $$ \begin{aligned} \prod_{k=m}^{n+1} (a_k b_k) &= \Bigl( \prod_{k=m}^{n} (a_k b_k) \Bigr) a_{n+1} b_{n+1} && \text{(définition de $\prod$)} \\ &= \Bigl( \prod_{k=m}^{n} a_k \Bigr) \Bigl( \prod_{k=m}^{n} b_k \Bigr) a_{n+1} b_{n+1} && \text{(hypothèse de récurrence)} \\ &= \Bigl( \prod_{k=m}^{n} a_k \Bigr) a_{n+1} \Bigl( \prod_{k=m}^{n} b_k \Bigr) b_{n+1} && \text{(commutativité de la multiplication)} \\ &= \Bigl( \prod_{k=m}^{n+1} a_k \Bigr) \Bigl( \prod_{k=m}^{n+1} b_k \Bigr), \end{aligned} $$ la dernière étape étant la définition de $\prod$, deux fois. C'est $P_{n+1}$, et la récurrence donne $P_n$ pour tout $n \ge m - 1$.
Constante, à partir de la première règle. Pour $\lambda \in \mathbb{R}$, $\prod_{k=m}^{n} \lambda = \lambda^{n-m+1}$ par récurrence sur $n$ : pour $n = m - 1$ les deux membres valent $1$, et $\prod_{k=m}^{n+1} \lambda = \lambda^{n-m+1} \lambda = \lambda^{(n+1)-m+1}$ par la définition de $\prod$. Donc $$ \begin{aligned} \prod_{k=m}^{n} (\lambda a_k) &= \Bigl( \prod_{k=m}^{n} \lambda \Bigr) \Bigl( \prod_{k=m}^{n} a_k \Bigr) && \text{(première règle, pour les facteurs $\lambda$ et $a_k$)} \\ &= \lambda^{n-m+1} \prod_{k=m}^{n} a_k. \end{aligned} $$ Puissance, à partir de la première règle, par récurrence sur $p$. Pour $p = 0$, $\prod_{k=m}^{n} a_k^{\,0} = \prod_{k=m}^{n} 1 = 1^{n-m+1} = 1 = \bigl( \prod_{k=m}^{n} a_k \bigr)^{0}$, par la règle de la constante avec $\lambda = 1$. Soit $p \in \mathbb{N}$ et supposons $\prod_{k=m}^{n} a_k^{\,p} = \bigl( \prod_{k=m}^{n} a_k \bigr)^{p}$. Alors $$ \begin{aligned} \prod_{k=m}^{n} a_k^{\,p+1} &= \prod_{k=m}^{n} \bigl( a_k^{\,p}\, a_k \bigr) && \text{(règle sur les puissances)} \\ &= \Bigl( \prod_{k=m}^{n} a_k^{\,p} \Bigr) \Bigl( \prod_{k=m}^{n} a_k \Bigr) && \text{(première règle, pour les facteurs $a_k^{\,p}$ et $a_k$)} \\ &= \Bigl( \prod_{k=m}^{n} a_k \Bigr)^{p} \Bigl( \prod_{k=m}^{n} a_k \Bigr) && \text{(hypothèse de récurrence sur $p$)} \\ &= \Bigl( \prod_{k=m}^{n} a_k \Bigr)^{p+1}. \end{aligned} $$ C'est la règle pour $p + 1$, et la récurrence sur $p$ la donne pour tout $p \in \mathbb{N}$.
Quotient. Un produit de réels non nuls est non nul : c'est vrai pour le produit vide, et si $\prod_{k=m}^{n} b_k \ne 0$ et $b_{n+1} \ne 0$, leur produit est non nul. Supposons $b_k \ne 0$ pour tout $k$. Par la première règle appliquée aux facteurs $\frac{a_k}{b_k}$ et $b_k$, $$ \begin{aligned} \Bigl( \prod_{k=m}^{n} \frac{a_k}{b_k} \Bigr) \Bigl( \prod_{k=m}^{n} b_k \Bigr) &= \prod_{k=m}^{n} \Bigl( \frac{a_k}{b_k}\, b_k \Bigr) && \text{(première règle)} \\ &= \prod_{k=m}^{n} a_k, \end{aligned} $$ la dernière étape simplifiant chaque facteur. En divisant par le nombre non nul $\prod_{k=m}^{n} b_k$, on obtient le quotient.
Relation de Chasles, par récurrence sur $n \ge q$, avec $m$ et $q$ fixés. Pour $n = q$ le produit de $q + 1$ à $q$ est vide, égal à $1$, et la relation s'écrit $\prod_{k=m}^{q} a_k = \bigl( \prod_{k=m}^{q} a_k \bigr) \cdot 1$. Si elle est vraie pour $n \ge q$, $$ \begin{aligned} \prod_{k=m}^{n+1} a_k &= \Bigl( \prod_{k=m}^{n} a_k \Bigr) a_{n+1} && \text{(définition de $\prod$)} \\ &= \Bigl( \prod_{k=m}^{q} a_k \Bigr) \Bigl( \prod_{k=q+1}^{n} a_k \Bigr) a_{n+1} && \text{(hypothèse de récurrence)} \\ &= \Bigl( \prod_{k=m}^{q} a_k \Bigr) \Bigl( \prod_{k=q+1}^{n+1} a_k \Bigr), \end{aligned} $$ la dernière étape étant la définition de $\prod$ de $q + 1$ à $n + 1$.
Décalage et réflexion, première démonstration, par l'énumération. Si $n < m$ tous les produits sont vides et valent $1$. Si $n \ge m$, les listes $a_{j-r}$ ($m + r \le j \le n + r$) et $a_{m+n-j}$ ($m \le j \le n$) contiennent chaque facteur $a_k$, $m \le k \le n$, exactement une fois : ce sont des énumérations de la famille $(a_k)_{k \in \llbracket m, n \rrbracket}$, donc la Définition « Produit sur un ensemble fini » donne les deux égalités.
Décalage et réflexion, seconde démonstration, par la forme développée. Si $n < m$ tous les produits sont vides et valent $1$. Si $n \ge m$, alors pour $j$ allant de $m + r$ à $n + r$ les facteurs $a_{j-r}$ sont $a_m, a_{m+1}, \dots, a_n$ dans le même ordre, et pour $j$ allant de $m$ à $n$ les facteurs $a_{m+n-j}$ sont $a_n, a_{n-1}, \dots, a_m$, les mêmes facteurs dans l'ordre inverse, qui a le même produit par la commutativité de la multiplication (la Définition « Produit sur un ensemble fini »).

Piège — un produit n'est pas une somme

Un produit est multiplicatif, et rien de plus. Le produit de sommes n'est pas la somme des produits : avec $a_k = k$ et $b_k = 1$, $\prod_{k=1}^{2} (a_k + b_k) = 2 \cdot 3 = 6$, alors que $\prod_{k=1}^{2} a_k + \prod_{k=1}^{2} b_k = 2 + 1 = 3$. Un facteur constant est élevé à la puissance du nombre de facteurs : $\prod_{k=1}^{n} (2a_k) = 2^n \prod_{k=1}^{n} a_k$, et non $2 \prod_{k=1}^{n} a_k$. Enfin $\prod_{k=1}^{n} n = n^n$ n'est pas $n! = \prod_{k=1}^{n} k$, et $(2n)!$ n'est pas $2 \times n!$ : pour $n = 2$, $(2n)! = 4! = 24$ alors que $2 \times 2! = 4$.

Signaler une erreur

Compétences à pratiquer

Évaluer un produit écrit avec $\prod$ ★
Utiliser les règles de calcul sur les produits ★★

I.5 La factorielle

Un produit d'entiers consécutifs

La factorielle est le produit des premiers entiers strictement positifs. Le lycée la définissait comme la liste $1 \times 2 \times \dots \times n$ ; avec le symbole produit, la définition tient en une ligne, et le produit vide donne un sens à $0!$. La factorielle est la brique des coefficients binomiaux, où elle apparaît dans des quotients que l'on simplifie par les mêmes deux règles : une relation de récurrence entre factorielles consécutives, et un quotient de deux factorielles qui est un produit d'entiers consécutifs.

Signaler une erreur

Définition — Factorielle

Pour $n \in \mathbb{N}$, la factorielle de $n$, notée $n!$, est $$ n! = \prod_{k=1}^{n} k = 1 \times 2 \times \dots \times n. $$ Pour $n = 0$ le produit est vide, donc $0! = 1$.

Exemple — Les premières factorielles

Les premières valeurs de la factorielle sont à connaître : $$ 0! = 1, \quad 1! = 1, \quad 2! = 2, \quad 3! = 6, \quad 4! = 24, \quad 5! = 120, \quad 6! = 720, $$ et la croissance est rapide : $10! = 3\,628\,800$.

Proposition — Récurrence et quotients de factorielles

Pour $n \in \mathbb{N}$, $(n + 1)! = (n + 1) \times n!$.
Pour $p, n \in \mathbb{N}$ avec $p \le n$, $$ \textcolor{colorprop}{\frac{n!}{p!} = \prod_{k=p+1}^{n} k = (p + 1)(p + 2) \cdots n.} $$

En particulier $\frac{n!}{(n-1)!} = n$ pour $n \ge 1$, et $\frac{n!}{p!}$ est un produit de $n - p$ entiers consécutifs.

Preuve

La récurrence. Pour $n \in \mathbb{N}$, $$ \begin{aligned} (n + 1)! &= \prod_{k=1}^{n+1} k && \text{(définition de la factorielle)} \\ &= \Bigl( \prod_{k=1}^{n} k \Bigr) (n + 1) && \text{(définition de $\prod$ : ajout du dernier facteur)} \\ &= (n + 1) \times n!, \end{aligned} $$ la dernière étape étant la définition de $n!$ et la commutativité de la multiplication.
Le quotient. Soit $p \le n$. La relation de Chasles pour les produits, avec la coupure en $q = p$ et $0 \le p \le n$, donne $$ \begin{aligned} n! &= \prod_{k=1}^{n} k && \text{(définition de la factorielle)} \\ &= \Bigl( \prod_{k=1}^{p} k \Bigr) \Bigl( \prod_{k=p+1}^{n} k \Bigr) && \text{(relation de Chasles pour les produits)} \\ &= p! \prod_{k=p+1}^{n} k, \end{aligned} $$ la dernière étape étant la définition de $p!$. Le nombre $p!$ est un produit d'entiers strictement positifs, donc strictement positif, donc non nul, et la division par $p!$ donne $\frac{n!}{p!} = \prod_{k=p+1}^{n} k$. Ce produit va de $p + 1$ à $n$, donc il a $n - (p + 1) + 1 = n - p$ facteurs.

Méthode — Simplifier un quotient de factorielles

Pour simplifier $\frac{n!}{m!}$ avec $m \le n$, écrire la plus grande factorielle à partir de son sommet jusqu'à ce que la plus petite apparaisse, puis simplifier :

Quotient avec la plus petite factorielle au dénominateur : $\frac{n!}{(n-k)!} = n (n-1) \cdots (n-k+1)$, un produit de $k$ entiers consécutifs terminant à $n$.
Quotient avec un paramètre : $\frac{(n+k)!}{n!} = (n+k)(n+k-1) \cdots (n+1)$, un produit de $k$ entiers consécutifs commençant juste au-dessus de $n$ ; pour un petit $k$, appliquer $k$ fois la récurrence $(N + 1)! = (N + 1)\,N!$, comme dans $(n + 2)! = (n + 2)(n + 1)\,n!$.

Le nombre de facteurs est la différence des deux arguments. Cette réécriture est l'outil de fond de toute manipulation des coefficients binomiaux.

Méthode — Calculer un produit

Pour calculer un produit $\prod_{k=1}^{n} a_k$ sous forme close :

Séparer les facteurs avec les règles de calcul sur les produits : les constantes sortent élevées au nombre de facteurs, $\prod_{k=1}^{n} (\lambda a_k) = \lambda^n \prod_{k=1}^{n} a_k$, les puissances se regroupent, un quotient se coupe en deux produits.
Reconnaître une factorielle dans un produit d'entiers consécutifs : $\prod_{k=1}^{n} k = n!$, $\prod_{k=1}^{n} (2k) = 2^n \, n!$, et $\prod_{k=p+1}^{n} k = \frac{n!}{p!}$ ; un produit $\prod_{k=1}^{n} (n + k)$ vaut $\frac{(2n)!}{n!}$, après le décalage $j = n + k$.

Compter les facteurs : une constante à élever à une puissance l'est à $n - m + 1$, non à $n$.

Exemple — Un produit et un quotient de factorielles

Pour $n \ge 1$, simplifier $P_n = \prod_{k=1}^{n} (2k)$ et $Q_n = \frac{(n+2)!}{(n-1)!}$.

Correction

Le produit $P_n$. $$ \begin{aligned} \prod_{k=1}^{n} (2k) &= 2^{n} \prod_{k=1}^{n} k && \text{(facteur constant : $n - 1 + 1 = n$ facteurs)} \\ &= 2^{n} \, n!, \end{aligned} $$ la dernière étape étant la définition de la factorielle. Vérification pour $n = 3$ : $2 \cdot 4 \cdot 6 = 48 = 2^3 \cdot 3!$.
Le quotient $Q_n$. $$ \begin{aligned} \frac{(n+2)!}{(n-1)!} &= \frac{(n+2)(n+1)\,n\,(n-1)!}{(n-1)!} && \text{(récurrence appliquée trois fois)} \\ &= (n+2)(n+1)\,n, \end{aligned} $$ la dernière étape simplifiant $(n-1)!$, qui est non nul. Vérification pour $n = 3$ : $\frac{5!}{2!} = \frac{120}{2} = 60 = 5 \cdot 4 \cdot 3$.

Factorielle et boucles

La relation de récurrence $(n + 1)! = (n + 1) \times n!$ est exactement la façon dont un programme calcule une factorielle : partir de $1$ et multiplier successivement par $2, 3, \dots, n$. Une somme se calcule de la même façon, par une boucle qui part de $0$ et ajoute $a_m, a_{m+1}, \dots, a_n$ l'un après l'autre, comme le montre la Méthode « D'une somme sigma à un algorithme » du chapitre Suites : la récurrence de la Définition « Notation sigma » est la boucle. La simplification d'un quotient comme $\frac{(n+1)!}{n!} = n + 1$ repose sur la même identité.

Signaler une erreur

Preuve différée

Les Définitions « Somme sur un ensemble fini » et « Produit sur un ensemble fini » ont admis que la valeur ne dépend pas de l'énumération choisie. La démonstration de l'indépendance vis-à-vis de l'énumération n'emploie que la Définition « Notation sigma », qui fixe la somme d'une liste, et la commutativité et l'associativité de l'addition de trois réels, sous la forme $(x + y) + z = (x + z) + y$. Celle de l'indépendance vis-à-vis du parenthésage n'emploie que la relation de Chasles, démontrée plus haut par récurrence à partir de la définition de $\sum$, et celle de la Proposition « Règles de calcul sur les produits », démontrée par récurrence à partir de la définition de $\prod$. Pour un produit la première démonstration est la même, avec $\times$ à la place de $+$ et $1$ à la place de $0$.
Lemme, retirer un terme. Soient $b_1, \dots, b_q$ des réels, avec $q \ge 1$, soit $1 \le r \le q$, et soit $b'_1, \dots, b'_{q-1}$ la liste obtenue en supprimant $b_r$ : $b'_j = b_j$ pour $j < r$ et $b'_j = b_{j+1}$ pour $j \ge r$. Alors $\sum_{j=1}^{q} b_j = \sum_{j=1}^{q-1} b'_j + b_r$.
Démonstration du lemme, par récurrence sur $q$. Pour $q = 1$, $r = 1$ et la liste $b'$ est vide : les deux membres valent $b_1$. Soit $q \ge 1$ et supposons le lemme pour les listes de $q$ termes. Soient $b_1, \dots, b_{q+1}$ des réels et $1 \le r \le q+1$. Si $r = q + 1$, la liste $b'$ est $b_1, \dots, b_q$ et le lemme est la définition de $\sum$. Si $r \le q$, alors $$ \begin{aligned} \sum_{j=1}^{q+1} b_j &= \sum_{j=1}^{q} b_j + b_{q+1} && \text{(définition de $\sum$)} \\ &= \Bigl( \sum_{j=1}^{q-1} b'_j + b_r \Bigr) + b_{q+1} && \text{(hypothèse de récurrence sur $b_1, \dots, b_q$)} \\ &= \Bigl( \sum_{j=1}^{q-1} b'_j + b_{q+1} \Bigr) + b_r && \text{(commutativité et associativité de l'addition)} \\ &= \sum_{j=1}^{q} b'_j + b_r, \end{aligned} $$ la dernière étape étant la définition de $\sum$, car le dernier terme de la liste $b'$ est $b'_q = b_{q+1}$ lorsque $r \le q$.
L'énoncé. Pour $p \in \mathbb{N}$, notons $Q_p$ la propriété « pour tout ensemble fini $I$ muni d'une énumération $i_1, \dots, i_p$, toute famille $(a_i)_{i \in I}$ et toute énumération $i'_1, \dots, i'_s$ de $I$, $s = p$ et $\sum_{j=1}^{p} a_{i_j} = \sum_{j=1}^{s} a_{i'_j}$ ». Pour $p = 0$, $I$ est vide, donc une liste $i'_1, \dots, i'_s$ d'éléments de $I$ est vide, $s = 0$, et les deux sommes valent $0$ : $Q_0$ est vraie. Soit $p \in \mathbb{N}$ et supposons $Q_p$. Soit $I$ muni des énumérations $i_1, \dots, i_{p+1}$ et $i'_1, \dots, i'_s$, et soit $x = i_{p+1}$. L'élément $x$ figure exactement une fois dans la seconde liste, à une position $r$, donc $s \ge 1$. En retirant $x$ de chaque liste, on obtient deux énumérations de $I \setminus \{x\}$ : $i_1, \dots, i_p$ et la liste $i''$ des $s - 1$ termes de $i'$ autres que $x$, puisque chaque élément de $I \setminus \{x\}$ figure une fois dans chaque liste et que $x$ n'y figure plus. Par $Q_p$ pour $I \setminus \{x\}$, $s - 1 = p$ et $\sum_{j=1}^{p} a_{i_j} = \sum_{j=1}^{s-1} a_{i''_j}$. Alors $$ \begin{aligned} \sum_{j=1}^{p+1} a_{i_j} &= \sum_{j=1}^{p} a_{i_j} + a_x && \text{(définition de $\sum$)} \\ &= \sum_{j=1}^{s-1} a_{i''_j} + a_x && \text{($Q_p$)} \\ &= \sum_{j=1}^{s} a_{i'_j}, \end{aligned} $$ la dernière étape étant le lemme pour les nombres $b_j = a_{i'_j}$ et la position $r$, où $b_r = a_x$. C'est $Q_{p+1}$, avec $s = p + 1$. Puisque $Q_0$ est vraie et que $Q_p \Rightarrow Q_{p+1}$ pour tout $p \in \mathbb{N}$, par récurrence $Q_p$ est vraie pour tout $p \in \mathbb{N}$ : deux énumérations d'un ensemble fini ont le même nombre de termes et la même somme, donc la somme $\sum_{i \in I} a_i$ ne dépend pas de l'énumération. Pour le produit, la même démonstration, avec la Définition « Notation produit » et la commutativité et l'associativité de la multiplication, donne le même résultat pour $\prod_{i \in I} a_i$.
Indépendance vis-à-vis du parenthésage, pour l'addition. La liste vide n'a aucune addition à parenthéser : sa valeur est $0$, la somme vide. Un parenthésage d'une liste $x_m, \dots, x_{m+n-1}$ de $n \ge 1$ réels est une façon de les additionner deux nombres à la fois, toujours deux sous-listes consécutives. Pour $n = 1$ la valeur est $x_m$, sans addition. Pour $n \ge 2$ la dernière addition partage la liste en deux sous-listes consécutives non vides $x_m, \dots, x_{m+r-1}$ et $x_{m+r}, \dots, x_{m+n-1}$, avec $1 \le r \le n - 1$, chacune parenthésée à son tour, et la valeur est la somme des valeurs des deux sous-listes. Pour $n \ge 1$, notons $R_n$ la propriété « pour tout $m \in \mathbb{Z}$, tous réels $x_m, \dots, x_{m+n-1}$ et tout parenthésage de cette liste, la valeur est $\sum_{k=m}^{m+n-1} x_k$ ». Pour $n = 1$ la valeur est $x_m$, et $\sum_{k=m}^{m} x_k = \sum_{k=m}^{m-1} x_k + x_m = 0 + x_m$ par la définition de $\sum$ : $R_1$ est vraie. Soit $n \ge 2$ et supposons $R_1, \dots, R_{n-1}$. Soit un parenthésage de $x_m, \dots, x_{m+n-1}$ qui partage la liste après $r$ termes, et posons $p = m + r - 1$ et $N = m + n - 1$, de sorte que $m \le p < N$. Chaque sous-liste a moins de $n$ termes, donc l'hypothèse de récurrence donne leurs valeurs, la seconde avec $m$ remplacé par $p + 1$. Alors $$ \begin{aligned} \text{valeur du parenthésage} &= \sum_{k=m}^{p} x_k + \sum_{k=p+1}^{N} x_k && \text{(hypothèse de récurrence sur les deux sous-listes)} \\ &= \sum_{k=m}^{N} x_k, \end{aligned} $$ la dernière étape étant la relation de Chasles, sous la forme de sa première démonstration. C'est $R_n$, et la récurrence forte donne $R_n$ pour tout $n \ge 1$ : tous les parenthésages d'une liste ont la même valeur, la somme de la liste.
Indépendance vis-à-vis du parenthésage, pour la multiplication. La liste vide n'a aucune multiplication à parenthéser : sa valeur est $1$, le produit vide. Un parenthésage de $x_m, \dots, x_{m+n-1}$ se définit comme ci-dessus, avec des produits à la place des sommes : la valeur est $x_m$ pour $n = 1$, et pour $n \ge 2$ le produit des valeurs des deux sous-listes. Notons $R'_n$ la propriété « pour tout $m \in \mathbb{Z}$, tous réels $x_m, \dots, x_{m+n-1}$ et tout parenthésage de cette liste, la valeur est $\prod_{k=m}^{m+n-1} x_k$ ». Pour $n = 1$, $\prod_{k=m}^{m} x_k = \prod_{k=m}^{m-1} x_k \cdot x_m = 1 \cdot x_m = x_m$ par la définition de $\prod$ : $R'_1$ est vraie. Soit $n \ge 2$ et supposons $R'_1, \dots, R'_{n-1}$. Avec les mêmes $p$ et $N$, $$ \begin{aligned} \text{valeur du parenthésage} &= \Bigl( \prod_{k=m}^{p} x_k \Bigr) \Bigl( \prod_{k=p+1}^{N} x_k \Bigr) && \text{(hypothèse de récurrence sur les deux sous-listes)} \\ &= \prod_{k=m}^{N} x_k, \end{aligned} $$ la dernière étape étant la relation de Chasles de la Proposition « Règles de calcul sur les produits », démontrée par récurrence à partir de la définition de $\prod$ avec le même rang $p$ à la place de $q$. C'est $R'_n$, et la récurrence forte la donne pour tout $n \ge 1$. Avec l'indépendance vis-à-vis de l'énumération, une somme ou un produit fini de réels ne dépend ni de l'ordre ni du parenthésage de ses termes.

Signaler une erreur

Compétences à pratiquer

Évaluer une factorielle ou un quotient de factorielles ★
Simplifier un quotient de factorielles ★
Exprimer un produit avec des factorielles ★★
Comparer une factorielle et une puissance ★★★

II Télescopage et sommes classiques

Des termes qui se compensent aux formes closes

La plupart des sommes rencontrées en pratique ne sont pas seulement réécrites : elles sont calculées, c'est-à-dire ramenées à une forme close en $n$. Trois outils y conduisent. Le télescopage fait se compenser deux à deux les termes d'une somme, de sorte que deux seulement subsistent. Les sommes classiques — les premiers entiers, leurs carrés et leurs cubes, et la somme géométrique — sont les formes closes auxquelles on ramène une somme par développement et linéarité, et elles se démontrent elles-mêmes par télescopage. Et quelques méthodes de calcul choisissent entre développer, télescoper et raisonner par récurrence, selon la forme du terme général.

Signaler une erreur

II.1 Télescopage

Une somme de différences consécutives

Une somme télescopique est une somme de différences consécutives $u_{k+1} - u_k$. Écrite en extension, chaque terme intermédiaire apparaît deux fois, une fois avec le signe $+$ et une fois avec le signe $-$, et les deux occurrences se compensent ; seuls le premier et le dernier terme subsistent : $$ (u_{m+1} - u_m) + (u_{m+2} - u_{m+1}) + \dots + (u_{n+1} - u_n) = u_{n+1} - u_m. $$ Le savoir-faire est de reconnaître qu'un terme général est une telle différence : la somme entière se réduit alors à deux termes. La Proposition « Somme télescopique » démontre cette réduction, de deux façons.

Signaler une erreur

Proposition — Somme télescopique

Soient $m, n \in \mathbb{Z}$ avec $n \ge m - 1$, et $u_k$ un réel pour $m \le k \le n + 1$. Alors $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=m}^{n} (u_{k+1} - u_k) &= u_{n+1} - u_m \\ (u_{m+1} - u_m) + (u_{m+2} - u_{m+1}) + \dots + (u_{n+1} - u_n) &= u_{n+1} - u_m \end{aligned}} $$ Lue dans l'autre sens, pour $n \ge m$ : $u_n = u_m + \sum_{k=m}^{n-1} (u_{k+1} - u_k)$, un terme d'une suite est son premier terme plus la somme des accroissements.

Preuve

Pour $n = m - 1$ la somme est vide, égale à $0$, et $u_{n+1} - u_m = u_m - u_m = 0$. La seconde formule est la première avec $n - 1$ à la place de $n$, ce qui est permis lorsque $n - 1 \ge m - 1$.
Première démonstration, par linéarité, décalage et Chasles. Soit $n \ge m$. $$ \begin{aligned} \sum_{k=m}^{n} (u_{k+1} - u_k) &= \sum_{k=m}^{n} u_{k+1} - \sum_{k=m}^{n} u_k && \text{(linéarité)} \\ &= \sum_{j=m+1}^{n+1} u_j - \sum_{k=m}^{n} u_k && \text{(décalage $j = k + 1$)} \\ &= \Bigl( \sum_{j=m+1}^{n} u_j + u_{n+1} \Bigr) - \Bigl( u_m + \sum_{k=m+1}^{n} u_k \Bigr) && \text{(relation de Chasles : $u_{n+1}$ et $u_m$ isolés)} \\ &= u_{n+1} - u_m, \end{aligned} $$ la dernière étape parce que les deux sommes de $m + 1$ à $n$ sont égales, l'indice étant muet.
Seconde démonstration, par récurrence sur $n$. Pour $n \ge m - 1$, notons $P_n$ la propriété « $\sum_{k=m}^{n} (u_{k+1} - u_k) = u_{n+1} - u_m$ ». L'initialisation $P_{m-1}$ est le cas de la somme vide, traité en premier. Soit $n \ge m - 1$ et supposons $P_n$. Alors $$ \begin{aligned} \sum_{k=m}^{n+1} (u_{k+1} - u_k) &= \sum_{k=m}^{n} (u_{k+1} - u_k) + (u_{n+2} - u_{n+1}) && \text{(définition de $\sum$)} \\ &= (u_{n+1} - u_m) + (u_{n+2} - u_{n+1}) && \text{(hypothèse de récurrence)} \\ &= u_{n+2} - u_m, \end{aligned} $$ la dernière étape simplifiant $u_{n+1}$. C'est $P_{n+1}$, et la récurrence donne $P_n$ pour tout $n \ge m - 1$.

Le télescopage d'un produit

L'analogue multiplicatif de la somme télescopique : un produit de quotients $\frac{u_{k+1}}{u_k}$ se réduit à deux termes aux bornes, car chaque numérateur simplifie le dénominateur du facteur suivant. On s'en sert dès qu'une fraction s'écrit comme le quotient de deux valeurs consécutives.

Signaler une erreur

Proposition — Produit télescopique

Soient $m, n \in \mathbb{Z}$ avec $n \ge m - 1$, et $u_k$ un réel non nul pour $m \le k \le n + 1$. Alors $$ \textcolor{colorprop}{\prod_{k=m}^{n} \frac{u_{k+1}}{u_k} = \frac{u_{n+1}}{u_m}.} $$

Preuve

Pour $n = m - 1$ le produit est vide, égal à $1$, et $\frac{u_{n+1}}{u_m} = \frac{u_m}{u_m} = 1$.
Première démonstration, par les règles sur les produits. Soit $n \ge m$. $$ \begin{aligned} \prod_{k=m}^{n} \frac{u_{k+1}}{u_k} &= \frac{\prod_{k=m}^{n} u_{k+1}}{\prod_{k=m}^{n} u_k} && \text{(règle du quotient, les $u_k$ étant non nuls)} \\ &= \frac{\prod_{j=m+1}^{n+1} u_j}{\prod_{k=m}^{n} u_k} && \text{(décalage $j = k + 1$)} \\ &= \frac{\bigl( \prod_{j=m+1}^{n} u_j \bigr) u_{n+1}}{u_m \prod_{k=m+1}^{n} u_k} && \text{(relation de Chasles : $u_{n+1}$ et $u_m$ isolés)} \\ &= \frac{u_{n+1}}{u_m}, \end{aligned} $$ la dernière étape simplifiant le facteur commun $\prod_{j=m+1}^{n} u_j$, qui est non nul comme produit de nombres non nuls.
Seconde démonstration, par récurrence sur $n$. Pour $n \ge m - 1$, notons $P_n$ la propriété « $\prod_{k=m}^{n} \frac{u_{k+1}}{u_k} = \frac{u_{n+1}}{u_m}$ ». L'initialisation $P_{m-1}$ est le cas du produit vide, traité en premier. Soit $n \ge m - 1$ et supposons $P_n$. Alors $$ \begin{aligned} \prod_{k=m}^{n+1} \frac{u_{k+1}}{u_k} &= \Bigl( \prod_{k=m}^{n} \frac{u_{k+1}}{u_k} \Bigr) \frac{u_{n+2}}{u_{n+1}} && \text{(définition de $\prod$)} \\ &= \frac{u_{n+1}}{u_m} \cdot \frac{u_{n+2}}{u_{n+1}} && \text{(hypothèse de récurrence)} \\ &= \frac{u_{n+2}}{u_m}, \end{aligned} $$ la dernière étape simplifiant le nombre non nul $u_{n+1}$. C'est $P_{n+1}$, et la récurrence donne $P_n$ pour tout $n \ge m - 1$.

Proposition — Télescopage avec un écart

Soient $m, n, p \in \mathbb{Z}$ avec $p \ge 1$ et $n \ge m + p - 1$, et $u_k$ un réel pour $m \le k \le n + p$. Alors $$ \textcolor{colorprop}{\sum_{k=m}^{n} (u_{k+p} - u_k) = \sum_{k=n+1}^{n+p} u_k - \sum_{k=m}^{m+p-1} u_k.} $$ La somme se réduit aux $p$ derniers termes moins les $p$ premiers ; pour $p = 1$ c'est la Proposition « Somme télescopique ».

Preuve

$$ \begin{aligned} \sum_{k=m}^{n} (u_{k+p} - u_k) &= \sum_{k=m}^{n} u_{k+p} - \sum_{k=m}^{n} u_k && \text{(linéarité)} \\ &= \sum_{j=m+p}^{n+p} u_j - \sum_{k=m}^{n} u_k && \text{(décalage $j = k + p$)} \\ &= \Bigl( \sum_{j=m+p}^{n} u_j + \sum_{j=n+1}^{n+p} u_j \Bigr) - \Bigl( \sum_{k=m}^{m+p-1} u_k + \sum_{k=m+p}^{n} u_k \Bigr) && \text{(relation de Chasles en $n$ et en $m + p - 1$)} \\ &= \sum_{j=n+1}^{n+p} u_j - \sum_{k=m}^{m+p-1} u_k, \end{aligned} $$ la dernière étape parce que les deux sommes de $m + p$ à $n$ sont égales, l'indice étant muet. Les deux coupures de la relation de Chasles sont permises car $m - 1 \le m + p - 1 \le n$ et $m + p - 1 \le n \le n + p$.

Exemple — Une somme télescopique de fractions

Calculer $\sum_{k=1}^{n} \frac{1}{k(k+1)}$ pour $n \ge 1$.

Correction

Le terme général est une différence : $\frac{1}{k} - \frac{1}{k+1} = \frac{(k+1) - k}{k(k+1)} = \frac{1}{k(k+1)}$. Avec $u_k = -\frac{1}{k}$, c'est $u_{k+1} - u_k = -\frac{1}{k+1} + \frac{1}{k}$. $$ \begin{aligned} \sum_{k=1}^{n} \frac{1}{k(k+1)} &= \sum_{k=1}^{n} (u_{k+1} - u_k) && \text{(décomposition $\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}$, $u_k = -\frac{1}{k}$)} \\ &= u_{n+1} - u_1 && \text{(somme télescopique)} \\ &= -\frac{1}{n+1} + 1 && \text{($u_{n+1} = -\frac{1}{n+1}$ et $u_1 = -1$)} \\ &= \frac{n}{n+1}, \end{aligned} $$ la dernière étape mettant les deux termes sur le dénominateur $n + 1$. Vérification : pour $n = 2$, $\frac{1}{2} + \frac{1}{6} = \frac{2}{3}$.

Exemple — Une somme télescopique de logarithmes

Calculer $\sum_{k=1}^{n} \ln \bigl( 1 + \frac{1}{k} \bigr)$ pour $n \ge 1$.

Correction

Le terme général est une différence de logarithmes, avec $u_k = \ln k$. $$ \begin{aligned} \sum_{k=1}^{n} \ln \Bigl( 1 + \frac{1}{k} \Bigr) &= \sum_{k=1}^{n} \bigl( \ln (k+1) - \ln k \bigr) && \text{($1 + \frac{1}{k} = \frac{k+1}{k}$ et $\ln \frac{a}{b} = \ln a - \ln b$)} \\ &= \ln (n+1) - \ln 1 && \text{(somme télescopique, $u_k = \ln k$)} \\ &= \ln (n+1), \end{aligned} $$ la dernière étape parce que $\ln 1 = 0$.

Exemple — Un produit télescopique

Calculer $\prod_{k=1}^{n} \frac{k+1}{k}$ pour $n \ge 1$.

Correction

Le facteur général est le quotient de deux valeurs consécutives de $u_k = k$, qui est non nul pour $k \ge 1$. $$ \begin{aligned} \prod_{k=1}^{n} \frac{k+1}{k} &= \prod_{k=1}^{n} \frac{u_{k+1}}{u_k} && \text{(avec $u_k = k$)} \\ &= \frac{u_{n+1}}{u_1} && \text{(produit télescopique)} \\ &= n + 1, \end{aligned} $$ la dernière étape parce que $u_{n+1} = n + 1$ et $u_1 = 1$. Vérification : pour $n = 3$, $\frac{2}{1} \cdot \frac{3}{2} \cdot \frac{4}{3} = 4$.

Méthode — Reconnaître une somme télescopique

Pour calculer une somme par télescopage, chercher $u_{k+1} - u_k$ (ou $u_k - u_{k+1}$) dans le terme général :

Une fraction rationnelle : $\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}$, différence de $u_k = -\frac{1}{k}$. Pour un écart plus large, $\frac{1}{k(k+2)} = \frac{1}{2} \bigl( \frac{1}{k} - \frac{1}{k+2} \bigr)$ est une différence avec un écart $p = 2$, traitée par la Proposition « Télescopage avec un écart ».
Un logarithme d'un quotient : $\ln \frac{f(k+1)}{f(k)} = \ln f(k+1) - \ln f(k)$.
Une factorielle : $k \cdot k! = (k+1)! - k!$, puisque $(k+1)! = (k+1)\,k! = k \cdot k! + k!$.
Une différence de deux valeurs consécutives d'une expression en $k$, comme $(k+1)^2 - k^2 = 2k + 1$ ; lorsque l'expression ne se voit pas, deviner $u_k$ à partir de la forme et vérifier que $u_{k+1} - u_k$ est le terme général.

Une fois le terme général écrit $u_{k+1} - u_k$, la somme se réduit à $u_{n+1} - u_m$. Vérifier les bornes : le nouveau premier terme est $u_m$ et le nouveau dernier terme est $u_{n+1}$.

Méthode — Reconnaître un produit télescopique

Pour calculer un produit par télescopage, chercher $\frac{u_{k+1}}{u_k}$ dans le facteur général :

Un quotient de valeurs consécutives : $\frac{f(k+1)}{f(k)}$ pour une expression $f$ qui ne s'annule jamais, comme dans $\frac{k+1}{k}$ ou $\frac{2k+2}{2k}$.
Un quotient de factorielles consécutives : $\frac{(k+1)!}{k!} = k + 1$, de sorte que $\prod_{k=1}^{n} \frac{(k+1)!}{k!} = \frac{(n+1)!}{1!} = (n+1)!$.
Le détour par le logarithme : lorsque les facteurs sont strictement positifs, prendre le logarithme, qui transforme le produit en la somme $\sum \bigl( \ln u_{k+1} - \ln u_k \bigr)$, la télescoper, puis appliquer $\exp$.

Une fois reconnu, le produit se réduit à $\frac{u_{n+1}}{u_m}$ : seules les valeurs aux bornes subsistent. Les valeurs $u_k$ doivent être non nulles.

Compétences à pratiquer

Reconnaître une somme ou un produit télescopique ★
Évaluer une somme ou un produit télescopique ★
Télescoper une différence ou un quotient donnés ★
Décomposer une fraction puis télescoper ★★
Télescoper un produit ★★
Télescoper avec un écart ★★
Trouver le télescopage caché dans une somme ★★★

II.2 Sommes classiques

Quatre sommes et une factorisation

Quatre sommes doivent être au bout des doigts : la somme des premiers entiers, la somme de leurs carrés, la somme de leurs cubes, et la somme géométrique. S'y ajoute une factorisation, la contrepartie algébrique de la somme géométrique : $a^n - b^n$. Toutes se trouvent par réflexion ou par télescopage, et aucune n'a besoin d'être connue d'avance : le télescopage de $(k+1)^3 - k^3$ produit la somme des carrés. La première se lit sur un dessin. Deux escaliers de $1, 2, \dots, n$ carrés, l'un retourné contre l'autre, remplissent un rectangle de $n$ lignes et $n + 1$ colonnes, dont l'aire est $n(n+1)$ ; chaque escalier a donc pour aire $\frac{n(n+1)}{2}$. Le dessin montre le cas $n = 4$ : l'escalier $1 + 2 + 3 + 4$ et l'escalier $4 + 3 + 2 + 1$ remplissent le rectangle de $4$ lignes et $5$ colonnes.

Signaler une erreur

Théorème — Sommes classiques

Pour $n \in \mathbb{N}$ :

Somme des premiers entiers. $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=0}^{n} k &= \frac{n(n+1)}{2} \\ 1 + 2 + 3 + \dots + n &= \frac{n(n+1)}{2} \end{aligned}} $$
Somme des carrés. $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=0}^{n} k^2 &= \frac{n(n+1)(2n+1)}{6} \\ 1^2 + 2^2 + 3^2 + \dots + n^2 &= \frac{n(n+1)(2n+1)}{6} \end{aligned}} $$
Somme des cubes. $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=0}^{n} k^3 &= \Bigl( \frac{n(n+1)}{2} \Bigr)^2 \\ 1^3 + 2^3 + 3^3 + \dots + n^3 &= \Bigl( \frac{n(n+1)}{2} \Bigr)^2 \end{aligned}} $$
Somme géométrique. Pour $x \in \mathbb{R}$ avec $x \ne 1$, $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=0}^{n} x^k &= \frac{1 - x^{n+1}}{1 - x} \\ 1 + x + x^2 + \dots + x^n &= \frac{1 - x^{n+1}}{1 - x} \end{aligned}} $$ et pour $x = 1$, $\sum_{k=0}^{n} 1^k = n + 1$.

Preuve

Chaque résultat se démontre par deux méthodes. La première est celle qui n'a pas besoin de la formule d'avance : la réflexion, ou le télescopage de la puissance suivante, qui trouve la forme close. La seconde est la récurrence, qui vérifie une forme close donnée. Le terme d'indice $0$ de $\sum k$, $\sum k^2$ et $\sum k^3$ est $0$, donc les sommes depuis $k = 1$ et depuis $k = 0$ sont égales.
Somme des premiers entiers : première méthode, par réflexion. Soit $S = \sum_{k=0}^{n} k$. $$ \begin{aligned} 2S &= \sum_{k=0}^{n} k + \sum_{k=0}^{n} (n - k) && \text{(réflexion sur la seconde copie de $S$)} \\ &= \sum_{k=0}^{n} \bigl( k + (n - k) \bigr) && \text{(linéarité)} \\ &= \sum_{k=0}^{n} n && \text{($k + (n - k) = n$)} \\ &= (n + 1)\,n, \end{aligned} $$ la dernière étape étant le nombre de termes, $n - 0 + 1$. Donc $S = \frac{n(n+1)}{2}$.
Seconde méthode, par télescopage. $$ \begin{aligned} \sum_{k=0}^{n} (2k + 1) &= \sum_{k=0}^{n} \bigl( (k+1)^2 - k^2 \bigr) && \text{(développement de $(k+1)^2$)} \\ &= (n+1)^2 - 0^2 && \text{(somme télescopique, $u_k = k^2$)} \\ &= (n+1)^2, \end{aligned} $$ et par linéarité et nombre de termes, $\sum_{k=0}^{n} (2k + 1) = 2S + (n + 1)$. Donc $2S = (n+1)^2 - (n+1) = n(n+1)$.
Somme des carrés : première méthode, par télescopage. Soit $T = \sum_{k=0}^{n} k^2$, et $S = \sum_{k=0}^{n} k = \frac{n(n+1)}{2}$. $$ \begin{aligned} (n+1)^3 &= \sum_{k=0}^{n} \bigl( (k+1)^3 - k^3 \bigr) && \text{(somme télescopique, $u_k = k^3$, $u_0 = 0$)} \\ &= \sum_{k=0}^{n} (3k^2 + 3k + 1) && \text{(développement de $(k+1)^3$)} \\ &= 3T + 3S + (n + 1) && \text{(linéarité, nombre de termes)} \\ &= 3T + \frac{3n(n+1)}{2} + (n+1), \end{aligned} $$ la dernière étape étant la valeur de $S$. En multipliant par $2$ et en isolant $T$, $$ \begin{aligned} 6T &= 2(n+1)^3 - 3n(n+1) - 2(n+1) && \text{(égalité précédente multipliée par $2$, puis isolement de $T$)} \\ &= (n+1) \bigl( 2(n+1)^2 - 3n - 2 \bigr) && \text{(factorisation de $n + 1$)} \\ &= (n+1)(2n^2 + n) && \text{(développement : $2(n+1)^2 - 3n - 2 = 2n^2 + n$)} \\ &= n(n+1)(2n+1), \end{aligned} $$ la dernière étape factorisant $n$. Donc $T = \frac{n(n+1)(2n+1)}{6}$.
Seconde méthode, par récurrence. Pour $n \in \mathbb{N}$, notons $P_n$ la propriété « $\sum_{k=0}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$ ». L'initialisation $P_0$ est $0 = 0$. Soit $n \in \mathbb{N}$ et supposons $P_n$. Alors $$ \begin{aligned} \sum_{k=0}^{n+1} k^2 &= \sum_{k=0}^{n} k^2 + (n+1)^2 && \text{(définition de $\sum$)} \\ &= \frac{n(n+1)(2n+1)}{6} + (n+1)^2 && \text{(hypothèse de récurrence)} \\ &= \frac{(n+1) \bigl( n(2n+1) + 6(n+1) \bigr)}{6} && \text{(dénominateur commun, factorisation de $n + 1$)} \\ &= \frac{(n+1)(2n^2 + 7n + 6)}{6} && \text{(développement)} \\ &= \frac{(n+1)(n+2)(2n+3)}{6}, \end{aligned} $$ la dernière étape factorisant $2n^2 + 7n + 6 = (n+2)(2n+3)$. C'est $P_{n+1}$, car $(n+1) + 1 = n + 2$ et $2(n+1) + 1 = 2n + 3$. Puisque $P_0$ est vraie et que $P_n \Rightarrow P_{n+1}$ pour tout $n \in \mathbb{N}$, par récurrence $P_n$ est vraie pour tout $n \in \mathbb{N}$.
Somme des cubes : première méthode, par télescopage. Soit $C = \sum_{k=0}^{n} k^3$, avec $T$ et $S$ comme définis pour les carrés et les entiers. $$ \begin{aligned} (n+1)^4 &= \sum_{k=0}^{n} \bigl( (k+1)^4 - k^4 \bigr) && \text{(somme télescopique, $u_k = k^4$, $u_0 = 0$)} \\ &= \sum_{k=0}^{n} (4k^3 + 6k^2 + 4k + 1) && \text{(développement de $(k+1)^4$)} \\ &= 4C + 6T + 4S + (n + 1) && \text{(linéarité, nombre de termes)} \\ &= 4C + n(n+1)(2n+1) + 2n(n+1) + (n+1), \end{aligned} $$ la dernière étape étant les valeurs de $T$ et de $S$. En isolant $C$, $$ \begin{aligned} 4C &= (n+1)^4 - n(n+1)(2n+1) - 2n(n+1) - (n+1) && \text{(égalité précédente, isolement de $C$)} \\ &= (n+1) \bigl( (n+1)^3 - n(2n+1) - 2n - 1 \bigr) && \text{(factorisation de $n + 1$)} \\ &= (n+1)(n^3 + n^2) && \text{(développement de $(n+1)^3$ et de $n(2n+1)$)} \\ &= n^2 (n+1)^2, \end{aligned} $$ la dernière étape factorisant $n^2$. Donc $C = \bigl( \frac{n(n+1)}{2} \bigr)^2$.
Seconde méthode, par récurrence. Pour $n \in \mathbb{N}$, notons $P_n$ la propriété « $\sum_{k=0}^{n} k^3 = \frac{n^2 (n+1)^2}{4}$ ». L'initialisation $P_0$ est $0 = 0$. Soit $n \in \mathbb{N}$ et supposons $P_n$. Alors $$ \begin{aligned} \sum_{k=0}^{n+1} k^3 &= \sum_{k=0}^{n} k^3 + (n+1)^3 && \text{(définition de $\sum$)} \\ &= \frac{n^2 (n+1)^2}{4} + (n+1)^3 && \text{(hypothèse de récurrence)} \\ &= \frac{(n+1)^2 \bigl( n^2 + 4(n+1) \bigr)}{4} && \text{(dénominateur commun, factorisation de $(n+1)^2$)} \\ &= \frac{(n+1)^2 (n+2)^2}{4}, \end{aligned} $$ la dernière étape étant $n^2 + 4n + 4 = (n+2)^2$. C'est $P_{n+1}$. Puisque $P_0$ est vraie et que $P_n \Rightarrow P_{n+1}$ pour tout $n \in \mathbb{N}$, par récurrence $P_n$ est vraie pour tout $n \in \mathbb{N}$.
Somme géométrique : première méthode, par télescopage. Soit $x \ne 1$ et $G = \sum_{k=0}^{n} x^k$. Pour $x = 1$ chaque terme vaut $1$, et le nombre de termes donne $n + 1$. $$ \begin{aligned} (1 - x)\,G &= \sum_{k=0}^{n} (x^k - x^{k+1}) && \text{(linéarité : distribution de $1 - x$)} \\ &= x^0 - x^{n+1} && \text{(somme télescopique, $u_k = -x^k$)} \\ &= 1 - x^{n+1}, \end{aligned} $$ la dernière étape étant $x^0 = 1$. En divisant par $1 - x \ne 0$, on obtient $G = \frac{1 - x^{n+1}}{1 - x}$.
Seconde méthode, par récurrence. Soit $x \ne 1$. Pour $n \in \mathbb{N}$, notons $P_n$ la propriété « $\sum_{k=0}^{n} x^k = \frac{1 - x^{n+1}}{1 - x}$ ». L'initialisation $P_0$ est $1 = \frac{1 - x}{1 - x}$. Soit $n \in \mathbb{N}$ et supposons $P_n$. Alors $$ \begin{aligned} \sum_{k=0}^{n+1} x^k &= \sum_{k=0}^{n} x^k + x^{n+1} && \text{(définition de $\sum$)} \\ &= \frac{1 - x^{n+1}}{1 - x} + x^{n+1} && \text{(hypothèse de récurrence)} \\ &= \frac{1 - x^{n+1} + x^{n+1} (1 - x)}{1 - x} && \text{(dénominateur commun)} \\ &= \frac{1 - x^{n+2}}{1 - x}, \end{aligned} $$ la dernière étape simplifiant $-x^{n+1} + x^{n+1} - x^{n+2}$. C'est $P_{n+1}$. Puisque $P_0$ est vraie et que $P_n \Rightarrow P_{n+1}$ pour tout $n \in \mathbb{N}$, avec $x \ne 1$ fixé, par récurrence $P_n$ est vraie pour tout $n \in \mathbb{N}$.
Remarque. Les formules des entiers et des cubes donnent $\sum_{k=0}^{n} k^3 = \bigl( \sum_{k=0}^{n} k \bigr)^2$ : la somme des premiers cubes est le carré de la somme des premiers entiers.

Proposition — Sommes de termes consécutifs d'une progression

Soient $p, n \in \mathbb{N}$ avec $p \le n$.

Progression arithmétique. Si $(u_k)$ vérifie $u_{k+1} - u_k = r$ pour tout $k$, alors $$ \textcolor{colorprop}{\sum_{k=p}^{n} u_k = (n - p + 1)\,\frac{u_p + u_n}{2},} $$ le nombre de termes fois la moyenne du premier et du dernier terme.
Progression géométrique. Pour $x \in \mathbb{R}$ avec $x \ne 1$, $$ \textcolor{colorprop}{\sum_{k=p}^{n} x^k = x^p\,\frac{1 - x^{n-p+1}}{1 - x},} $$ et pour $x = 1$ la somme vaut $n - p + 1$.

Preuve

Le terme général d'une progression arithmétique. Pour $k \ge p$, $$ \begin{aligned} u_k &= u_p + \sum_{j=p}^{k-1} (u_{j+1} - u_j) && \text{(Proposition « Somme télescopique », lue à l'envers)} \\ &= u_p + \sum_{j=p}^{k-1} r && \text{($u_{j+1} - u_j = r$)} \\ &= u_p + (k - p)\,r, \end{aligned} $$ la dernière étape étant le nombre de termes.
Progression arithmétique : première démonstration, par symétrisation. Soit $S = \sum_{k=p}^{n} u_k$. $$ \begin{aligned} 2S &= \sum_{k=p}^{n} u_k + \sum_{k=p}^{n} u_{p+n-k} && \text{(réflexion sur la seconde copie de $S$)} \\ &= \sum_{k=p}^{n} \bigl( u_k + u_{p+n-k} \bigr) && \text{(linéarité)} \\ &= \sum_{k=p}^{n} \bigl( 2u_p + (n - p)\,r \bigr) && \text{($u_k = u_p + (k - p)\,r$ et $u_{p+n-k} = u_p + (n - k)\,r$)} \\ &= (n - p + 1)\,(u_p + u_n), \end{aligned} $$ la dernière étape étant le nombre de termes, et $2u_p + (n - p)\,r = u_p + u_n$ car $u_n = u_p + (n - p)\,r$. En divisant par $2$, on obtient la formule.
Seconde démonstration, par la somme des premiers entiers. $$ \begin{aligned} \sum_{k=p}^{n} u_k &= \sum_{k=p}^{n} \bigl( u_p + (k - p)\,r \bigr) && \text{($u_k = u_p + (k - p)\,r$)} \\ &= (n - p + 1)\,u_p + r \sum_{k=p}^{n} (k - p) && \text{(linéarité, nombre de termes)} \\ &= (n - p + 1)\,u_p + r \sum_{j=0}^{n-p} j && \text{(décalage $j = k - p$)} \\ &= (n - p + 1)\,u_p + r\,\frac{(n - p)(n - p + 1)}{2} && \text{(somme des premiers entiers, $n - p \in \mathbb{N}$)} \\ &= (n - p + 1)\,\frac{2u_p + (n - p)\,r}{2}, \end{aligned} $$ la dernière étape factorisant $n - p + 1$ ; et $2u_p + (n - p)\,r = u_p + u_n$.
Progression géométrique : première démonstration, par un décalage. Soit $x \ne 1$. $$ \begin{aligned} \sum_{k=p}^{n} x^k &= \sum_{j=0}^{n-p} x^{j+p} && \text{(décalage $j = k - p$)} \\ &= x^p \sum_{j=0}^{n-p} x^j && \text{(linéarité : $x^{j+p} = x^p x^j$)} \\ &= x^p\,\frac{1 - x^{n-p+1}}{1 - x}, \end{aligned} $$ la dernière étape étant la somme géométrique du Théorème « Sommes classiques », avec $n - p \in \mathbb{N}$. Pour $x = 1$, chaque terme vaut $1$ et il y en a $n - p + 1$.
Seconde démonstration, par télescopage. Soit $x \ne 1$. $$ \begin{aligned} (1 - x) \sum_{k=p}^{n} x^k &= \sum_{k=p}^{n} (x^k - x^{k+1}) && \text{(linéarité : distribution de $1 - x$)} \\ &= x^p - x^{n+1} && \text{(somme télescopique, $u_k = -x^k$)} \\ &= x^p \bigl( 1 - x^{n-p+1} \bigr), \end{aligned} $$ la dernière étape factorisant $x^p$, puisque $x^{n+1} = x^p x^{n-p+1}$. En divisant par $1 - x \ne 0$, on obtient la formule.

Proposition — Factorisation de $a^n - b^n$

Pour $a, b \in \mathbb{R}$ et $n \in \mathbb{N}^*$ : $$ \textcolor{colorprop}{\begin{aligned} a^n - b^n &= (a - b) \sum_{k=0}^{n-1} a^{n-1-k} b^k \\ &= (a - b)\bigl( a^{n-1} + a^{n-2} b + \dots + a b^{n-2} + b^{n-1} \bigr) \end{aligned}} $$

Preuve

Première démonstration, par télescopage. Posons $u_k = a^{n-k} b^k$ pour $0 \le k \le n$, de sorte que $u_0 = a^n$ et $u_n = b^n$. Comme $a \cdot a^{n-1-k} b^k = u_k$ et $b \cdot a^{n-1-k} b^k = u_{k+1}$, $$ \begin{aligned} (a - b) \sum_{k=0}^{n-1} a^{n-1-k} b^k &= \sum_{k=0}^{n-1} \bigl( a^{n-k} b^k - a^{n-1-k} b^{k+1} \bigr) && \text{(linéarité : distribution de $a - b$)} \\ &= \sum_{k=0}^{n-1} (u_k - u_{k+1}) && \text{(définition de $u_k$)} \\ &= u_0 - u_n && \text{(somme télescopique, pour $-u_k$)} \\ &= a^n - b^n, \end{aligned} $$ la dernière étape étant les valeurs de $u_0$ et de $u_n$.
Seconde démonstration, par la somme géométrique. Si $a = b$, les deux membres valent $0$. Si $b = 0$, la somme se réduit à son terme d'indice $0$, $a^{n-1}$, car $0^k = 0$ pour $k \ge 1$, et $a \cdot a^{n-1} = a^n$. Supposons $b \ne 0$ et $a \ne b$, et posons $x = \frac{a}{b} \ne 1$. $$ \begin{aligned} a^n - b^n &= b^n \bigl( x^n - 1 \bigr) && \text{($a = bx$)} \\ &= -b^n (1 - x) \sum_{k=0}^{n-1} x^k && \text{(somme géométrique : $1 - x^n = (1 - x) \sum_{k=0}^{n-1} x^k$)} \\ &= b^{n-1} (a - b) \sum_{k=0}^{n-1} x^k && \text{($-b (1 - x) = a - b$)} \\ &= (a - b) \sum_{k=0}^{n-1} a^k b^{n-1-k}, \end{aligned} $$ la dernière étape étant $b^{n-1} x^k = a^k b^{n-1-k}$. La réflexion $j = n - 1 - k$ transforme cette dernière somme en $\sum_{j=0}^{n-1} a^{n-1-j} b^j$.

Proposition — Puissances impaires

Pour $a, b \in \mathbb{R}$ et $p \in \mathbb{N}$ : $$ \textcolor{colorprop}{a^{2p+1} + b^{2p+1} = (a + b) \sum_{k=0}^{2p} (-1)^k a^{2p-k} b^k.} $$

Preuve

On applique la Proposition « Factorisation de $a^n - b^n$ » avec $n = 2p + 1$ et $-b$ à la place de $b$. $$ \begin{aligned} a^{2p+1} + b^{2p+1} &= a^{2p+1} - (-b)^{2p+1} && \text{(puissance impaire : $(-b)^{2p+1} = -b^{2p+1}$)} \\ &= \bigl( a - (-b) \bigr) \sum_{k=0}^{2p} a^{2p-k} (-b)^k && \text{(factorisation, $-b$ pour $b$)} \\ &= (a + b) \sum_{k=0}^{2p} (-1)^k a^{2p-k} b^k, \end{aligned} $$ la dernière étape étant $(-b)^k = (-1)^k b^k$.

Exemple — La somme des cent premiers entiers

Calculer $\sum_{k=1}^{100} k$.

Correction

$$ \begin{aligned} \sum_{k=1}^{100} k &= \sum_{k=0}^{100} k && \text{(le terme d'indice $0$ est $0$)} \\ &= \frac{100 \cdot 101}{2} && \text{(théorème « Sommes classiques », $n = 100$)} \\ &= 5050. \end{aligned} $$

Exemple — Une somme géométrique de puissances de deux

Calculer $\sum_{k=0}^{n} 2^k$.

Correction

$$ \begin{aligned} \sum_{k=0}^{n} 2^k &= \frac{1 - 2^{n+1}}{1 - 2} && \text{(somme géométrique, $x = 2 \ne 1$)} \\ &= 2^{n+1} - 1, \end{aligned} $$ la dernière étape car $1 - 2 = -1$. Vérification : pour $n = 3$, $1 + 2 + 4 + 8 = 15 = 2^4 - 1$.

Méthode — Calculer une somme de termes consécutifs d'une progression

Pour calculer $\sum_{k=p}^{n} u_k$ lorsque $(u_k)$ est une progression arithmétique ou géométrique :

Identifier le premier terme $u_p$, la raison $r$ ou $q$, et le nombre de termes, $n - p + 1$.
Progression arithmétique : le nombre de termes fois la moyenne du premier et du dernier terme, $(n - p + 1)\,\frac{u_p + u_n}{2}$.
Progression géométrique de raison $q \ne 1$, avec $u_k = u_p\,q^{k-p}$ : le premier terme fois $\frac{1 - q^{\text{nombre de termes}}}{1 - q}$, c'est-à-dire $u_p\,\frac{1 - q^{n-p+1}}{1 - q}$ ; le décalage $j = k - p$ et la somme géométrique la donnent. Pour $q = 1$ la progression est constante et la somme vaut $(n - p + 1)\,u_p$.

Le nombre de termes est $n - p + 1$ quel que soit le premier indice, et le cas $q = 1$ se traite à part.

Compétences à pratiquer

Reconnaître le premier terme, la raison et le nombre de termes d'une progression ★
Évaluer une somme arithmétique ou géométrique ★
Calculer une somme géométrique ★
Calculer une somme de termes consécutifs ★★
Factoriser une différence ou une somme de puissances ★★

II.3 Calculer une somme

Quelle méthode pour quelle somme

Calculer une somme, c'est la ramener à une forme close en $n$. Trois méthodes couvrent presque tous les cas, et le choix se lit sur le terme général. Lorsqu'il est polynomial en $k$, le développement et la linéarité le ramènent aux sommes classiques. Lorsque c'est une différence, ou lorsque l'on veut une somme de puissances, le télescopage fait le travail, sans avoir besoin du résultat d'avance. Lorsque la forme close est donnée, ou devinée sur les premières valeurs, la récurrence la démontre.

Signaler une erreur

Méthode — Calculer une somme à terme général polynomial

Pour calculer $\sum_{k=m}^{n} a_k$ lorsque $a_k$ est un polynôme en $k$, un produit de facteurs en $k$ en étant un :

Développer le terme général en une somme de puissances de $k$ à coefficients constants.
Séparer par linéarité en sommes $\sum k^j$ et une somme de constantes.
Remplacer chaque somme par sa valeur classique, jusqu'aux cubes : $\sum_{k=0}^{n} 1 = n + 1$, $\sum k$, $\sum k^2$, $\sum k^3$. Pour une somme qui commence à $k = 1$, le terme d'indice $0$ de $\sum k^j$ est nul dès que $j \ge 1$, mais une somme de constantes $\sum_{k=1}^{n} c$ a $n$ termes, non $n + 1$.
Factoriser le résultat, dont les facteurs communs sont d'ordinaire $n$ et $n + 1$, et le vérifier pour $n = 1$ et $n = 2$.

Compter les termes des constantes, et factoriser à la fin : une forme close laissée développée cache sa structure.

Exemple — Un terme général polynomial

Calculer $\sum_{k=1}^{n} k(k+1)$ pour $n \ge 1$.

Correction

Les termes d'indice $0$ de $\sum k$ et de $\sum k^2$ sont nuls, donc les sommes depuis $k = 1$ sont les sommes classiques. $$ \begin{aligned} \sum_{k=1}^{n} k(k+1) &= \sum_{k=1}^{n} (k^2 + k) && \text{(développement)} \\ &= \sum_{k=1}^{n} k^2 + \sum_{k=1}^{n} k && \text{(linéarité)} \\ &= \frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2} && \text{(sommes classiques)} \\ &= \frac{n(n+1)(2n+1) + 3n(n+1)}{6} && \text{(dénominateur commun $6$)} \\ &= \frac{n(n+1) \bigl( (2n+1) + 3 \bigr)}{6} && \text{(factorisation de $n(n+1)$)} \\ &= \frac{n(n+1)(2n+4)}{6} && \text{(addition)} \\ &= \frac{n(n+1)(n+2)}{3}, \end{aligned} $$ la dernière étape simplifiant $2n + 4 = 2(n+2)$ avec le dénominateur. Vérification : pour $n = 2$, $1 \cdot 2 + 2 \cdot 3 = 8$ et $\frac{2 \cdot 3 \cdot 4}{3} = 8$.

Méthode — Calculer une somme de puissances par télescopage

Pour calculer $\sum_{k=0}^{n} k^p$ pour $p = 1, 2, 3$ sans connaître le résultat, ou une somme dont le terme général est un produit de facteurs consécutifs :

Télescoper la puissance suivante. Développer $(k+1)^{p+1} - k^{p+1}$ avec les identités remarquables : c'est $2k+1$, $3k^2+3k+1$ ou $4k^3+6k^2+4k+1$, un polynôme de degré $p$ en $k$ de terme dominant $(p+1)\,k^p$. La somme télescopique donne $\sum_{k=0}^{n} \bigl( (k+1)^{p+1} - k^{p+1} \bigr) = (n+1)^{p+1}$, et la linéarité isole $\sum k^p$ des sommes des puissances inférieures, déjà connues.
Télescoper un produit de facteurs consécutifs avec un facteur de plus : la différence $u_k - u_{k-1}$ de $u_k = k(k+1)(k+2)(k+3)$ est $4k(k+1)(k+2)$, car les trois facteurs communs sortent.

Il n'est pas nécessaire de connaître le résultat d'avance : le télescopage le trouve.

Exemple — Un produit de trois entiers consécutifs

Calculer $\sum_{k=1}^{n} k(k+1)(k+2)$ pour $n \ge 1$, en télescopant $u_k = k(k+1)(k+2)(k+3)$.

Correction

Pour $k \ge 1$, les trois facteurs communs sortent de la différence : $$ \begin{aligned} u_k - u_{k-1} &= k(k+1)(k+2)(k+3) - (k-1)\,k(k+1)(k+2) && \text{(définition de $u_k$ et $u_{k-1}$)} \\ &= k(k+1)(k+2) \bigl( (k+3) - (k-1) \bigr) && \text{(factorisation des trois facteurs communs)} \\ &= 4k(k+1)(k+2). \end{aligned} $$ Donc $$ \begin{aligned} 4 \sum_{k=1}^{n} k(k+1)(k+2) &= \sum_{k=1}^{n} (u_k - u_{k-1}) && \text{(différence $u_k - u_{k-1}$, linéarité)} \\ &= \sum_{j=0}^{n-1} (u_{j+1} - u_j) && \text{(décalage $j = k - 1$)} \\ &= u_n - u_0 && \text{(somme télescopique)} \\ &= n(n+1)(n+2)(n+3), \end{aligned} $$ la dernière étape car $u_n = n(n+1)(n+2)(n+3)$ et $u_0 = 0$. En divisant par $4$, on obtient $\sum_{k=1}^{n} k(k+1)(k+2) = \frac{n(n+1)(n+2)(n+3)}{4}$. Vérification : pour $n = 2$, $1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 = 30$ et $\frac{2 \cdot 3 \cdot 4 \cdot 5}{4} = 30$.

Méthode — Démontrer une forme close par récurrence

Pour démontrer que $\sum_{k=m}^{n} a_k = F(n)$ pour tout $n \ge m$, lorsque la forme close $F(n)$ est donnée ou devinée sur les premières valeurs :

Énoncer $P_n$ pour un $n$ donné : « $\sum_{k=m}^{n} a_k = F(n)$ », comme dans la Méthode « Rédiger une récurrence simple ».
Initialisation : calculer les deux membres en $n = m$, ou en $n = m - 1$, où la somme est vide et où $F(m-1)$ doit valoir $0$.
Hérédité : écrire $\sum_{k=m}^{n+1} a_k = \sum_{k=m}^{n} a_k + a_{n+1}$, remplacer la somme par $F(n)$ grâce à l'hypothèse de récurrence, puis montrer que $F(n) + a_{n+1} = F(n+1)$ en calculant les deux membres à part et en les comparant. Le pas est l'identité $F(n+1) - F(n) = a_{n+1}$.

Une récurrence démontre une forme close donnée, elle n'en trouve pas : les sommes classiques et le télescopage la trouvent.

Exemple — Une somme alternée démontrée par récurrence

Montrer que $\sum_{k=0}^{n} (-1)^k (2k+1) = (-1)^n (n+1)$ pour tout $n \in \mathbb{N}$.

Correction

Pour $n \in \mathbb{N}$, notons $P_n$ la propriété « $\sum_{k=0}^{n} (-1)^k (2k+1) = (-1)^n (n+1)$ ».
Initialisation. Pour $n = 0$, le premier membre est $(-1)^0 (2 \cdot 0 + 1) = 1$ et le second membre est $(-1)^0 (0 + 1) = 1$ : $P_0$ est vraie.
Hérédité. Soit $n \in \mathbb{N}$ et supposons $P_n$. $$ \begin{aligned} \sum_{k=0}^{n+1} (-1)^k (2k+1) &= \sum_{k=0}^{n} (-1)^k (2k+1) + (-1)^{n+1} (2n+3) && \text{(définition de $\sum$)} \\ &= (-1)^n (n+1) + (-1)^{n+1} (2n+3) && \text{(hypothèse de récurrence)} \\ &= (-1)^{n+1} \bigl( -(n+1) + (2n+3) \bigr) && \text{(factorisation de $(-1)^{n+1}$, car $(-1)^n = -(-1)^{n+1}$)} \\ &= (-1)^{n+1} (n+2), \end{aligned} $$ la dernière étape étant $-(n+1) + (2n+3) = n + 2$. C'est $P_{n+1}$, car $(n+1) + 1 = n + 2$.
Conclusion. Puisque $P_0$ est vraie et que $P_n \Rightarrow P_{n+1}$ pour tout $n \in \mathbb{N}$, par récurrence, $P_n$ est vraie pour tout $n \in \mathbb{N}$.
Seconde démonstration, par télescopage. Posons $u_k = (-1)^k k$. Alors $u_k - u_{k+1} = (-1)^k k + (-1)^k (k+1) = (-1)^k (2k+1)$, car $-(-1)^{k+1} = (-1)^k$. Donc $$ \begin{aligned} \sum_{k=0}^{n} (-1)^k (2k+1) &= \sum_{k=0}^{n} (u_k - u_{k+1}) && \text{(la différence ci-dessus)} \\ &= u_0 - u_{n+1} && \text{(somme télescopique, pour $-u_k$)} \\ &= (-1)^n (n+1), \end{aligned} $$ la dernière étape car $u_0 = 0$ et $-u_{n+1} = -(-1)^{n+1} (n+1) = (-1)^n (n+1)$. La récurrence vérifie une forme close donnée ; le télescopage la trouve, une fois la suite $u_k$ aperçue.

Compétences à pratiquer

Choisir la technique pour calculer une somme ★
Évaluer une somme de carrés ou de cubes ★
Calculer une somme à terme polynomial ★★
Démontrer une formule par récurrence ★★
Sommer un polynôme fois une progression géométrique ★★★
Trouver la forme close d'une somme ★★★

III Sommes doubles

Deux indices à la fois

Beaucoup de sommes portent sur des couples d'indices : les cases d'un tableau, les produits $a_i b_j$ de deux listes, les couples $i < j$ d'une famille ordonnée. Une somme double se calcule en choisissant un ordre, ligne par ligne ou colonne par colonne, et en employant les outils des sommes simples dans chaque ligne ou chaque colonne. Quatre faits gouvernent le calcul : l'ordre de sommation ne change pas le total, la somme double d'un produit $a_i b_j$ est le produit de deux sommes, une somme sur un triangle se calcule dans l'un ou l'autre ordre à condition de réécrire les bornes, et les mêmes énoncés valent pour les produits.

Signaler une erreur

III.1 Sommes sur un rectangle

Additionner un tableau par lignes et par colonnes

Les cases $a_{i,j}$ d'un tableau de lignes $i$ et de colonnes $j$ peuvent être additionnées de deux façons : ligne par ligne, en additionnant d'abord chaque ligne puis les totaux de lignes, ou colonne par colonne. La figure montre un tableau de trois lignes et quatre colonnes avec ses totaux. Les deux façons aboutissent au même total général, ce qui est le premier fait à démontrer. Lorsque la case est un produit $a_i b_j$, le tableau est la table de multiplication de deux listes, et son total général se factorise.

La ligne $i$ s'additionne en $\sum_{j=1}^{4} a_{i,j}$ et la colonne $j$ en $\sum_{i=1}^{3} a_{i,j}$ ; le total général du coin est à la fois la somme des totaux de lignes et la somme des totaux de colonnes.

Signaler une erreur

Définition — Somme double

Soient $I$ et $J$ deux ensembles finis et $(a_{i,j})_{(i,j) \in I \times J}$ une famille de réels indexée par le produit cartésien $I \times J$, qui est un ensemble fini. La somme double de la famille est sa somme sur $I \times J$, au sens de la Définition « Somme sur un ensemble fini » : $$ \textcolor{colordef}{\sum_{(i,j) \in I \times J} a_{i,j}}, $$ aussi notée $\sum_{i \in I,\, j \in J} a_{i,j}$ ; pour $I = \llbracket m, n \rrbracket$ et $J = \llbracket p, q \rrbracket$ elle s'écrit aussi $\sum_{m \le i \le n,\ p \le j \le q} a_{i,j}$, et pour $I = J = \llbracket 1, n \rrbracket$ elle s'écrit $\sum_{1 \le i, j \le n} a_{i,j}$. Elle vaut $0$ lorsque $I$ ou $J$ est vide.
Les sommes itérées sont $\sum_{i \in I} \sum_{j \in J} a_{i,j} = \sum_{i \in I} \bigl( \sum_{j \in J} a_{i,j} \bigr)$ et $\sum_{j \in J} \sum_{i \in I} a_{i,j} = \sum_{j \in J} \bigl( \sum_{i \in I} a_{i,j} \bigr)$. Dans la première, la somme intérieure $\sum_{j \in J} a_{i,j}$ est le total de la ligne $i$ et la somme extérieure additionne les totaux de lignes ; dans la seconde, la somme intérieure est le total de la colonne $j$.

Proposition — Permuter l'ordre de sommation

Soient $I$ et $J$ deux ensembles finis et $(a_{i,j})_{(i,j) \in I \times J}$ une famille de réels. Alors $$ \textcolor{colorprop}{\sum_{(i,j) \in I \times J} a_{i,j} = \sum_{i \in I} \Bigl( \sum_{j \in J} a_{i,j} \Bigr) = \sum_{j \in J} \Bigl( \sum_{i \in I} a_{i,j} \Bigr).} $$ En particulier, pour des bornes entières, $\sum_{i=m}^{n} \sum_{j=p}^{q} a_{i,j} = \sum_{j=p}^{q} \sum_{i=m}^{n} a_{i,j}$ : on peut échanger l'ordre de deux sommations sur un rectangle.
Le rectangle est essentiel. Les bornes de $j$ ne doivent pas dépendre de $i$, ni celles de $i$ de $j$ ; sinon l'ensemble des couples est un triangle ou une autre région, et échanger les deux sommations change les bornes.

Preuve

Première démonstration, par la sommation par paquets. Soit $i_1, \dots, i_r$ une énumération de $I$. Les lignes $\{i_1\} \times J, \dots, \{i_r\} \times J$ forment un recouvrement disjoint de $I \times J$ : un couple $(i, j)$ est dans la ligne de sa première composante $i$ et dans aucune autre, puisque deux lignes d'indices distincts ont des premières composantes distinctes, donc aucun couple en commun. D'après la Proposition « Sommation par paquets », $$ \sum_{(i,j) \in I \times J} a_{i,j} = \sum_{k=1}^{r} \ \sum_{(i,j) \in \{i_k\} \times J} a_{i,j}. $$ Pour chaque $k$, l'application $j \mapsto (i_k, j)$ est une bijection de $J$ sur $\{i_k\} \times J$, de réciproque $(i_k, j) \mapsto j$. D'après la Proposition « Changement d'indice par une bijection », $$ \sum_{(i,j) \in \{i_k\} \times J} a_{i,j} = \sum_{j \in J} a_{i_k, j}. $$ Donc la somme double est $\sum_{k=1}^{r} \sum_{j \in J} a_{i_k, j}$, qui est $\sum_{i \in I} \bigl( \sum_{j \in J} a_{i,j} \bigr)$ par la Définition « Somme sur un ensemble fini », les totaux de lignes étant listés dans l'énumération $i_1, \dots, i_r$. En échangeant les rôles de $i$ et de $j$, avec les colonnes $I \times \{j\}$ à la place des lignes, on obtient la seconde égalité.
Seconde démonstration de l'échange des sommes itérées, par récurrence sur le nombre de lignes. Si $I$ est vide, les deux sommes itérées valent $0$. Sinon soit $i_1, \dots, i_r$ une énumération de $I$, avec $r \ge 1$, et $b_{k,j} = a_{i_k, j}$. Par la Définition « Somme sur un ensemble fini », appliquée à $I$ et, pour chaque $j$, à la somme sur $I$ des termes $a_{i,j}$, les deux sommes itérées sont $\sum_{k=1}^{r} \sum_{j \in J} b_{k,j}$ et $\sum_{j \in J} \sum_{k=1}^{r} b_{k,j}$. Pour $1 \le s \le r$ notons $P_s$ la propriété « $\sum_{k=1}^{s} \sum_{j \in J} b_{k,j} = \sum_{j \in J} \sum_{k=1}^{s} b_{k,j}$ ». Pour $s = 1$ chaque somme $\sum_{k=1}^{1} b_{k,j}$ a l'unique terme $b_{1,j}$, donc les deux membres de $P_1$ valent $\sum_{j \in J} b_{1,j}$ : $P_1$ est vraie. Soit $1 \le s < r$ et supposons $P_s$. Alors $$ \begin{aligned} \sum_{k=1}^{s+1} \sum_{j \in J} b_{k,j} &= \sum_{k=1}^{s} \sum_{j \in J} b_{k,j} + \sum_{j \in J} b_{s+1,j} && \text{(définition de $\sum$)} \\ &= \sum_{j \in J} \sum_{k=1}^{s} b_{k,j} + \sum_{j \in J} b_{s+1,j} && \text{(hypothèse de récurrence)} \\ &= \sum_{j \in J} \Bigl( \sum_{k=1}^{s} b_{k,j} + b_{s+1,j} \Bigr) && \text{(linéarité de $\sum$)} \\ &= \sum_{j \in J} \sum_{k=1}^{s+1} b_{k,j}, \end{aligned} $$ la dernière étape par la définition de $\sum$. C'est $P_{s+1}$. Puisque $P_1$ est vraie et que $P_s \Rightarrow P_{s+1}$ pour $1 \le s < r$, par récurrence $P_r$ est vraie : les deux sommes itérées sont égales.

Proposition — Produit de deux sommes

Soient $I$ et $J$ deux ensembles finis, et $(a_i)_{i \in I}$ et $(b_j)_{j \in J}$ deux familles de réels. Alors $$ \textcolor{colorprop}{\Bigl( \sum_{i \in I} a_i \Bigr) \Bigl( \sum_{j \in J} b_j \Bigr) = \sum_{(i,j) \in I \times J} a_i b_j.} $$ Une somme double dont le terme est un produit d'un facteur en $i$ seul et d'un facteur en $j$ seul est le produit de deux sommes simples. En particulier $\bigl( \sum_{i \in I} a_i \bigr)^2 = \sum_{(i,j) \in I \times I} a_i a_j$.

Preuve

Première démonstration, par linéarité. Dans la somme sur $i$, le facteur $\sum_{j \in J} b_j$ ne dépend pas de $i$ : c'est une constante. Puis, dans la somme sur $j$, le facteur $a_i$ ne dépend pas de $j$. Donc $$ \begin{aligned} \Bigl( \sum_{i \in I} a_i \Bigr) \Bigl( \sum_{j \in J} b_j \Bigr) &= \sum_{i \in I} a_i \Bigl( \sum_{j \in J} b_j \Bigr) && \text{(linéarité de $\sum$, la constante $\sum_{j} b_j$)} \\ &= \sum_{i \in I} \sum_{j \in J} a_i b_j && \text{(linéarité de $\sum$, la constante $a_i$)} \\ &= \sum_{(i,j) \in I \times J} a_i b_j. \end{aligned} $$ La dernière étape est la Proposition « Permuter l'ordre de sommation », première égalité.
Seconde démonstration, par la distributivité écrite en développé. Soit $i_1, \dots, i_r$ une énumération de $I$ et $j_1, \dots, j_s$ une de $J$. Par distributivité, $(a_{i_1} + \dots + a_{i_r})(b_{j_1} + \dots + b_{j_s})$ est la somme des $rs$ produits $a_{i_k} b_{j_l}$, un pour chaque choix d'un terme dans le premier facteur et d'un terme dans le second ; chaque couple $(i, j) \in I \times J$ figure exactement une fois parmi ces choix. Cette somme est $\sum_{(i,j) \in I \times J} a_i b_j$, puisqu'une somme finie ne dépend ni de l'ordre ni du parenthésage de ses termes.

Exemple — Un terme séparable

Calculer $\displaystyle \sum_{i=1}^{n} \sum_{j=1}^{n} ij$ pour $n \ge 1$.

Correction

Le terme $ij$ est un produit d'un facteur en $i$ seul et d'un facteur en $j$ seul, donc la somme double se factorise : $$ \begin{aligned} \sum_{i=1}^{n} \sum_{j=1}^{n} ij &= \Bigl( \sum_{i=1}^{n} i \Bigr) \Bigl( \sum_{j=1}^{n} j \Bigr) && \text{(produit de deux sommes)} \\ &= \Bigl( \frac{n(n+1)}{2} \Bigr)^2, \end{aligned} $$ la dernière étape par le Théorème « Sommes classiques » pour chacune des deux sommes.

Exemple — Un terme qui n'est pas un produit

Calculer $\displaystyle \sum_{1 \le i, j \le n} (2i + 3j)$ pour $n \ge 1$.

Correction

Le terme $2i + 3j$ est une somme, non un produit : on traite les deux parties à part, chacune sommée sur tout le carré. $$ \begin{aligned} \sum_{1 \le i, j \le n} (2i + 3j) &= 2 \sum_{1 \le i, j \le n} i + 3 \sum_{1 \le i, j \le n} j && \text{(linéarité de $\sum$)} \\ &= 2 \sum_{i=1}^{n} \sum_{j=1}^{n} i + 3 \sum_{j=1}^{n} \sum_{i=1}^{n} j && \text{(permuter l'ordre de sommation)} \\ &= 2 \sum_{i=1}^{n} n i + 3 \sum_{j=1}^{n} n j && \text{(nombre de termes : les sommes intérieures ont $n$ termes égaux)} \\ &= 2n \sum_{i=1}^{n} i + 3n \sum_{j=1}^{n} j && \text{(linéarité de $\sum$)} \\ &= 5n \sum_{k=1}^{n} k && \text{(l'indice est muet)} \\ &= 5n \cdot \frac{n(n+1)}{2} && \text{(sommes classiques)} \\ &= \frac{5n^2(n+1)}{2}. \end{aligned} $$ Vérification pour $n = 1$ : l'unique couple est $(1,1)$ et $2 + 3 = 5 = \frac{5 \cdot 1 \cdot 2}{2}$.

Compétences à pratiquer

Évaluer une somme double sur un rectangle ★
Calculer une somme double par lignes et par colonnes ★
Factoriser ou couper une somme double ★★

III.2 Triangles et autres domaines

Quand les bornes d'un indice dépendent de l'autre

Dans une somme double, les couples $(i, j)$ ne remplissent pas toujours un rectangle. Dans $\sum_{i=1}^{n} \sum_{j=i}^{n}$ l'indice intérieur commence à l'indice extérieur, et les couples gardés sont ceux tels que $i \le j$ : le tableau est coupé le long de sa diagonale et la moitié en reste, un triangle. La figure montre les couples $(i, j)$ tels que $1 \le i \le j \le 5$, balayés ligne par ligne à gauche et colonne par colonne à droite ; les deux balayages visitent les mêmes couples, mais les bornes qui les décrivent sont différentes.

Signaler une erreur

Définition — Sommes triangulaires

Soit $n \ge 1$. Une somme triangulaire est une somme double sur une partie de $\llbracket 1, n \rrbracket^2$ définie par une inégalité entre les deux indices :

sur le triangle large $\{(i, j) \in \llbracket 1, n \rrbracket^2 \mid i \le j\}$, diagonale comprise, c'est $\textcolor{colordef}{\sum_{1 \le i \le j \le n} a_{i,j}}$ ;
sur le triangle strict $\{(i, j) \in \llbracket 1, n \rrbracket^2 \mid i < j\}$, diagonale exclue, c'est $\textcolor{colordef}{\sum_{1 \le i < j \le n} a_{i,j}}$.

La somme sur tout le carré $\llbracket 1, n \rrbracket^2$ s'écrit $\sum_{1 \le i, j \le n} a_{i,j}$. Ces ensembles sont finis, donc chaque somme est une somme sur un ensemble fini au sens de la Définition « Somme sur un ensemble fini » ; pour $n = 1$ le triangle strict est vide et sa somme vaut $0$.

Proposition — Permuter l'ordre sur un triangle

Soient $n \ge 1$ et $(a_{i,j})$ des réels indexés par les couples $(i, j)$ de $\llbracket 1, n \rrbracket^2$. Alors $$ \textcolor{colorprop}{\sum_{1 \le i \le j \le n} a_{i,j} = \sum_{i=1}^{n} \sum_{j=i}^{n} a_{i,j} = \sum_{j=1}^{n} \sum_{i=1}^{j} a_{i,j},} $$ et $$ \textcolor{colorprop}{\sum_{1 \le i < j \le n} a_{i,j} = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} a_{i,j} = \sum_{j=2}^{n} \sum_{i=1}^{j-1} a_{i,j}.} $$ Dans une somme itérée sur un triangle, les bornes de l'indice intérieur dépendent de l'indice extérieur, et les bornes extérieures sont constantes : échanger les deux sommations n'est pas échanger les deux symboles $\sum$, les bornes se recalculent à partir de l'inégalité entre les indices.

Preuve

Première démonstration, par prolongement par zéro. Le triangle large, par lignes. Notons $\tilde a_{i,j} = a_{i,j}$ si $i \le j$ et $\tilde a_{i,j} = 0$ sinon, pour $(i, j) \in \llbracket 1, n \rrbracket^2$. Le carré $\llbracket 1, n \rrbracket^2$ est la réunion disjointe du triangle et de son complémentaire, et $\tilde a$ est nul sur le complémentaire. Alors $$ \begin{aligned} \sum_{1 \le i \le j \le n} a_{i,j} &= \sum_{1 \le i, j \le n} \tilde a_{i,j} && \text{(sommation par paquets : le complémentaire porte des zéros)} \\ &= \sum_{i=1}^{n} \sum_{j=1}^{n} \tilde a_{i,j} && \text{(permuter l'ordre de sommation, première égalité)} \\ &= \sum_{i=1}^{n} \Bigl( \sum_{j=1}^{i-1} 0 + \sum_{j=i}^{n} a_{i,j} \Bigr) && \text{(relation de Chasles en $p = i - 1$, définition de $\tilde a$)} \\ &= \sum_{i=1}^{n} \sum_{j=i}^{n} a_{i,j}, \end{aligned} $$ la dernière étape car une somme de zéros est nulle, d'après la Proposition « Nombre de termes » avec $c = 0$.
Par colonnes. La seconde égalité de la Proposition « Permuter l'ordre de sommation » donne $\sum_{1 \le i, j \le n} \tilde a_{i,j} = \sum_{j=1}^{n} \sum_{i=1}^{n} \tilde a_{i,j}$, et, pour tout $j$, $$ \begin{aligned} \sum_{i=1}^{n} \tilde a_{i,j} &= \sum_{i=1}^{j} a_{i,j} + \sum_{i=j+1}^{n} 0 && \text{(relation de Chasles en $p = j$, définition de $\tilde a$)} \\ &= \sum_{i=1}^{j} a_{i,j}, \end{aligned} $$ la dernière étape car une somme de zéros est nulle : donc $\sum_{1 \le i \le j \le n} a_{i,j} = \sum_{j=1}^{n} \sum_{i=1}^{j} a_{i,j}$.
Le triangle strict se traite de la même façon avec $\tilde a_{i,j} = a_{i,j}$ si $i < j$ et $0$ sinon. La relation de Chasles en $p = i$, respectivement en $p = j - 1$, donne les sommes intérieures $\sum_{j=i+1}^{n} a_{i,j}$ et $\sum_{i=1}^{j-1} a_{i,j}$ ; le terme $i = n$ de la première somme itérée et le terme $j = 1$ de la seconde sont des sommes vides, égales à $0$, donc les sommes extérieures vont de $1$ à $n - 1$ et de $2$ à $n$. Pour $n = 1$ le triangle est vide et toutes les sommes valent $0$.
Seconde démonstration, par la sommation par paquets. Le triangle large, par lignes. Pour $i \in \llbracket 1, n \rrbracket$, la ligne $\{i\} \times \llbracket i, n \rrbracket$ contient les couples du triangle de première composante $i$. Les $n$ lignes forment un recouvrement disjoint du triangle, puisqu'un couple $(i, j)$ est dans la ligne de sa première composante seulement. D'après la Proposition « Sommation par paquets », et par la bijection $j \mapsto (i, j)$ de $\llbracket i, n \rrbracket$ sur la ligne $i$ (Proposition « Changement d'indice par une bijection »), $$ \begin{aligned} \sum_{1 \le i \le j \le n} a_{i,j} &= \sum_{i=1}^{n} \sum_{(p,q) \in \{i\} \times \llbracket i, n \rrbracket} a_{p,q} && \text{(sommation par paquets, les lignes étant les paquets)} \\ &= \sum_{i=1}^{n} \sum_{j=i}^{n} a_{i,j}. \end{aligned} $$ Par colonnes. Pour $j \in \llbracket 1, n \rrbracket$, la colonne $\llbracket 1, j \rrbracket \times \{j\}$ contient les couples du triangle de seconde composante $j$ ; les $n$ colonnes forment un recouvrement disjoint, et la bijection $i \mapsto (i, j)$ de $\llbracket 1, j \rrbracket$ sur la colonne $j$ donne de la même façon $\sum_{1 \le i \le j \le n} a_{i,j} = \sum_{j=1}^{n} \sum_{i=1}^{j} a_{i,j}$.
Le triangle strict se traite de la même façon, avec les lignes $\{i\} \times \llbracket i+1, n \rrbracket$ pour $i \in \llbracket 1, n-1 \rrbracket$ et les colonnes $\llbracket 1, j-1 \rrbracket \times \{j\}$ pour $j \in \llbracket 2, n \rrbracket$ ; pour $n = 1$ le triangle est vide et toutes les sommes valent $0$.

Proposition — Carré d'une somme

Soient $n \ge 1$ et $x_1, \dots, x_n$ des réels. Alors $$ \textcolor{colorprop}{\begin{aligned} \Bigl( \sum_{k=1}^{n} x_k \Bigr)^2 &= \sum_{k=1}^{n} x_k^2 + 2 \sum_{1 \le i < j \le n} x_i x_j \\ (x_1 + \dots + x_n)^2 &= x_1^2 + \dots + x_n^2 + 2 \bigl( x_1 x_2 + x_1 x_3 + \dots + x_{n-1} x_n \bigr) \end{aligned}} $$ Pour $n = 2$ c'est l'identité remarquable $(x_1 + x_2)^2 = x_1^2 + x_2^2 + 2 x_1 x_2$, et pour $n = 3$ elle donne $(x_1 + x_2 + x_3)^2 = x_1^2 + x_2^2 + x_3^2 + 2(x_1 x_2 + x_1 x_3 + x_2 x_3)$ : le carré d'une somme est la somme des carrés plus le double de la somme des produits de deux termes distincts.

Preuve

Première démonstration, par les trois zones du carré. D'après la Proposition « Produit de deux sommes », avec $a_i = b_i = x_i$, $$ \Bigl( \sum_{k=1}^{n} x_k \Bigr)^2 = \sum_{1 \le i, j \le n} x_i x_j. $$ Le carré $\llbracket 1, n \rrbracket^2$ est la réunion disjointe de trois zones : la diagonale $D = \{(i, i) \mid 1 \le i \le n\}$, le triangle supérieur strict $T = \{(i, j) \mid i < j\}$ et le triangle inférieur strict $L = \{(i, j) \mid i > j\}$, puisqu'un couple $(i, j)$ vérifie exactement une des relations $i = j$, $i < j$, $i > j$. D'après la Proposition « Sommation par paquets », $$ \sum_{1 \le i, j \le n} x_i x_j = \sum_{(i,j) \in D} x_i x_j + \sum_{(i,j) \in T} x_i x_j + \sum_{(i,j) \in L} x_i x_j. $$ L'application $i \mapsto (i, i)$ est une bijection de $\llbracket 1, n \rrbracket$ sur $D$, donc d'après la Proposition « Changement d'indice par une bijection » la première somme est $\sum_{i=1}^{n} x_i^2$. L'application $(i, j) \mapsto (j, i)$ est une bijection de $T$ sur $L$, puisque $i < j$ signifie $j > i$, et $x_j x_i = x_i x_j$ : la même Proposition donne $\sum_{(p,q) \in L} x_p x_q = \sum_{(i,j) \in T} x_j x_i = \sum_{(i,j) \in T} x_i x_j$. Les trois zones donnent $\sum_{k=1}^{n} x_k^2 + 2 \sum_{1 \le i < j \le n} x_i x_j$.
Seconde démonstration, par récurrence sur $n$. Notons $s_n = \sum_{k=1}^{n} x_k$, $q_n = \sum_{k=1}^{n} x_k^2$ et $p_n = \sum_{1 \le i < j \le n} x_i x_j$ ; l'énoncé est $P_n$ : $s_n^2 = q_n + 2 p_n$. Pour $n = 1$, $s_1^2 = x_1^2 = q_1$ et $p_1 = 0$ (triangle vide) : $P_1$ est vraie. Pour tout $n \ge 1$ la définition de $\sum$ donne $s_{n+1} = s_n + x_{n+1}$ et $q_{n+1} = q_n + x_{n+1}^2$, et, d'après la Proposition « Permuter l'ordre sur un triangle » et la définition de $\sum$ sur la borne supérieure, $$ \begin{aligned} p_{n+1} &= \sum_{j=2}^{n+1} \sum_{i=1}^{j-1} x_i x_j && \text{(Proposition « Permuter l'ordre sur un triangle »)} \\ &= \sum_{j=2}^{n} \sum_{i=1}^{j-1} x_i x_j + \sum_{i=1}^{n} x_i x_{n+1} && \text{(définition de $\sum$ sur la borne supérieure $j = n + 1$)} \\ &= p_n + x_{n+1} s_n, \end{aligned} $$ la dernière étape car $\sum_{j=2}^{n} \sum_{i=1}^{j-1} x_i x_j = p_n$ d'après la même Proposition, et $x_{n+1}$ sort de la somme sur $i$. Supposons $P_n$. Alors $$ \begin{aligned} s_{n+1}^2 &= (s_n + x_{n+1})^2 && \text{(définition de $s_{n+1}$)} \\ &= s_n^2 + 2 x_{n+1} s_n + x_{n+1}^2 && \text{(identité remarquable)} \\ &= q_n + 2 p_n + 2 x_{n+1} s_n + x_{n+1}^2 && \text{(hypothèse de récurrence $P_n$)} \\ &= \bigl( q_n + x_{n+1}^2 \bigr) + 2 \bigl( p_n + x_{n+1} s_n \bigr) && \text{(regroupement)} \\ &= q_{n+1} + 2 p_{n+1}. \end{aligned} $$ C'est $P_{n+1}$. Par récurrence, $P_n$ est vraie pour tout $n \ge 1$.

Piège — seules les bornes intérieures dépendent de l'autre indice

Dans une somme itérée, les bornes de la somme intérieure peuvent dépendre de l'indice extérieur ; les bornes de la somme extérieure ne dépendent jamais de l'indice intérieur. Dans $\sum_{i=1}^{n} \sum_{j=i}^{n} a_{i,j}$ la somme intérieure commence à $i$, qui est l'indice extérieur : c'est permis. L'expression $\sum_{j=i}^{n} \sum_{i=1}^{n} a_{i,j}$ n'a pas de sens, puisque $i$ figure dans une borne avant d'être introduit. Donc échanger l'ordre sur un triangle n'est jamais échanger les deux symboles $\sum$ : on écrit la condition sur le couple, $1 \le i \le j \le n$, et l'on en récrit les bornes, ce qui donne $\sum_{j=1}^{n} \sum_{i=1}^{j} a_{i,j}$.
Un triangle n'est pas un rectangle. Pour $n = 2$, $\sum_{i=1}^{2} \sum_{j=i}^{2} 1 = 3$, les trois couples $(1,1)$, $(1,2)$, $(2,2)$, alors que $\sum_{i=1}^{2} \sum_{j=1}^{2} 1 = 4$.

Signaler une erreur

Exemple — Le nombre de couples d'un triangle

Calculer $\displaystyle \sum_{1 \le i \le j \le n} 1$ pour $n \ge 1$.

Correction

On ordonne la somme avec $j$ à l'extérieur : les bornes de $i$ sont alors visibles, de $1$ à $j$. $$ \begin{aligned} \sum_{1 \le i \le j \le n} 1 &= \sum_{j=1}^{n} \sum_{i=1}^{j} 1 && \text{(permuter l'ordre sur un triangle)} \\ &= \sum_{j=1}^{n} j && \text{(nombre de termes : la somme intérieure a $j$ termes égaux à $1$)} \\ &= \frac{n(n+1)}{2}, \end{aligned} $$ la dernière étape par le Théorème « Sommes classiques ». Vérification avec l'autre ordre : $\sum_{i=1}^{n} \sum_{j=i}^{n} 1 = \sum_{i=1}^{n} (n - i + 1)$ d'après la Proposition « Nombre de termes », et la réflexion $k = n - i + 1$ transforme cette somme en $\sum_{k=1}^{n} k$, la même valeur. Vérification pour $n = 3$ : les couples sont $(1,1)$, $(1,2)$, $(1,3)$, $(2,2)$, $(2,3)$, $(3,3)$, soit $6 = \frac{3 \cdot 4}{2}$.

Méthode — Calculer une somme double

Pour calculer une somme double, regarder l'ensemble des couples et le terme, et choisir parmi ces réflexes :

Terme séparable : si $a_{i,j} = b_i c_j$, la somme double sur un rectangle est le produit de deux sommes simples, $\bigl( \sum_i b_i \bigr) \bigl( \sum_j c_j \bigr)$ (Produit de deux sommes).
Rectangle : les deux ordres donnent le même total (Permuter l'ordre de sommation) ; sommer d'abord sur l'indice qui laisse une somme simple connue, une somme classique ou une somme géométrique, et traiter l'autre indice comme une constante.
Triangle : dessiner les couples, écrire l'inégalité entre les indices, et choisir l'ordre dont la somme intérieure est connue ; les bornes intérieures dépendent de l'indice extérieur (Permuter l'ordre sur un triangle).
Terme constant sur les droites $i + j = s$ : les couples tels que $i + j = s$ forment une seule somme par le changement d'indice $j = s - i$ (Changement d'indice par une bijection) ; regrouper les couples selon la valeur de $s$ (Sommation par paquets).
Terme symétrique, $a_{i,j} = a_{j,i}$ : couper le carré en $i < j$, $i = j$ et $i > j$ ; les zones $i < j$ et $i > j$ ont la même somme, comme dans la Proposition « Carré d'une somme ».
Bloqué : échanger l'ordre et réessayer ; la forme échangée montre souvent un terme séparable ou une somme intérieure connue.

Toujours vérifier les bornes sur un petit cas, comme $n = 2$ ou $n = 3$, en écrivant les couples.

Exemple — Une somme sur le triangle strict

Calculer $\displaystyle \sum_{1 \le i < j \le n} ij$ pour $n \ge 1$.

Correction

La Proposition « Carré d'une somme » avec $x_k = k$ relie la somme sur le triangle strict aux sommes $\sum k$ et $\sum k^2$. $$ \begin{aligned} \sum_{1 \le i < j \le n} ij &= \frac{1}{2} \Bigl( \Bigl( \sum_{k=1}^{n} k \Bigr)^2 - \sum_{k=1}^{n} k^2 \Bigr) && \text{(carré d'une somme avec $x_k = k$)} \\ &= \frac{1}{2} \Bigl( \frac{n^2 (n+1)^2}{4} - \frac{n(n+1)(2n+1)}{6} \Bigr) && \text{(sommes classiques)} \\ &= \frac{n(n+1)}{2} \cdot \frac{3n(n+1) - 2(2n+1)}{12} && \text{(factorisation de $\frac{n(n+1)}{2}$, dénominateur commun $12$)} \\ &= \frac{n(n+1)(3n^2 - n - 2)}{24} && \text{(développement)} \\ &= \frac{(n-1) n (n+1)(3n+2)}{24}, \end{aligned} $$ la dernière étape parce que $3n^2 - n - 2 = (3n+2)(n-1)$. Vérification pour $n = 3$ : les couples $i < j$ donnent $1 \cdot 2 + 1 \cdot 3 + 2 \cdot 3 = 11$, et $\frac{2 \cdot 3 \cdot 4 \cdot 11}{24} = 11$.

Compétences à pratiquer

Lire le domaine d'une somme triangulaire ★
Évaluer une somme triangulaire ★
Permuter l'ordre d'une somme triangulaire ★★
Calculer une somme triangulaire ★★
Utiliser une somme double pour démontrer une identité ★★★
Couper une somme double symétrique ★★★

III.3 Produits doubles

Produits sur des couples

Le symbole $\prod$ sur des couples d'indices suit les mêmes règles que $\sum$ : l'ordre des deux produits peut s'échanger sur un rectangle et sur un triangle. Les démonstrations sont celles des sommes doubles, avec le produit à la place de la somme, puisqu'un produit se construit en multipliant un facteur après l'autre comme une somme se construit en ajoutant un terme après l'autre.

Signaler une erreur

Proposition — Permuter des produits

Soient $I$ et $J$ deux ensembles finis et $(a_{i,j})_{(i,j) \in I \times J}$ une famille de réels. Alors $$ \textcolor{colorprop}{\prod_{(i,j) \in I \times J} a_{i,j} = \prod_{i \in I} \Bigl( \prod_{j \in J} a_{i,j} \Bigr) = \prod_{j \in J} \Bigl( \prod_{i \in I} a_{i,j} \Bigr).} $$ Pour $n \ge 1$ et des réels $a_{i,j}$ indexés par $\llbracket 1, n \rrbracket^2$, $$ \textcolor{colorprop}{\prod_{1 \le i \le j \le n} a_{i,j} = \prod_{i=1}^{n} \prod_{j=i}^{n} a_{i,j} = \prod_{j=1}^{n} \prod_{i=1}^{j} a_{i,j},} $$ et il en va de même pour le triangle strict $1 \le i < j \le n$, avec les bornes de la Proposition « Permuter l'ordre sur un triangle ». Les deux produits sur un rectangle, ou sur un triangle, s'échangent exactement comme les deux sommes.

Preuve

Démonstration, en listant les facteurs. D'après la Définition « Produit sur un ensemble fini », un produit sur un ensemble fini ne dépend ni de l'ordre ni du parenthésage de ses facteurs. Soit $i_1, \dots, i_r$ une énumération de $I$ et $j_1, \dots, j_s$ une de $J$. On liste les couples de $I \times J$ ligne par ligne, $(i_1, j_1), \dots, (i_1, j_s), (i_2, j_1), \dots, (i_r, j_s)$, et l'on regroupe les facteurs de chaque ligne : le produit sur $I \times J$ est $\prod_{k=1}^{r} \bigl( \prod_{l=1}^{s} a_{i_k, j_l} \bigr) = \prod_{i \in I} \prod_{j \in J} a_{i,j}$. En listant les couples colonne par colonne et en regroupant chaque colonne, on obtient $\prod_{j \in J} \prod_{i \in I} a_{i,j}$. Pour le triangle large, les couples listés ligne par ligne, la ligne de $i$ étant $(i, i), (i, i+1), \dots, (i, n)$, donnent $\prod_{i=1}^{n} \prod_{j=i}^{n} a_{i,j}$ ; listés colonne par colonne, la colonne de $j$ étant $(1, j), \dots, (j, j)$, ils donnent $\prod_{j=1}^{n} \prod_{i=1}^{j} a_{i,j}$. Le triangle strict est identique avec les lignes $(i, i+1), \dots, (i, n)$ et les colonnes $(1, j), \dots, (j-1, j)$.

Exemple — Un produit double

Calculer $\displaystyle \prod_{1 \le i, j \le n} i j^2$ pour $n \ge 1$.

Correction

Le produit porte sur tout le carré ; on prend d'abord le produit sur $j$, en traitant $i$ comme une constante. $$ \begin{aligned} \prod_{1 \le i, j \le n} i j^2 &= \prod_{i=1}^{n} \prod_{j=1}^{n} i j^2 && \text{(permuter des produits)} \\ &= \prod_{i=1}^{n} \Bigl( i^n \prod_{j=1}^{n} j^2 \Bigr) && \text{(règles de calcul sur les produits : le facteur $i$ figure $n$ fois)} \\ &= \prod_{i=1}^{n} \Bigl( i^n (n!)^2 \Bigr) && \text{(règles de calcul sur les produits : $\prod_j j^2 = (\prod_j j)^2$, et $\prod_{j=1}^{n} j = n!$)} \\ &= \Bigl( \prod_{i=1}^{n} i^n \Bigr) \Bigl( \prod_{i=1}^{n} (n!)^2 \Bigr) && \text{(règles de calcul sur les produits : produit de deux familles)} \\ &= \Bigl( \prod_{i=1}^{n} i \Bigr)^n \bigl( (n!)^2 \bigr)^n && \text{(règles de calcul sur les produits : puissances, $n$ facteurs égaux)} \\ &= (n!)^n \, (n!)^{2n} && \text{(définition « Factorielle »)} \\ &= (n!)^{3n}, \end{aligned} $$ la dernière étape par la règle $x^a x^b = x^{a+b}$. Vérification pour $n = 2$ : les quatre couples $(1,1)$, $(1,2)$, $(2,1)$, $(2,2)$ donnent les facteurs $1$, $4$, $2$, $8$, dont le produit est $64 = (2!)^6$.

Compétences à pratiquer

Évaluer un produit double ★
Calculer un produit double ★★

IV Coefficients binomiaux

Des nombres définis par une formule

Le coefficient binomial $\binom{n}{k}$ est un nombre défini par une formule avec des factorielles. C'est le coefficient de $a^{n-k} b^k$ dans le développement de $(a + b)^n$, ce qu'énonce la formule du binôme ; il dénombre aussi les parties à $k$ éléments d'un ensemble à $n$ éléments, lecture établie dans le chapitre de dénombrement et non employée ici. Chaque propriété est un calcul sur la formule : la symétrie, l'identité d'absorption, et la relation de Pascal, qui construit le triangle de Pascal et, par une récurrence, la formule du binôme elle-même. Deux conventions rendent les formules valables pour tout entier $k$ : $0! = 1$, et $\binom{n}{k} = 0$ en dehors de $0 \le k \le n$.

Signaler une erreur

IV.1 Définition et premières propriétés

Définir le coefficient par sa formule

Le lycée a défini $\binom{n}{k}$ par une formule et l'a lu dans le triangle de Pascal. La définition garde la formule et fixe une valeur pour tout entier $k$, nulle en dehors de $0 \le k \le n$. Trois résultats en découlent, tous démontrés par le calcul : une forme produit qui évite la factorielle de $n$ et vaut même lorsque $k > n$, les identités de symétrie et d'absorption, et la relation de Pascal.

Signaler une erreur

Définition — Coefficient binomial

Pour $n \in \mathbb{N}$ et $k \in \mathbb{Z}$, le coefficient binomial $\binom{n}{k}$ est $$ \textcolor{colordef}{\binom{n}{k}} = \begin{cases} \dfrac{n!}{k!\,(n-k)!} & \text{si } 0 \le k \le n, \\ 0 & \text{sinon.} \end{cases} $$ On lit « $k$ parmi $n$ ». La convention $\binom{n}{k} = 0$ pour $k < 0$ et pour $k > n$ rend valable pour tout entier $k$ chaque formule sur les coefficients binomiaux, sans séparer les bords.

Proposition — Forme produit

Pour $n \in \mathbb{N}$ et $k \in \mathbb{N}$, y compris $k > n$, $$ \textcolor{colorprop}{\binom{n}{k} = \frac{1}{k!} \prod_{i=0}^{k-1} (n - i) = \frac{n(n-1) \cdots (n-k+1)}{k!}.} $$ La forme produit a $k$ facteurs et n'exige pas la factorielle de $n$ ; pour $k = 0$ le produit est vide et vaut $1$.

Preuve

Le cas $k \le n$. D'après la Proposition « Récurrence et quotients de factorielles » avec $p = n - k$, $\frac{n!}{(n-k)!} = \prod_{m=n-k+1}^{n} m$. Les $k$ entiers $n - k + 1, \dots, n$ sont les nombres $n - i$ pour $i = 0, \dots, k - 1$, listés dans l'ordre inverse : $$ \begin{aligned} \prod_{m=n-k+1}^{n} m &= \prod_{j=n-k+1}^{n} (2n - k + 1 - j) && \text{(réflexion de la Proposition « Règles de calcul sur les produits »)} \\ &= \prod_{i=0}^{k-1} (n - i), \end{aligned} $$ la dernière étape étant le décalage $j = n - k + 1 + i$ de la même Proposition. Donc $$ \begin{aligned} \binom{n}{k} &= \frac{n!}{k!\,(n-k)!} && \text{(définition)} \\ &= \frac{1}{k!} \cdot \frac{n!}{(n-k)!} && \text{(factorisation de $\frac{1}{k!}$)} \\ &= \frac{1}{k!} \prod_{i=0}^{k-1} (n - i). \end{aligned} $$ Le cas $k > n$. Alors $n \le k - 1$, donc l'indice $i = n$ figure dans le produit $\prod_{i=0}^{k-1} (n - i)$, avec le facteur $n - n = 0$ : le produit est $0$, et $\binom{n}{k}$ aussi par la Définition.

Proposition — Valeurs usuelles

Pour tout $n \in \mathbb{N}$, $$ \textcolor{colorprop}{\binom{n}{0} = \binom{n}{n} = 1, \qquad \binom{n}{1} = \binom{n}{n-1} = n, \qquad \binom{n}{2} = \binom{n}{n-2} = \frac{n(n-1)}{2}.} $$

Preuve

Les valeurs $\binom{n}{0}$ et $\binom{n}{n}$. Les indices $0$ et $n$ sont dans $\llbracket 0, n \rrbracket$, et la Définition donne $\binom{n}{0} = \frac{n!}{0!\,n!} = 1$ et $\binom{n}{n} = \frac{n!}{n!\,0!} = 1$.
Les valeurs $\binom{n}{1}$ et $\binom{n}{2}$. D'après la Proposition « Forme produit », valable pour tout $n \in \mathbb{N}$, $\binom{n}{1} = \frac{1}{1!} \prod_{i=0}^{0} (n - i) = n$ et $$ \begin{aligned} \binom{n}{2} &= \frac{1}{2!} \prod_{i=0}^{1} (n - i) && \text{(forme produit)} \\ &= \frac{n(n-1)}{2}. \end{aligned} $$ Les valeurs $\binom{n}{n-1}$ et $\binom{n}{n-2}$. Pour $n \ge 1$, $\binom{n}{n-1} = \frac{n!}{(n-1)!\,1!} = n$ par la Définition. Pour $n \ge 2$, $$ \begin{aligned} \binom{n}{n-2} &= \frac{n!}{(n-2)!\,2!} && \text{(définition)} \\ &= \frac{n(n-1)}{2}, \end{aligned} $$ la dernière étape d'après la Proposition « Récurrence et quotients de factorielles », $\frac{n!}{(n-2)!} = n(n-1)$. Pour $n = 0$ l'indice du bas $n - 1 = -1$ est strictement négatif, donc $\binom{0}{-1} = 0 = n$ ; pour $n \in \{0, 1\}$ l'indice du bas $n - 2$ est strictement négatif, donc $\binom{n}{n-2} = 0 = \frac{n(n-1)}{2}$ : la convention couvre ces bords.

Exemple — Calculer à partir de la définition

À partir de la définition, puis de la forme produit : $$ \begin{aligned} \binom{5}{2} &= \frac{5!}{2!\,3!} && \text{(définition)} \\ &= \frac{120}{2 \times 6} && \text{(valeurs des factorielles)} \\ &= 10, \end{aligned} $$ et, d'après la Proposition « Forme produit », $\binom{5}{2} = \frac{5 \times 4}{2!} = 10$ : un seul produit court à la place de trois factorielles. La convention donne $\binom{3}{5} = 0$ et $\binom{4}{-1} = 0$ ; pour $\binom{3}{5}$ la forme produit montre pourquoi, puisque $\binom{3}{5} = \frac{3 \times 2 \times 1 \times 0 \times (-1)}{5!}$ a le facteur nul $3 - 3$.

Proposition — Symétrie et absorption

Soient $n \in \mathbb{N}$ et $k \in \mathbb{Z}$.

Symétrie : $\textcolor{colorprop}{\binom{n}{k} = \binom{n}{n-k}}$.
Absorption : pour $n \ge 1$, $\textcolor{colorprop}{k \binom{n}{k} = n \binom{n-1}{k-1}}$ ; pour $n \ge 2$, $\textcolor{colorprop}{k(k-1) \binom{n}{k} = n(n-1) \binom{n-2}{k-2}}$.

Pour $k \ne 0$ la première identité d'absorption s'écrit $\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}$, la « formule du capitaine ».

Preuve

Première démonstration, par la formule factorielle. Symétrie. Pour $0 \le k \le n$, l'entier $n - k$ est aussi dans $\llbracket 0, n \rrbracket$, et $$ \begin{aligned} \binom{n}{n-k} &= \frac{n!}{(n-k)!\,\bigl( n - (n-k) \bigr)!} && \text{(définition à l'indice $n - k$)} \\ &= \frac{n!}{(n-k)!\,k!} && \text{(car $n - (n-k) = k$)} \\ &= \frac{n!}{k!\,(n-k)!} && \text{(commutativité du produit)} \\ &= \binom{n}{k}, \end{aligned} $$ la dernière étape par la Définition à l'indice $k$. Pour $k < 0$ ou $k > n$, l'indice $n - k$ est plus grand que $n$ ou strictement négatif, donc les deux coefficients sont nuls.
Absorption. Soit $n \ge 1$. Pour $1 \le k \le n$, $$ \begin{aligned} k \binom{n}{k} &= \frac{k \cdot n!}{k!\,(n-k)!} && \text{(définition)} \\ &= \frac{k \cdot n!}{k\,(k-1)!\,(n-k)!} && \text{($k! = k\,(k-1)!$)} \\ &= \frac{n!}{(k-1)!\,(n-k)!} && \text{(simplification de $k \ne 0$)} \\ &= \frac{n\,(n-1)!}{(k-1)!\,\bigl( (n-1) - (k-1) \bigr)!} && \text{($n! = n\,(n-1)!$ et $n - k = (n-1) - (k-1)$)} \\ &= n \binom{n-1}{k-1}, \end{aligned} $$ la dernière étape par la Définition en $(n-1, k-1)$. Pour $k \le 0$ ou $k > n$ les deux membres sont nuls : le membre de gauche parce que $\binom{n}{k} = 0$ ou $k = 0$, le membre de droite parce que $k - 1 < 0$ ou $k - 1 > n - 1$. Pour la seconde identité, soit $n \ge 2$ ; la première s'applique au couple $(n-1, k-1)$ puisque $n - 1 \ge 1$ : $$ \begin{aligned} k(k-1) \binom{n}{k} &= (k-1) \cdot n \binom{n-1}{k-1} && \text{(absorption en $(n, k)$)} \\ &= n \cdot (k-1) \binom{n-1}{k-1} && \text{(commutativité du produit)} \\ &= n(n-1) \binom{n-2}{k-2}, \end{aligned} $$ la dernière étape par l'absorption en $(n-1, k-1)$.
Seconde démonstration de l'absorption, par la forme produit. Soient $n \ge 1$ et $k \ge 1$, sans condition entre $k$ et $n$. Alors $$ \begin{aligned} k \binom{n}{k} &= \frac{k}{k!} \prod_{i=0}^{k-1} (n - i) && \text{(forme produit)} \\ &= \frac{1}{(k-1)!} \cdot n \prod_{i=1}^{k-1} (n - i) && \text{($k! = k\,(k-1)!$ ; le facteur $i = 0$ est $n$)} \\ &= n \cdot \frac{1}{(k-1)!} \prod_{j=0}^{k-2} \bigl( (n-1) - j \bigr) && \text{(règles de calcul sur les produits : décalage $j = i - 1$)} \\ &= n \binom{n-1}{k-1}, \end{aligned} $$ la dernière étape par la Proposition « Forme produit » au couple $(n-1, k-1)$ d'entiers naturels. Ce calcul n'a pas de cas $k > n$ : le facteur nul de la forme produit fait le travail de la convention. Pour $k \le 0$ les deux membres sont nuls, comme dans la première démonstration.

Proposition — Relation de Pascal

Pour $n \in \mathbb{N}$ et $k \in \mathbb{Z}$, $$ \textcolor{colorprop}{\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}.} $$ Chaque case d'une ligne du triangle est la somme des deux cases situées au-dessus : les cases $\binom{n}{k}$ et $\binom{n}{k+1}$ de la ligne $n$ donnent la case $\binom{n+1}{k+1}$ de la ligne $n + 1$. La relation vaut pour tout entier $k$, bords du triangle compris, grâce à la convention $\binom{n}{k} = 0$ en dehors de $0 \le k \le n$.

Preuve

Première démonstration, par l'absorption et la symétrie. L'identité d'absorption au couple $(n+1, k+1)$, valable pour tout entier $k$ car $n + 1 \ge 1$, s'écrit $(k+1) \binom{n+1}{k+1} = (n+1) \binom{n}{k}$ : c'est la première identité. Au couple $(n+1, n-k)$ elle s'écrit $(n-k) \binom{n+1}{n-k} = (n+1) \binom{n}{n-k-1}$. Par la symétrie, $$ \begin{aligned} \binom{n+1}{n-k} &= \binom{n+1}{(n+1)-(n-k)} && \text{(symétrie)} \\ &= \binom{n+1}{k+1} \end{aligned} $$ et $$ \begin{aligned} \binom{n}{n-k-1} &= \binom{n}{n-(n-k-1)} && \text{(symétrie)} \\ &= \binom{n}{k+1}, \end{aligned} $$ les dernières étapes simplifiant les indices inférieurs, donc $(n-k) \binom{n+1}{k+1} = (n+1) \binom{n}{k+1}$ : c'est la seconde identité. Alors $$ \begin{aligned} (n+1) \Bigl( \binom{n}{k} + \binom{n}{k+1} \Bigr) &= (n+1) \binom{n}{k} + (n+1) \binom{n}{k+1} && \text{(distributivité)} \\ &= (k+1) \binom{n+1}{k+1} + (n-k) \binom{n+1}{k+1} && \text{(la première et la seconde identité)} \\ &= (n+1) \binom{n+1}{k+1}, \end{aligned} $$ la dernière étape en factorisant $\binom{n+1}{k+1}$, puisque $(k+1) + (n-k) = n+1$. La division par $n + 1 \ne 0$ donne la relation de Pascal, pour tout entier $k$ : la démonstration n'a aucun cas, car l'absorption et la symétrie valent pour tout entier $k$, bords du triangle compris.
Seconde démonstration, par la formule factorielle. L'entier $k$ est dans l'un de cinq cas, qui recouvrent $\mathbb{Z}$ quel que soit $n$ : $0 \le k \le n - 1$, $k = n$, $k = -1$, $k < -1$, $k > n$.
Cas $0 \le k \le n - 1$. Les entiers $k$ et $k + 1$ sont dans $\llbracket 0, n \rrbracket$. Le dénominateur commun $(k+1)!\,(n-k)!$ s'obtient avec les identités $(k+1)! = (k+1)\,k!$ et $(n-k)! = (n-k)\,(n-k-1)!$ : $$ \begin{aligned} \binom{n}{k} + \binom{n}{k+1} &= \frac{n!}{k!\,(n-k)!} + \frac{n!}{(k+1)!\,(n-k-1)!} && \text{(définition)} \\ &= \frac{(k+1)\,n!}{(k+1)!\,(n-k)!} + \frac{(n-k)\,n!}{(k+1)!\,(n-k)!} && \text{(dénominateur commun)} \\ &= \frac{n!\,\bigl[ (k+1) + (n-k) \bigr]}{(k+1)!\,(n-k)!} && \text{(factorisation de $n!$)} \\ &= \frac{(n+1)\,n!}{(k+1)!\,\bigl( (n+1) - (k+1) \bigr)!} && \text{($(k+1) + (n-k) = n+1$ et $n - k = (n+1) - (k+1)$)} \\ &= \frac{(n+1)!}{(k+1)!\,\bigl( (n+1) - (k+1) \bigr)!} && \text{($(n+1)\,n! = (n+1)!$)} \\ &= \binom{n+1}{k+1}, \end{aligned} $$ la dernière étape par la Définition en $(n+1, k+1)$, puisque $0 \le k + 1 \le n + 1$.
Cas $k = n$. $\binom{n}{n} + \binom{n}{n+1} = 1 + 0 = 1 = \binom{n+1}{n+1}$.
Cas $k = -1$. $\binom{n}{-1} + \binom{n}{0} = 0 + 1 = 1 = \binom{n+1}{0}$.
Cas $k < -1$. Alors $k < 0$ et $k + 1 < 0$, donc les trois coefficients sont nuls.
Cas $k > n$. Alors $k > n$ et $k + 1 > n + 1$, donc les trois coefficients sont nuls.

Proposition — Les coefficients binomiaux sont entiers

Pour tout $n \in \mathbb{N}$ et tout $k \in \mathbb{Z}$, $$ \textcolor{colorprop}{\binom{n}{k} \in \mathbb{N}.} $$ Le quotient $\frac{n!}{k!\,(n-k)!}$ de factorielles est donc un entier, ce que la formule seule ne montre pas ; que $\binom{n}{k}$ dénombre les parties à $k$ éléments d'un ensemble à $n$ éléments est l'objet du chapitre de dénombrement.

Preuve

Récurrence sur $n$. Notons $P_n$ la propriété « $\binom{n}{k} \in \mathbb{N}$ pour tout $k \in \mathbb{Z}$ ».
Initialisation. Pour $n = 0$, $\binom{0}{0} = \frac{0!}{0!\,0!} = 1$ et $\binom{0}{k} = 0$ pour $k \ne 0$ : $P_0$ est vraie.
Hérédité. Soit $n \in \mathbb{N}$ et supposons $P_n$. Soit $k \in \mathbb{Z}$. La relation de Pascal en $(n, k-1)$, valable car $k - 1 \in \mathbb{Z}$, donne $$ \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}. $$ Les deux termes de droite sont des entiers naturels par $P_n$, et une somme de deux entiers naturels est un entier naturel : $\binom{n+1}{k} \in \mathbb{N}$. Cela vaut pour tout $k \in \mathbb{Z}$ : c'est $P_{n+1}$. Puisque $P_0$ est vraie et que $P_n \Rightarrow P_{n+1}$ pour tout $n \in \mathbb{N}$, par récurrence $P_n$ est vraie pour tout $n \in \mathbb{N}$.

Méthode — Calculer avec des coefficients binomiaux

Pour calculer avec des coefficients binomiaux, de l'outil le moins coûteux au plus coûteux :

Une valeur numérique : remplacer $k$ par $n - k$ si celui-ci est plus petit (Symétrie et absorption), puis employer la forme produit à $k$ facteurs ; par exemple $\binom{13}{10} = \binom{13}{3} = \frac{13 \times 12 \times 11}{3!} = 286$.
Un coefficient multiplié par $k$ ou divisé par $k + 1$ : faire sortir le facteur par l'absorption, $k \binom{n}{k} = n \binom{n-1}{k-1}$, ou sous la forme $(k+1) \binom{n+1}{k+1} = (n+1) \binom{n}{k}$.
Deux voisins d'une ligne : les comparer par le quotient $\binom{n}{k} = \frac{n-k+1}{k} \binom{n}{k-1}$ pour $1 \le k \le n$, obtenu à partir de la formule factorielle avec $k! = k\,(k-1)!$ et $(n-k+1)! = (n-k+1)\,(n-k)!$.
Une somme de deux voisins : la relation de Pascal, $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$.
Tout le reste : revenir aux factorielles et simplifier.

Vérifier les bords : les formules valent pour tout entier $k$ grâce à la convention, donc un coefficient en dehors de $0 \le k \le n$ vaut $0$, et n'est pas indéfini.

Exemple — Passer à la ligne suivante

Montrer que $\binom{n+1}{k+1} = \dfrac{n+1}{k+1} \binom{n}{k}$ pour $n, k \in \mathbb{N}$, et en déduire $\binom{10}{4}$ à partir de $\binom{9}{3}$.

Correction

L'absorption au couple $(n+1, k+1)$, valable puisque $n + 1 \ge 1$, s'écrit $(k+1) \binom{n+1}{k+1} = (n+1) \binom{n}{k}$. En divisant par $k + 1 \ne 0$ : $$ \begin{aligned} \binom{n+1}{k+1} &= \frac{1}{k+1} \cdot (k+1) \binom{n+1}{k+1} && \text{($k + 1 \ne 0$)} \\ &= \frac{1}{k+1} \cdot (n+1) \binom{n}{k} && \text{(symétrie et absorption)} \\ &= \frac{n+1}{k+1} \binom{n}{k}. \end{aligned} $$ Pour $n = 9$ et $k = 3$ : $$ \begin{aligned} \binom{10}{4} &= \frac{10}{4} \binom{9}{3} && \text{(l'identité avec $n = 9$, $k = 3$)} \\ &= \frac{10}{4} \times 84 && \text{(forme produit : $\binom{9}{3} = \frac{9 \times 8 \times 7}{3!} = 84$)} \\ &= 210. \end{aligned} $$ Donc $\binom{n+1}{k+1} = \frac{n+1}{k+1} \binom{n}{k}$ pour tous $n, k \in \mathbb{N}$, et $\binom{10}{4} = 210$.

Compétences à pratiquer

Distinguer les identités vraies sur les coefficients binomiaux ★
Évaluer un coefficient binomial ★
Utiliser la symétrie et les valeurs usuelles ★
Démontrer une identité sur les coefficients binomiaux ★★
Démontrer une propriété arithmétique ou d'ordre des coefficients binomiaux ★★★

IV.2 Triangle de Pascal et sommes de coefficients binomiaux

Un tableau construit par addition

La relation de Pascal donne la case $\binom{n+1}{k+1}$ à partir de deux cases de la ligne $n$, sans aucune factorielle : chaque case d'une nouvelle ligne est la somme des deux cases situées au-dessus. Le tableau des coefficients binomiaux, ligne après ligne, est le triangle de Pascal. Ses diagonales sont des sommes de cases à calculer, et la relation de Pascal les calcule.

Signaler une erreur

Exemple

Les sept premières lignes du triangle de Pascal. La ligne $n$ contient $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$. Chaque entrée est la somme des deux entrées diagonales au-dessus (relation de Pascal).

Méthode — Construire le triangle de Pascal ligne par ligne

Pour calculer les coefficients binomiaux des premières lignes :

Partir de la ligne $0$, qui est $\binom{0}{0} = 1$.
Bords : chaque ligne commence et finit par $1$, puisque $\binom{n}{0} = \binom{n}{n} = 1$ (Valeurs usuelles).
Intérieur : chaque case est la somme des deux cases situées en diagonale au-dessus, par la relation de Pascal $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$ : les cases $\binom{n}{k}$ et $\binom{n}{k+1}$ de la ligne $n$ donnent la case $\binom{n+1}{k+1}$ de la ligne $n + 1$.
Contrôle : la ligne $n$ se lit de la même façon de droite à gauche (Symétrie et absorption), et sa deuxième case est $n$.

Pour un seul coefficient d'une grande ligne, la forme produit après la symétrie est plus courte que le triangle.

Proposition — Somme d'une colonne du triangle de Pascal

Pour $p, n \in \mathbb{N}$ avec $p \le n$, $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=p}^{n} \binom{k}{p} &= \binom{n+1}{p+1} \\ \binom{p}{p} + \binom{p+1}{p} + \dots + \binom{n}{p} &= \binom{n+1}{p+1} \end{aligned}} $$ La somme des cases d'une diagonale du triangle, de la case $1$ du haut jusqu'à la ligne $n$, est la case située en dessous à droite de la dernière, sur la ligne $n + 1$.

Preuve

Première démonstration, par télescopage. Pour tout $k \ge p$, la relation de Pascal en $(k, p)$ s'écrit $\binom{k}{p} + \binom{k}{p+1} = \binom{k+1}{p+1}$, donc $\binom{k}{p} = \binom{k+1}{p+1} - \binom{k}{p+1}$. Avec $u_k = \binom{k}{p+1}$, c'est $\binom{k}{p} = u_{k+1} - u_k$. D'après la Proposition « Somme télescopique », $$ \begin{aligned} \sum_{k=p}^{n} \binom{k}{p} &= \sum_{k=p}^{n} (u_{k+1} - u_k) && \text{(relation de Pascal)} \\ &= u_{n+1} - u_p && \text{(somme télescopique)} \\ &= \binom{n+1}{p+1} - \binom{p}{p+1} && \text{(définition de $u_k$)} \\ &= \binom{n+1}{p+1}, \end{aligned} $$ la dernière étape parce que $\binom{p}{p+1} = 0$, l'indice du bas dépassant celui du haut.
Seconde démonstration, par récurrence sur $n \ge p$. Notons $P_n$ la propriété « $\sum_{k=p}^{n} \binom{k}{p} = \binom{n+1}{p+1}$ ». Pour $n = p$, la somme est $\binom{p}{p} = 1 = \binom{p+1}{p+1}$ : $P_p$ est vraie. Soit $n \ge p$ et supposons $P_n$. Alors $$ \begin{aligned} \sum_{k=p}^{n+1} \binom{k}{p} &= \sum_{k=p}^{n} \binom{k}{p} + \binom{n+1}{p} && \text{(définition de $\sum$)} \\ &= \binom{n+1}{p+1} + \binom{n+1}{p} && \text{(hypothèse de récurrence)} \\ &= \binom{n+2}{p+1}, \end{aligned} $$ la dernière étape par la relation de Pascal en $(n+1, p)$. C'est $P_{n+1}$ ; par récurrence, $P_n$ est vraie pour tout $n \ge p$.

Exemple — La somme des carrés par les coefficients binomiaux

Calculer $\displaystyle \sum_{k=1}^{n} k^2$ pour $n \ge 2$ avec les coefficients binomiaux $\binom{k}{1}$ et $\binom{k}{2}$.

Correction

On écrit le carré avec les deux coefficients : $k^2 = k(k-1) + k = 2 \binom{k}{2} + \binom{k}{1}$, d'après la Proposition « Valeurs usuelles ». $$ \begin{aligned} \sum_{k=1}^{n} k^2 &= \sum_{k=1}^{n} \Bigl( 2 \binom{k}{2} + \binom{k}{1} \Bigr) && \text{(valeurs usuelles)} \\ &= 2 \sum_{k=2}^{n} \binom{k}{2} + \sum_{k=1}^{n} \binom{k}{1} && \text{(linéarité de $\sum$ ; le terme $k = 1$ de la première somme est $\binom{1}{2} = 0$)} \\ &= 2 \binom{n+1}{3} + \binom{n+1}{2} && \text{(somme d'une colonne du triangle de Pascal, avec $p = 2$ et $p = 1$)} \\ &= \frac{(n+1)\,n\,(n-1)}{3} + \frac{(n+1)\,n}{2} && \text{(forme produit)} \\ &= \frac{n(n+1)}{6} \bigl( 2(n-1) + 3 \bigr) && \text{(dénominateur commun $6$, factorisation de $\frac{n(n+1)}{6}$)} \\ &= \frac{n(n+1)(2n+1)}{6}. \end{aligned} $$ C'est la valeur du Théorème « Sommes classiques », atteinte par une troisième méthode.

Compétences à pratiquer

Construire et lire le triangle de Pascal ★
Sommer une colonne du triangle de Pascal ★★
Déduire une somme de l'identité de la colonne ★★★

IV.3 La formule du binôme

Développer la puissance d'une somme

Le lycée a développé $(a + b)^2 = a^2 + 2ab + b^2$ et $(a + b)^3$, et a lu les coefficients de $(a + b)^n$ dans le triangle de Pascal. La formule du binôme énonce le développement pour tout $n$ et donne le coefficient de chaque monôme : le coefficient binomial $\binom{n}{k}$ multiplie $a^{n-k} b^k$. Sa démonstration est une récurrence dans laquelle la relation de Pascal est le pas.

Signaler une erreur

Théorème — Formule du binôme (Newton)

Pour $a, b \in \mathbb{R}$ et $n \in \mathbb{N}$, avec la convention $x^0 = 1$ pour tout réel $x$, $0$ compris, $$ \textcolor{colorprop}{\begin{aligned} (a + b)^n &= \sum_{k=0}^{n} \binom{n}{k}\, a^{n-k} b^k \\ (a + b)^n &= \binom{n}{0} a^n + \binom{n}{1} a^{n-1} b + \dots + \binom{n}{n} b^n \end{aligned}} $$ La puissance d'une somme est la somme, sur $k$, des monômes $a^{n-k} b^k$ pondérés par les coefficients binomiaux : elle a $n + 1$ termes, et dans chacun d'eux les exposants de $a$ et de $b$ ont pour somme $n$.

Preuve

Récurrence sur $n$. Notons $P_n$ la formule au rang $n$.
Initialisation. Pour $n = 0$, $(a + b)^0 = 1$ et $\sum_{k=0}^{0} \binom{0}{k}\, a^{0-k} b^k = \binom{0}{0}\, a^0 b^0 = 1$ : $P_0$ est vraie.
Hérédité. Soit $n \in \mathbb{N}$ et supposons $P_n$. Alors $$ \begin{aligned} (a + b)^{n+1} &= (a + b) \sum_{k=0}^{n} \binom{n}{k}\, a^{n-k} b^k && \text{(puissance ; hypothèse de récurrence)} \\ &= a \sum_{k=0}^{n} \binom{n}{k}\, a^{n-k} b^k + b \sum_{k=0}^{n} \binom{n}{k}\, a^{n-k} b^k && \text{(distributivité)} \\ &= \sum_{k=0}^{n} \binom{n}{k}\, a^{n+1-k} b^k + \sum_{k=0}^{n} \binom{n}{k}\, a^{n-k} b^{k+1} && \text{(linéarité de $\sum$, règles sur les puissances)} \\ &= \sum_{k=0}^{n+1} \binom{n}{k}\, a^{n+1-k} b^k + \sum_{k=0}^{n} \binom{n}{k}\, a^{n-k} b^{k+1} && \text{(le terme ajouté $k = n+1$ est $0$, car $\binom{n}{n+1} = 0$)} \\ &= \sum_{k=0}^{n+1} \binom{n}{k}\, a^{n+1-k} b^k + \sum_{k=1}^{n+1} \binom{n}{k-1}\, a^{n+1-k} b^k && \text{(décalage et réflexion, $j = k+1$)} \\ &= \sum_{k=0}^{n+1} \binom{n}{k}\, a^{n+1-k} b^k + \sum_{k=0}^{n+1} \binom{n}{k-1}\, a^{n+1-k} b^k && \text{(le terme ajouté $k = 0$ est $0$, car $\binom{n}{-1} = 0$)} \\ &= \sum_{k=0}^{n+1} \Bigl( \binom{n}{k} + \binom{n}{k-1} \Bigr) a^{n+1-k} b^k && \text{(linéarité de $\sum$)} \\ &= \sum_{k=0}^{n+1} \binom{n+1}{k}\, a^{n+1-k} b^k, \end{aligned} $$ la dernière étape par la relation de Pascal en $(n, k-1)$, valable pour tout entier $k$. Aucun terme n'est détaché des sommes : la convention $\binom{n}{k} = 0$ en dehors de $0 \le k \le n$ étend les deux sommes au même ensemble $\llbracket 0, n+1 \rrbracket$. C'est $P_{n+1}$. Puisque $P_0$ est vraie et que $P_n \Rightarrow P_{n+1}$ pour tout $n \in \mathbb{N}$, par récurrence $P_n$ est vraie pour tout $n \in \mathbb{N}$. La démonstration par dénombrement, qui lit $\binom{n}{k}$ comme le nombre de façons de choisir les facteurs qui donnent $b$, est l'objet du chapitre de dénombrement.

Le domaine de la formule du binôme

La démonstration n'emploie que les règles de calcul, jamais l'ordre de $\mathbb{R}$. Des nombres $a$ et $b$ elle emploie qu'on peut les additionner et les multiplier, que la multiplication est distributive sur l'addition et associative, et que $ab = ba$ ; des coefficients, que ce sont des entiers, un entier fois $x$ signifiant $x + \dots + x$. La formule vaut donc sans changement pour des nombres complexes, pour des polynômes, dans un anneau pour deux éléments qui commutent, et pour deux matrices qui commutent : ces cas sont traités dans les chapitres sur les nombres complexes, les polynômes, les structures algébriques et le calcul matriciel. L'hypothèse $ab = ba$ ne peut pas être supprimée : pour deux matrices $A$ et $B$ qui ne commutent pas, $(A + B)^2 = A^2 + AB + BA + B^2$ n'est pas $A^2 + 2AB + B^2$. Ici $a$ et $b$ sont des nombres réels.

Signaler une erreur

Proposition — Somme et somme alternée d'une ligne

Pour $n \in \mathbb{N}$, $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=0}^{n} \binom{n}{k} &= 2^n \\ \binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n} &= 2^n \end{aligned}} $$ Pour $n \ge 1$, $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=0}^{n} (-1)^k \binom{n}{k} &= 0 \\ \binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \dots + (-1)^n \binom{n}{n} &= 0 \end{aligned}} $$ $$ \textcolor{colorprop}{\sum_{\substack{0 \le k \le n \\ k \text{ pair}}} \binom{n}{k} = \sum_{\substack{0 \le k \le n \\ k \text{ impair}}} \binom{n}{k} = 2^{n-1}.} $$ Les cases d'une ligne du triangle ont pour somme $2^n$ ; la somme alternée d'une ligne est $0$, et les cases de rang pair et celles de rang impair ont la même somme.

Preuve

Première démonstration, par la formule du binôme. Avec $a = b = 1$, $$ \begin{aligned} \sum_{k=0}^{n} \binom{n}{k} &= \sum_{k=0}^{n} \binom{n}{k}\, 1^{n-k} 1^k && \text{($1^{n-k} 1^k = 1$)} \\ &= (1 + 1)^n && \text{(formule du binôme, $a = b = 1$)} \\ &= 2^n. \end{aligned} $$ Avec $a = 1$ et $b = -1$, pour $n \ge 1$, $$ \begin{aligned} \sum_{k=0}^{n} (-1)^k \binom{n}{k} &= \sum_{k=0}^{n} \binom{n}{k}\, 1^{n-k} (-1)^k && \text{($1^{n-k} = 1$)} \\ &= \bigl( 1 + (-1) \bigr)^n && \text{(formule du binôme, $a = 1$, $b = -1$)} \\ &= 0, \end{aligned} $$ la dernière étape parce que $0^n = 0$ pour $n \ge 1$. Notons $E$ et $O$ les sommes des $\binom{n}{k}$ sur les entiers $k$ pairs et sur les entiers $k$ impairs de $\llbracket 0, n \rrbracket$. Les entiers pairs et les entiers impairs forment un recouvrement disjoint de $\llbracket 0, n \rrbracket$, donc d'après la Proposition « Sommation par paquets » $E + O = \sum_{k=0}^{n} \binom{n}{k} = 2^n$ ; le signe $(-1)^k$ vaut $+1$ sur les $k$ pairs et $-1$ sur les $k$ impairs, donc par la même Proposition $E - O = \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$. En additionnant et en soustrayant ces deux relations, $2E = 2^n$ et $2O = 2^n$ : donc $E = O = 2^{n-1}$.
Seconde démonstration de la somme d'une ligne, par récurrence. Notons $S_n = \sum_{k=0}^{n} \binom{n}{k}$. Alors $S_0 = \binom{0}{0} = 1$, et pour $n \in \mathbb{N}$ $$ \begin{aligned} S_{n+1} &= \sum_{k=0}^{n+1} \binom{n+1}{k} && \text{(définition de $S_{n+1}$)} \\ &= \sum_{k=0}^{n+1} \binom{n}{k-1} + \sum_{k=0}^{n+1} \binom{n}{k} && \text{(relation de Pascal en $(n, k-1)$ ; linéarité de $\sum$)} \\ &= \sum_{k=1}^{n+1} \binom{n}{k-1} + \sum_{k=0}^{n} \binom{n}{k} && \text{(les termes $k = 0$ et $k = n+1$ sont nuls)} \\ &= \sum_{j=0}^{n} \binom{n}{j} + S_n && \text{(décalage et réflexion : $j = k - 1$ ; définition de $S_n$)} \\ &= 2 S_n. \end{aligned} $$ La dernière étape est la définition de $S_n$. Donc $S_{n+1} = 2 S_n$, et par récurrence à partir de $S_0 = 1$, $S_n = 2^n$ pour tout $n \in \mathbb{N}$.

Exemple — Développer une puissance quatrième

Développer $(a + b)^4$.

Correction

La formule du binôme avec $n = 4$ donne les cinq monômes, avec les coefficients de la ligne $4$ : $$ \begin{aligned} (a + b)^4 &= \sum_{k=0}^{4} \binom{4}{k}\, a^{4-k} b^k && \text{(formule du binôme)} \\ &= \binom{4}{0} a^4 + \binom{4}{1} a^3 b + \binom{4}{2} a^2 b^2 + \binom{4}{3} a b^3 + \binom{4}{4} b^4 && \text{(forme développée)} \\ &= a^4 + 4 a^3 b + 6 a^2 b^2 + 4 a b^3 + b^4, \end{aligned} $$ la dernière étape par la Proposition « Valeurs usuelles » : $\binom{4}{0} = \binom{4}{4} = 1$, $\binom{4}{1} = \binom{4}{3} = 4$ et $\binom{4}{2} = \frac{4 \times 3}{2} = 6$. Ce sont les cases de la ligne $4$ du triangle de Pascal.

Exemple — Des sommes reconnues comme une puissance

Calculer $\displaystyle \sum_{k=0}^{n} \binom{n}{k}\, 2^k$ et $\displaystyle \sum_{k=0}^{n} (-1)^k \binom{n}{k}\, 3^{n-k}$ pour $n \ge 1$.

Correction

Chaque somme a la forme $\sum_{k=0}^{n} \binom{n}{k}\, a^{n-k} b^k$ une fois son terme général récrit. $$ \begin{aligned} \sum_{k=0}^{n} \binom{n}{k}\, 2^k &= \sum_{k=0}^{n} \binom{n}{k}\, 1^{n-k} 2^k && \text{($1^{n-k} = 1$)} \\ &= (1 + 2)^n && \text{(formule du binôme, $a = 1$, $b = 2$)} \\ &= 3^n. \end{aligned} $$ $$ \begin{aligned} \sum_{k=0}^{n} (-1)^k \binom{n}{k}\, 3^{n-k} &= \sum_{k=0}^{n} \binom{n}{k}\, 3^{n-k} (-1)^k && \text{(commutativité du produit)} \\ &= \bigl( 3 + (-1) \bigr)^n && \text{(formule du binôme, $a = 3$, $b = -1$)} \\ &= 2^n. \end{aligned} $$ Vérification pour $n = 1$ : $1 + 2 = 3$ et $3 - 1 = 2$.

Méthode — Appliquer la formule du binôme

Pour appliquer la formule du binôme :

Pour développer $(a + b)^n$, prendre les coefficients de la ligne $n$ du triangle de Pascal pour un petit $n$, ou les calculer (Valeurs usuelles, Forme produit), et écrire $\binom{n}{k}\, a^{n-k} b^k$ pour $k = 0, \dots, n$. Lorsque $a$ ou $b$ est un produit, un nombre strictement négatif ou une puissance, le mettre entre parenthèses : pour $(2x - 3)^4$, $a = 2x$ et $b = -3$.
Pour reconnaître une somme, récrire son terme général sous la forme $\binom{n}{k}\, \alpha^{k} \beta^{n-k}$ avec $1$ pour une puissance absente ($2^{-k} = \bigl( \frac{1}{2} \bigr)^k$, $(-1)^k$, $3^{n-k}$) : la somme est $(\alpha + \beta)^n$.
Pour trouver un coefficient, écrire chaque terme comme une puissance de la variable : le terme général $\binom{n}{k}\, a^{n-k} b^k$ donne un exposant qui dépend de $k$ ; résoudre l'équation qui fixe cet exposant à celui voulu. Si elle a une solution entière dans $\llbracket 0, n \rrbracket$, le coefficient est $\binom{n}{k}$ fois les nombres portés par $a$ et $b$ ; sinon, le terme est absent.
Pour évaluer une somme de coefficients, choisir des valeurs de $a$ et $b$ : $a = b = 1$ donne la somme d'une ligne, $a = 1$ et $b = -1$ la somme alternée (Somme et somme alternée d'une ligne).

La formule exige les deux termes du binôme : une puissance d'une somme de trois nombres ne s'y développe pas directement.

Exemple — Un coefficient dans un développement

Déterminer le terme en $x^5$ dans le développement de $\Bigl( x + \dfrac{1}{x} \Bigr)^{11}$, pour $x \ne 0$.

Correction

La formule du binôme avec $a = x$ et $b = \frac{1}{x}$ donne chaque terme, et l'on lit l'exposant de $x$ dans chacun. $$ \begin{aligned} \Bigl( x + \frac{1}{x} \Bigr)^{11} &= \sum_{k=0}^{11} \binom{11}{k}\, x^{11-k} \Bigl( \frac{1}{x} \Bigr)^k && \text{(formule du binôme, $a = x$, $b = \frac{1}{x}$)} \\ &= \sum_{k=0}^{11} \binom{11}{k}\, x^{11-2k}, \end{aligned} $$ la dernière étape par les règles sur les puissances, $x^{11-k} x^{-k} = x^{11-2k}$. Les exposants $11 - 2k$ sont deux à deux distincts, donc un seul terme au plus a l'exposant $5$. L'équation $11 - 2k = 5$ a l'unique solution $k = 3$, entier de $\llbracket 0, 11 \rrbracket$. Le coefficient de $x^5$ est donc $$ \begin{aligned} \binom{11}{3} &= \frac{11 \times 10 \times 9}{3!} && \text{(forme produit)} \\ &= 165, \end{aligned} $$ et le terme en $x^5$ est $165\, x^5$.

Le télescopage d'une puissance quelconque

La Méthode « Calculer une somme de puissances par télescopage » calcule $\sum k^p$ pour $p = 1, 2, 3$ avec les identités remarquables. La formule du binôme la donne pour tout $p \in \mathbb{N}^*$. Pour $k \in \mathbb{N}$, $$ \begin{aligned} (k+1)^{p+1} - k^{p+1} &= \sum_{j=0}^{p+1} \binom{p+1}{j}\, k^j - k^{p+1} && \text{(formule du binôme, $a = 1$, $b = k$)} \\ &= \sum_{j=0}^{p} \binom{p+1}{j}\, k^j + \binom{p+1}{p+1}\, k^{p+1} - k^{p+1} && \text{(découpage et relation de Chasles)} \\ &= \sum_{j=0}^{p} \binom{p+1}{j}\, k^j + k^{p+1} - k^{p+1} && \text{(valeurs usuelles)} \\ &= \sum_{j=0}^{p} \binom{p+1}{j}\, k^j, \end{aligned} $$ la dernière étape simplifiant $k^{p+1}$ et $-k^{p+1}$. La différence $(k+1)^{p+1} - k^{p+1}$ est un polynôme de degré $p$ en $k$, de terme dominant $\binom{p+1}{p}\, k^p = (p+1)\,k^p$ d'après la Proposition « Valeurs usuelles ». Notons $S_j = \sum_{k=0}^{n} k^j$, de sorte que $S_0 = n + 1$, avec la convention $x^0 = 1$. La somme télescopique avec $u_k = k^{p+1}$ donne $\sum_{k=0}^{n} \bigl( (k+1)^{p+1} - k^{p+1} \bigr) = (n+1)^{p+1} - 0^{p+1} = (n+1)^{p+1}$, et la même somme se développe terme à terme : $$ \begin{aligned} \sum_{k=0}^{n} \bigl( (k+1)^{p+1} - k^{p+1} \bigr) &= \sum_{k=0}^{n} \sum_{j=0}^{p} \binom{p+1}{j}\, k^j && \text{(développement de $(k+1)^{p+1} - k^{p+1}$)} \\ &= \sum_{j=0}^{p} \sum_{k=0}^{n} \binom{p+1}{j}\, k^j && \text{(permuter l'ordre de sommation)} \\ &= \sum_{j=0}^{p} \binom{p+1}{j}\, S_j, \end{aligned} $$ la dernière étape par linéarité de $\sum$. Donc $(n+1)^{p+1} = \sum_{j=0}^{p} \binom{p+1}{j}\, S_j$, et, en isolant le terme $j = p$ où $\binom{p+1}{p} = p + 1$, pour tout $p \ge 1$, $$ S_p = \frac{1}{p+1} \Bigl( (n+1)^{p+1} - \sum_{j=0}^{p-1} \binom{p+1}{j}\, S_j \Bigr). $$ La somme des puissances $p$-ièmes se calcule à partir des sommes des puissances inférieures, pour tout $p$ ; les cas $p = 1, 2, 3$ redonnent le Théorème « Sommes classiques ».

Signaler une erreur

Compétences à pratiquer

Lire un développement binomial ★
Trouver un coefficient dans un développement ★
Développer une puissance d'un binôme ★
Évaluer une somme de coefficients binomiaux avec la formule du binôme ★
Évaluer une somme de coefficients binomiaux par absorption ou par parité ★★
Trouver l'identité cachée derrière une somme binomiale ★★★
Démontrer une identité de convolution de coefficients binomiaux ★★★

V Arithmétique dans $\mathbb{Z}$

On clôt l'atelier par les bases de l'arithmétique sur les entiers. Les ensembles $\mathbb{N}$ et $\mathbb{Z}$ sont supposés connus ; leur construction est hors de notre champ. On développe quatre outils, chacun élémentaire et chacun utilisé constamment par la suite. D'abord la relation de divisibilité $b \mid a$ et la division euclidienne $a = b q + r$, l'outil algorithmique qui convertit « $b$ divise-t-il $a$ ? » en « le reste est-il nul ? ». Puis le plus grand commun diviseur $a \wedge b$, calculé par les divisions euclidiennes itérées de l'algorithme d'Euclide, et le plus petit commun multiple $a \vee b$, relié au PGCD par $(a \wedge b)(a \vee b) = |ab|$. Enfin les nombres premiers : leur définition, l'infinitude de $\mathbb{P}$ (Euclide), le crible d'Ératosthène, et la décomposition de tout $n \geq 2$ en produit de nombres premiers — les briques de $\mathbb{N}^*$ pour la multiplication.
Convention permanente. Tout au long de cette section, un diviseur est toujours un entier non nul : chaque fois qu'on écrit « $d \mid a$ », on suppose tacitement $d \in \mathbb{Z}^*$. On utilise $\mathbb{N} = \{0, 1, 2, \dots\}$ et $\mathbb{N}^* = \mathbb{N} \setminus \{0\}$. Les notations $a \wedge b$ (PGCD) et $a \vee b$ (PPCM) sont standard.

Signaler une erreur

V.1 Divisibilité et division euclidienne

Deux définitions, un théorème. La définition de la divisibilité est le point d'entrée ; la division euclidienne est l'outil algorithmique qui convertit « $b \mid a$ ? » en « le reste est-il nul ? ». Le lycée couvre déjà les deux de façon informelle ; on les énonce formellement et on étend la division euclidienne aux dividendes négatifs.

Signaler une erreur

Définition — Divisibilité

Soient $a \in \mathbb{Z}$ et $b \in \mathbb{Z}^*$. On dit que $b$ divise $a$, et on note $b \mid a$, s'il existe $k \in \mathbb{Z}$ tel que $a = b k$. On dit aussi que $a$ est un multiple de $b$, ou que $b$ est un diviseur de $a$.
Notations :

$a \mathbb{Z} = \{a k : k \in \mathbb{Z}\}$ est l'ensemble des multiples de $a$ ;
$\operatorname{div}(a) = \{d \in \mathbb{Z}^* : d \mid a\}$ est l'ensemble des diviseurs de $a$.

Exemple

$\operatorname{div}(12) = \{\pm 1, \pm 2, \pm 3, \pm 4, \pm 6, \pm 12\}$. $\operatorname{div}(0) = \mathbb{Z}^*$ car tout entier non nul $d$ vérifie $0 = d \cdot 0$. L'ensemble des multiples de $5$ est $5 \mathbb{Z} = \{\dots, -10, -5, 0, 5, 10, \dots\}$.

Proposition — Propriétés de la divisibilité

Soient $a, b, c, d \in \mathbb{Z}$ et $u, v \in \mathbb{Z}$, avec la convention permanente qu'un diviseur est non nul (le diviseur figurant dans chaque énoncé ci-dessous appartient à $\mathbb{Z}^*$).

Réflexivité et transitivité. Pour tout $a \in \mathbb{Z}^*$, $a \mid a$. Si $a \mid b$ et $b \mid c$ (avec $a, b \in \mathbb{Z}^*$), alors $a \mid c$.
Entiers associés. Pour $a, b \in \mathbb{Z}^*$, $a \mid b \text{ et } b \mid a \iff |a| = |b|$. En particulier, restreint à $\mathbb{N}^*$ ceci redonne l'antisymétrie de $\mid$ : $a \mid b$ et $b \mid a \iff a = b$.
Combinaisons linéaires. Si $d \mid a$ et $d \mid b$, alors $d \mid (a u + b v)$ pour tout $u, v \in \mathbb{Z}$.
Produit. Si $a \mid b$ et $c \mid d$ (avec $a, c \in \mathbb{Z}^*$), alors $a c \mid b d$. En particulier $a^k \mid b^k$ pour tout $k \in \mathbb{N}^*$ lorsque $a \mid b$.

Preuve

Réflexivité / transitivité. $a = a \cdot 1$ donne $a \mid a$. Si $b = a k$ et $c = b k'$, alors $c = a (k k')$ avec $k k' \in \mathbb{Z}$, donc $a \mid c$.
Entiers associés. Si $a \mid b$ et $b \mid a$, écrire $b = a k$ et $a = b k'$. Alors $a = a (k k')$, donc $k k' = 1$ (car $a \neq 0$). Avec $k, k' \in \mathbb{Z}$, cela force $k = k' = \pm 1$, donc $|a| = |b|$. Réciproquement si $|a| = |b|$ alors $a = \pm b$, donc chacun divise l'autre.
Combinaisons linéaires. De $a = d k$ et $b = d k'$, $a u + b v = d (k u + k' v) \in d \mathbb{Z}$.
Produit. De $b = a k$ et $d = c k'$, $b d = (a c)(k k')$, donc $a c \mid b d$.

Méthode — Décider si $b \mid a$

Deux tests équivalents pour $b \in \mathbb{Z}^*$, $a \in \mathbb{Z}$ :

Test direct du quotient. Calculer $a / b$ dans $\mathbb{Q}$ ; vérifier si le résultat est entier.
Test du reste (préféré pour $a, b$ grands). Calculer la division euclidienne $a = b q + r$ avec $0 \leq r < |b|$ ; alors $b \mid a \iff r = 0$ (théorème suivant).

Théorème — Division euclidienne

Pour tout $a \in \mathbb{Z}$ et tout $b \in \mathbb{Z}^*$, il existe un unique couple $(q, r) \in \mathbb{Z} \times \mathbb{N}$ tel que $$ \textcolor{colorprop}{a = b q + r \quad \text{et} \quad 0 \leq r < |b|.} $$ L'entier $a$ est le dividende, $b$ le diviseur, $q$ le quotient et $r$ le reste de la division euclidienne de $a$ par $b$. Lorsque $b > 0$, le quotient est $q = \lfloor a / b \rfloor$, où $\lfloor \cdot \rfloor$ désigne la partie entière (le plus grand entier inférieur ou égal à un réel, vue dans le matériel sur les propriétés de $\mathbb{R}$).

Preuve

On traite d'abord le cas $b > 0$, puis on ramène le cas général à celui-ci.
Existence ($b > 0$). Posons $R = \{a - b k : k \in \mathbb{Z}\} \cap \mathbb{N}$. L'ensemble $R$ est non vide : si $a \geq 0$, alors $a = a - b \cdot 0 \in R$ ; si $a < 0$, alors $k = a$ donne $a - b a = a (1 - b) \geq 0$ car $1 - b \leq 0$ et $a < 0$, donc $a - b a \in R$. Comme partie non vide de $\mathbb{N}$, $R$ admet un plus petit élément ; notons-le $r$, et écrivons $r = a - b q$ pour un certain $q \in \mathbb{Z}$, soit $a = b q + r$ avec $r \geq 0$. Il reste à montrer $r < b$. Supposons par l'absurde $r \geq b$. Alors $r - b \in \mathbb{N}$ et $r - b = a - b (q + 1) \in R$, ce qui contredit la minimalité de $r$. Donc $r < b = |b|$.
Unicité ($b > 0$). Supposons $a = b q + r = b q' + r'$ avec $0 \leq r, r' < b$. Alors $b (q - q') = r' - r$, donc $|b (q - q')| = |r' - r| < b$, ce qui force $|q - q'| < 1$. Comme $q - q' \in \mathbb{Z}$, $q = q'$, et donc $r = r'$.
Cas général $b \in \mathbb{Z}^*$. On applique le cas déjà démontré au diviseur positif $|b|$ : il existe un unique $(q_0, r) \in \mathbb{Z} \times \mathbb{N}$ avec $a = |b| q_0 + r$ et $0 \leq r < |b|$. Si $b > 0$, on prend $(q, r) = (q_0, r)$ ; si $b < 0$, alors $|b| = -b$ et $a = b(-q_0) + r$, donc on prend $(q, r) = (-q_0, r)$. Dans les deux cas $a = b q + r$ avec $0 \leq r < |b|$, et l'unicité de $r$ (donc de $q$) découle de l'unicité pour $|b|$.
Formule pour $q$ lorsque $b > 0$. De $a / b = q + r / b$ avec $0 \leq r/b < 1$, on obtient $q = \lfloor a / b \rfloor$.

Exemple

Pour $a = 23$, $b = 5$ : $23 = 5 \cdot 4 + 3$, donc $q = 4$ et $r = 3$. En effet $\lfloor 23 / 5 \rfloor = 4$.

Exemple — Dividende négatif — piège classique

Pour $a = -23$, $b = 5$ : non $-23 = 5 \cdot (-4) - 3$, car le reste vaudrait alors $-3 < 0$. La division euclidienne correcte est $$ \textcolor{colorprop}{-23 = 5 \cdot (-5) + 2,} $$ donc $q = -5$ et $r = 2$. Vérification : $\lfloor -23 / 5 \rfloor = -5$ (pas $-4$). Le reste est toujours dans $\{0, 1, \dots, |b| - 1\}$.

Compétences à pratiquer

Divisibilité et division euclidienne

V.2 PGCD, algorithme d'Euclide et PPCM

Le plus grand commun diviseur (PGCD) de deux entiers est le plus grand entier qui les divise tous les deux. On le définit ici comme le plus grand élément, pour l'ordre naturel $\leq$ sur $\mathbb{N}^*$, de l'ensemble des diviseurs communs ; il se calcule effectivement par l'algorithme d'Euclide, une suite itérée de divisions euclidiennes. Le plus petit commun multiple (PPCM) est la notion duale, et la relation $(a \wedge b)(a \vee b) = |ab|$ relie les deux.

Signaler une erreur

Définition — Plus grand commun diviseur (PGCD)

Soient $a, b \in \mathbb{Z}$ non tous deux nuls. Le plus grand commun diviseur de $a$ et $b$, noté $a \wedge b$, est le plus grand élément de $\{d \in \mathbb{N}^* : d \mid a \text{ et } d \mid b\}$ pour l'ordre naturel $\leq$ sur $\mathbb{N}^*$. Par convention, $0 \wedge 0 = 0$.
L'ensemble $\{d \in \mathbb{N}^* : d \mid a \text{ et } d \mid b\}$ est non vide (il contient $1$) et fini (tout diviseur commun est majoré par $\max(|a|, |b|)$), donc son maximum existe.

Exemple

$12 \wedge 18 = 6$ : les diviseurs de $12$ dans $\mathbb{N}^*$ sont $\{1, 2, 3, 4, 6, 12\}$, les diviseurs de $18$ sont $\{1, 2, 3, 6, 9, 18\}$, les diviseurs communs sont $\{1, 2, 3, 6\}$, le maximum est $6$. De plus $a \wedge 1 = 1$ pour tout $a \in \mathbb{Z}$, et $a \wedge 0 = |a|$ pour tout $a \in \mathbb{Z}^*$.

Proposition — Idée fondamentale

Pour tout $a \in \mathbb{Z}$ et tout $b \in \mathbb{N}^*$, si $a = b q + r$ est la division euclidienne de $a$ par $b$, alors $$ \textcolor{colorprop}{a \wedge b = b \wedge r.} $$

Preuve

On montre que l'ensemble des diviseurs communs à $a$ et $b$ est égal à l'ensemble des diviseurs communs à $b$ et $r$ ; le PGCD, défini comme le maximum de cet ensemble, est donc le même.

$(\subset)$ Si $d \mid a$ et $d \mid b$, alors par combinaison linéaire $d \mid (a - b q) = r$. Donc $d$ divise $b$ et $r$.
$(\supset)$ Si $d \mid b$ et $d \mid r$, alors $d \mid (b q + r) = a$. Donc $d$ divise $a$ et $b$.

Les deux ensembles coïncident ; leurs maxima aussi : $a \wedge b = b \wedge r$.

Théorème — Existence du PGCD par l'algorithme d'Euclide

Soient $a, b \in \mathbb{N}$ avec $0 < b \leq a$. Définir une suite de restes par $r_0 = a$, $r_1 = b$, et $r_{k+2} = $ reste de la division euclidienne de $r_k$ par $r_{k+1}$ tant que $r_{k+1} > 0$. La suite s'arrête : il existe $N \geq 1$ tel que $r_N = 0$, et le PGCD est le dernier reste non nul : $$ \textcolor{colorprop}{a \wedge b = r_{N - 1}.} $$

Preuve

Terminaison. Tant que $r_{k+1} > 0$, la construction donne $0 \leq r_{k+2} < r_{k+1}$, donc les restes strictement positifs $r_1, r_2, \dots$ forment une suite strictement décroissante dans $\mathbb{N}^*$, qui est nécessairement finie ; il existe $N$ tel que $r_N = 0$.
Correction. Par l'« idée fondamentale » appliquée à chaque étape, $r_k \wedge r_{k+1} = r_{k+1} \wedge r_{k+2}$. En enchaînant, $$ a \wedge b = r_0 \wedge r_1 = r_1 \wedge r_2 = \cdots = r_{N-1} \wedge r_N = r_{N-1} \wedge 0 = r_{N-1}. $$

Méthode — Calculer $a \wedge b$ par l'algorithme d'Euclide

Supposer $0 < b \leq a$. Tabuler les divisions euclidiennes successives $r_k = r_{k+1} \, q_{k+1} + r_{k+2}$ avec $0 \leq r_{k+2} < r_{k+1}$, en partant de $a = b \, q_1 + r_2$. S'arrêter dès qu'un reste est nul ; le dernier reste non nul est $a \wedge b$. Pour $a, b \in \mathbb{Z}$ généraux, les remplacer par $|a|, |b|$.

Exemple

Calculer $1542 \wedge 58$.

Correction

On applique l'algorithme d'Euclide : $$ \begin{aligned} 1542 &= 26 \cdot 58 + 34, \\ 58 &= 1 \cdot 34 + 24, \\ 34 &= 1 \cdot 24 + 10, \\ 24 &= 2 \cdot 10 + 4, \\ 10 &= 2 \cdot 4 + 2, \\ 4 &= 2 \cdot 2 + 0. \end{aligned} $$ Le dernier reste non nul est $2$, donc $1542 \wedge 58 = 2$.

Définition — Plus petit commun multiple (PPCM)

Soient $a, b \in \mathbb{N}^*$. Le plus petit commun multiple de $a$ et $b$, noté $a \vee b$, est le plus petit élément de $\{m \in \mathbb{N}^* : a \mid m \text{ et } b \mid m\}$ pour l'ordre naturel $\leq$ sur $\mathbb{N}^*$. L'ensemble est non vide (il contient $a b$). Par convention $0 \vee b := 0$, et pour $a, b \in \mathbb{Z}$, $a \vee b := |a| \vee |b|$.

Proposition — Les multiples communs sont les multiples du PPCM

Pour tout $a, b \in \mathbb{N}^*$, $$ \textcolor{colorprop}{a \mathbb{Z} \cap b \mathbb{Z} = (a \vee b) \mathbb{Z},} $$ de manière équivalente : $a \mid n$ et $b \mid n \iff (a \vee b) \mid n$. Donc $a \vee b$ est aussi le plus petit multiple commun pour l'ordre de divisibilité $\mid$.

Preuve

Posons $m = a \vee b$.

$(\supset)$ $m$ est un multiple commun de $a$ et $b$, donc tout multiple de $m$ est un multiple commun.
$(\subset)$ Soit $n$ un multiple commun. La division euclidienne donne $n = m q + r$ avec $0 \leq r < m$. Alors $r = n - m q$ est un multiple commun de $a$ et $b$ ; comme $0 \leq r < m$ et que $m$ est le plus petit multiple commun strictement positif, $r = 0$. Donc $n = m q \in m \mathbb{Z}$.

Proposition — Relation PGCD-PPCM

Pour tout $a, b \in \mathbb{Z}$, $$ \textcolor{colorprop}{(a \wedge b)(a \vee b) = |a b|.} $$ (La démonstration la plus propre lit les exposants dans la décomposition en facteurs premiers de $a$ et $b$ via l'identité $\min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \beta$ ; on admet la formule.)

Exemple

$12 \vee 18 = 36$, et $12 \cdot 18 = 216 = 6 \cdot 36 = (12 \wedge 18)(12 \vee 18)$.

Compétences à pratiquer

PGCD, algorithme d'Euclide et PPCM

V.3 Nombres premiers

Les nombres premiers sont les atomes multiplicatifs de $\mathbb{N}^*$ : tout $n \geq 2$ est un produit de nombres premiers. On donne la définition, on démontre le théorème classique d'infinitude d'Euclide, on présente le crible d'Ératosthène, et on énonce l'existence et l'unicité de la décomposition en facteurs premiers, dont la démonstration dépasse notre champ ici. La décomposition donne ensuite une façon nette de lire le PGCD et le PPCM.

Signaler une erreur

Définition — Nombre premier, nombre composé

Un entier naturel $p \geq 2$ est dit premier si ses seuls diviseurs dans $\mathbb{N}^*$ sont $1$ et $p$ (de manière équivalente, $\operatorname{div}(p) = \{\pm 1, \pm p\}$). On note $\mathbb{P}$ l'ensemble des nombres premiers. Un entier naturel $n \geq 2$ qui n'est pas premier est dit composé : il admet un diviseur $d$ avec $1 < d < n$. L'entier $1$ n'est, par convention, ni premier ni composé.

Exemple

Les premiers nombres premiers sont $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, \dots$. L'entier $4 = 2 \cdot 2$ est composé. (L'exclusion de $1$ des nombres premiers est nécessaire pour garder l'unicité de la décomposition en facteurs premiers : sinon $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3$, etc.)

Proposition — Existence d'un diviseur premier

Tout entier $n \geq 2$ admet au moins un diviseur premier.

Preuve

L'ensemble $D = \{d \in \mathbb{N} : d \geq 2 \text{ et } d \mid n\}$ est non vide (il contient $n$) et minoré par $2$, donc admet un plus petit élément $p_0$. Si $p_0$ était composé, il aurait un diviseur $d$ avec $1 < d < p_0$ ; alors $d \mid n$ (transitivité), donc $d \in D$ avec $d < p_0$ — ce qui contredit la minimalité. Donc $p_0$ est premier, et $p_0 \mid n$.

Théorème — Infinitude des nombres premiers

L'ensemble $\mathbb{P}$ des nombres premiers est infini.

Preuve

Démonstration classique d'Euclide, par l'absurde. Supposons $\mathbb{P}$ fini, disons $\mathbb{P} = \{p_1, \dots, p_r\}$. Considérons $N = p_1 \, p_2 \cdots p_r + 1$. Comme $N \geq 2$, $N$ admet un diviseur premier $p_k$. Alors $p_k$ divise à la fois $N$ et $p_1 \cdots p_r$, donc $p_k$ divise leur différence $N - p_1 \cdots p_r = 1$. Mais un nombre premier est $\geq 2$, donc ne peut pas diviser $1$ — contradiction. Donc $\mathbb{P}$ est infini.

Méthode — Crible d'Ératosthène

Pour lister tous les nombres premiers $\leq N$ (pour un $N \geq 2$ donné) :
Étape 1. Écrire les entiers $2, 3, 4, \dots, N$ dans un tableau.
Étape 2. Prendre le plus petit entier non rayé $p$. Alors $p$ est premier ; rayer tous ses multiples propres $2p, 3p, \dots \leq N$.
Étape 3. Répéter jusqu'à $p > \sqrt{N}$. Tout entier $\leq N$ non rayé est alors premier.
Pourquoi $\sqrt{N}$ suffit. Si $n \leq N$ est composé, on écrit $n = a b$ avec $a \leq b$ ; alors $a \leq \sqrt{n} \leq \sqrt{N}$, donc $n$ est rayé par un premier $\leq \sqrt{N}$.

Exemple — Premiers $\leq 30$ par le crible

$\sqrt{30} < 6$, donc les nombres premiers servant à rayer sont $2, 3, 5$. Après avoir rayé les multiples de $2$, puis de $3$, puis de $5$, les survivants sont $$ \textcolor{colorprop}{\mathbb{P} \cap [\![ 2, 30 ]\!] = \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29\}.} $$ Total : $10$ nombres premiers $\leq 30$.

Théorème — Existence et unicité de la décomposition en facteurs premiers

Tout entier $n \geq 2$ s'écrit comme produit de nombres premiers, $$ \textcolor{colorprop}{n = p_1^{\alpha_1} \, p_2^{\alpha_2} \cdots p_s^{\alpha_s},} $$ avec $p_1 < p_2 < \cdots < p_s$ premiers et $\alpha_1, \dots, \alpha_s \in \mathbb{N}^*$, et cette écriture est unique (les nombres premiers et leurs exposants sont déterminés par $n$). On admet ce théorème ; sa démonstration dépasse notre champ.

Exemple

$360 = 2^3 \cdot 3^2 \cdot 5$ et $84 = 2^2 \cdot 3 \cdot 7$. Ces deux écritures sont les seules décompositions en facteurs premiers de $360$ et $84$.

Méthode — Calculer le PGCD et le PPCM par la décomposition

Écrire $a$ et $b$ en décomposition sur la même liste de premiers $p_1, \dots, p_s$ (avec l'exposant $0$ là où un premier est absent) : $a = \prod_i p_i^{\alpha_i}$, $b = \prod_i p_i^{\beta_i}$. Alors $$ \textcolor{colorprop}{a \wedge b = \prod_i p_i^{\min(\alpha_i, \beta_i)}, \qquad a \vee b = \prod_i p_i^{\max(\alpha_i, \beta_i)}.} $$ Exemple : $360 = 2^3 \cdot 3^2 \cdot 5^1 \cdot 7^0$ et $84 = 2^2 \cdot 3^1 \cdot 5^0 \cdot 7^1$ donnent $360 \wedge 84 = 2^2 \cdot 3^1 = 12$ et $360 \vee 84 = 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$, avec $12 \cdot 2520 = 30240 = 360 \cdot 84$.

Compétences à pratiquer

Nombres premiers

VI Exercices de colle

Compétences à pratiquer

Travailler un exercice de colle ★
Travailler un exercice de colle ★★
Travailler un exercice de colle ★★★

VII Problèmes d'écrit

Compétences à pratiquer

Travailler un problème d'écrit ★
Travailler un problème d'écrit ★★
Travailler un problème d'écrit ★★★
Quiz

Devoir facile : sommes de coefficients binomiaux et de produits consécutifs

3 exercices, sur 20 points. Durée indicative : 1 h 30.

À traiter sur papier, puis à photographier : la correction est automatique, par IA.

Ce contrôle ne modifie pas la maîtrise du chapitre, quelle que soit la note.

Aucun exercice composé.

Devoir difficile : inversion de Pascal et formule de Faulhaber

3 exercices, sur 20 points. Durée indicative : 3 h.

À traiter sur papier, puis à photographier : la correction est automatique, par IA.

Ce contrôle ne modifie pas la maîtrise du chapitre, quelle que soit la note.

Aucun exercice composé.

Aller à la section