CommeUnJeu · L1 MPSI

Sommes, produits et coefficients binomiaux

⌚ ~91 min ▢ 11 blocs ✓ 39 exercices ➣ Prérequis : Logique, Formule du binôme de Newton

Ce chapitre est un atelier. On n'y introduit pas une théorie profonde ; on y muscle les outils de calcul nécessaires à tous les chapitres qui suivent. Trois outils s'aiguisent ici. Sommes (avec la notation compacte $\sum$) : comment les manipuler, changement d'indice, simplification télescopique, sommes doubles. Produits et factorielle (avec $\prod$) : comment fonctionne l'analogue multiplicatif, la factorielle $n!$, les produits télescopiques. Coefficients binomiaux : $\binom{n}{p}$, le triangle de Pascal, et la fameuse formule $(a+b)^n$.
Le plan se déroule en trois mouvements, chacun indépendant des autres, chacun court. On ira vite sur ce que les étudiants ont déjà rencontré au lycée (factorielles, binôme pour les petits $n$) ; on prendra son temps sur le matériel vraiment nouveau (sommes télescopiques, sommes doubles, formule du binôme). De nombreuses démonstrations de ce chapitre se font par récurrence sur $n$, ou par manipulation soignée d'indices --- techniques maîtrisées au chapitre de logique ; on les applique ici. Le chapitre compagnon Propriétés de $\mathbb{R}$ (côté Analyse) traite le versant ordonné : inégalités, valeur absolue, partie entière, borne supérieure/inférieure. Convention pédagogique. Pour clarifier une identité avec $\sum$, on écrira parfois la forme formelle et la forme développée (termes écrits avec des \texttt{+}) sur deux lignes consécutives, afin que le lecteur voie à quoi ressemble chaque terme.

I Sommes

La notation $\sum$ est un raccourci : elle abrège une somme qu'il serait pénible d'écrire en extension. On commence par poser ses règles : comment fonctionne l'indice muet, comment éclater une somme ou décaler l'indice, comment deux termes consécutifs se télescopent. Les cinq sous-sections de cette section exercent ces mécaniques sur des exemples classiques ; les chapitres ultérieurs s'en serviront partout.

I.1 Notation sigma

Étant donné une liste finie de réels $a_m, a_{m+1}, \dots, a_n$, leur somme $a_m + a_{m+1} + \dots + a_n$ se note $\sum_{k=m}^{n} a_k$. La variable $k$ est un indice muet : elle parcourt les entiers de $m$ à $n$ (inclus), et la valeur de la somme ne dépend pas du nom de la lettre ($k$, $i$, $j$, $\ell$ donnent la même somme). Deux règles élémentaires régissent l'interaction de $\sum$ avec l'addition et la multiplication par un scalaire.

Définition — Notation sigma

Pour $m, n \in \mathbb{Z}$ et $(a_k)$ une famille de réels indexée par les entiers, la somme $\sum_{k=m}^{n} a_k$ est définie comme suit.

Si $m \le n$ : $$ \sum_{k=m}^{n} a_k = a_m + a_{m+1} + \dots + a_n. $$
Si $m > n$ (cas de la somme vide) : $$ \sum_{k=m}^{n} a_k = 0. $$

Exemple

$\sum_{k=1}^{5} k = 1 + 2 + 3 + 4 + 5 = 15$.

Proposition — Linéarité de $\sum$

Pour $m, n \in \mathbb{Z}$ avec $m \le n$, $\lambda, \mu \in \mathbb{R}$, et $(a_k)_{m \le k \le n}$, $(b_k)_{m \le k \le n}$ deux familles finies de réels : $$ \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}} $$ En particulier, $\sum (a_k + b_k) = \sum a_k + \sum b_k$ et $\sum \lambda a_k = \lambda \sum a_k$.

Proposition — Découpage et relation de Chasles

Pour $m, p, n \in \mathbb{Z}$ avec $m \le p < n$, et $(a_k)_{m \le k \le n}$ une famille finie de réels : $$ \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_n &= (a_m + \dots + a_p) + (a_{p+1} + \dots + a_n). \end{aligned}} $$

Compétences à pratiquer

Lire et évaluer une somme avec $\sum$

I.2 Changement d'indice

L'indice muet peut être renommé (il reste un entier) ou décalé par une transformation additive ou symétrique. Deux changements d'indice sont omniprésents : le décalage $j = k - p$ (renumérotation par $p$) et la réflexion $j = n - k$ (compter en sens inverse). Chacun préserve la somme --- il ne fait que reformuler les bornes.

Proposition — Changement d'indice

Soient $m \le n$ deux entiers (l'ensemble d'indices $\{m, m+1, \dots, n\}$ est donc non vide).

Décalage : pour $p \in \mathbb{Z}$, 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 = n - k$ (soit $k = n - j$), qui ramène la borne inférieure à $0$, $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=m}^{n} a_k &= \sum_{j=0}^{n-m} a_{n-j} \\ a_m + a_{m+1} + \dots + a_{n-1} + a_n &= a_n + a_{n-1} + \dots + a_{m+1} + a_m \end{aligned}} $$ ou, de façon équivalente, sous la forme qui préserve les bornes, avec $j = n + m - k$ (soit $k = n + m - j$), $$ \textcolor{colorprop}{ \sum_{k=m}^{n} a_k = \sum_{j=m}^{n} a_{n+m-j} } $$ qui laisse les bornes initiales $m$ et $n$ inchangées.

Exemple

Réécrire $\sum_{k=3}^{n+3} k^2$ avec un indice de sommation commençant à $0$.

Correction

Posons $j = k - 3$. Alors $k = j + 3$, et lorsque $k$ parcourt $3$ à $n+3$, $j$ parcourt $0$ à $n$. D'où $$ \sum_{k=3}^{n+3} k^2 = \sum_{j=0}^{n} (j+3)^2 = \sum_{j=0}^{n} (j^2 + 6j + 9). $$

Exemple

Montrer que $\sum_{k=0}^{n} a_k = \sum_{k=0}^{n} a_{n-k}$.

Correction

On applique la réflexion $j = n - k$ : $k = n - j$, et lorsque $k$ parcourt $0$ à $n$, $j$ parcourt $n$ à $0$, donc $j$ prend les mêmes valeurs que $k$. D'où $$ \sum_{k=0}^{n} a_k = \sum_{j=0}^{n} a_{n-j} = \sum_{k=0}^{n} a_{n-k} $$ (la dernière égalité renomme l'indice muet en $k$).

Compétences à pratiquer

Translater et réfléchir un indice

I.3 Sommes classiques

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. Et une factorisation, duale algébrique de la somme géométrique : $a^n - b^n$. Ces cinq formules sous-tendent tout calcul ultérieur.

Theorem — Sommes classiques

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

Somme des 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 &= \left(\frac{n(n+1)}{2}\right)^2 \\ 1^3 + 2^3 + 3^3 + \dots + n^3 &= \left(\frac{n(n+1)}{2}\right)^2. \end{aligned}} $$

Somme géométrique. Pour $x \in \mathbb{R}$ avec $x \ne 1$ et $n \in \mathbb{N}$ : $$ \textcolor{colorprop}{\begin{aligned} \sum_{k=0}^{n} x^k &= \frac{1 - x^{n+1}}{1 - x} = \frac{x^{n+1} - 1}{x - 1} \\ 1 + x + x^2 + \dots + x^n &= \frac{1 - x^{n+1}}{1 - x}. \end{aligned}} $$ Pour $x = 1$ : $\sum_{k=0}^{n} 1 = n+1$.

Preuve

Les démonstrations utilisent deux idées récurrentes : le changement d'indice (pour la somme des entiers) et le télescopage d'une différence $u_{k+1} - u_k$ suivi du développement polynomial (pour les sommes des carrés et des cubes, et pour la somme géométrique). On utilise ici le télescopage par anticipation : il est énoncé et démontré en détail dans la Proposition de télescopage de la sous-section suivante (Sommes télescopiques ci-dessous) ; on n'invoque ici que sa conclusion $\sum_{k=m}^{n}(u_{k+1}-u_k) = u_{n+1} - u_m$.

Somme des entiers --- changement d'indice. Soit $S = \sum_{i=0}^{n} i$. Avec le changement d'indice $i \mapsto n - i$, la même somme s'écrit aussi $S = \sum_{i=0}^{n} (n - i)$. Additionnons les deux expressions de $S$ : $$ \begin{aligned} 2S &= \sum_{i=0}^{n} i + \sum_{i=0}^{n} (n - i) \\ &= \sum_{i=0}^{n} \big(i + (n - i)\big) && \text{(linéarité)} \\ &= \sum_{i=0}^{n} n && \text{(simplification : } i + (n-i) = n\text{)} \\ &= n \sum_{i=0}^{n} 1 && \text{(linéarité)} \\ &= n (n+1) && \text{(} \sum_{i=0}^{n} 1 = n+1 \text{)}. \end{aligned} $$ D'où $\displaystyle\sum_{k=0}^{n} k = \frac{n(n+1)}{2}$.
Somme des carrés --- télescopage avec les cubes. On applique le télescopage à $u_k = k^3$ et on enchaîne les opérations : $$ \begin{aligned} \sum_{k=0}^{n} \big((k+1)^3 - k^3\big) &= (n+1)^3 && \text{(télescopage, } u_k = k^3 \text{)} \\ \sum_{k=0}^{n} (3k^2 + 3k + 1) &= (n+1)^3 && \text{(développer } (k+1)^3 - k^3\text{)} \\ 3 \sum_{k=0}^{n} k^2 + 3 \sum_{k=0}^{n} k + \sum_{k=0}^{n} 1 &= (n+1)^3 && \text{(linéarité)} \\ 3 \sum_{k=0}^{n} k^2 + 3 \cdot \frac{n(n+1)}{2} + (n+1) &= (n+1)^3 && \text{(sommes connues)} \\ 3 \sum_{k=0}^{n} k^2 &= (n+1)^3 - \frac{3n(n+1)}{2} - (n+1) && \text{(isolation)} \\ 6 \sum_{k=0}^{n} k^2 &= 2(n+1)^3 - 3n(n+1) - 2(n+1) && \text{(}\times 2\text{)} \\ 6 \sum_{k=0}^{n} k^2 &= (n+1)\big[2(n+1)^2 - 3n - 2\big] && \text{(factoriser } (n+1) \text{)} \\ 6 \sum_{k=0}^{n} k^2 &= (n+1)\big[2n^2 + 4n + 2 - 3n - 2\big] && \text{(développer } 2(n+1)^2 = 2n^2 + 4n + 2 \text{)} \\ 6 \sum_{k=0}^{n} k^2 &= (n+1)(2n^2 + n) && \text{(regrouper les termes du crochet)} \\ 6 \sum_{k=0}^{n} k^2 &= n(n+1)(2n+1) && \text{(factoriser } n \text{).} \end{aligned} $$ D'où $\displaystyle\sum_{k=0}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$.
Somme des cubes --- même astuce avec $(k+1)^4 - k^4$. On applique le télescopage à $u_k = k^4$, on développe $(k+1)^4 - k^4 = 4k^3 + 6k^2 + 4k + 1$, et on réutilise $\sum k$ et $\sum k^2$ : $$ \begin{aligned} \sum_{k=0}^{n} \big((k+1)^4 - k^4\big) &= (n+1)^4 && \text{\doublecolumnscriptsize (télescopage, } u_k = k^4 \text{)} \\ \sum_{k=0}^{n} (4k^3 + 6k^2 + 4k + 1) &= (n+1)^4 && \text{\doublecolumnscriptsize (développement)} \\ 4 \sum k^3 + 6 \sum k^2 + 4 \sum k + \sum 1 &= (n+1)^4 && \text{\doublecolumnscriptsize (linéarité)} \\ 4 \sum k^3 + n(n+1)(2n+1) \\ \quad + 2n(n+1) + (n+1) &= (n+1)^4 && \text{\doublecolumnscriptsize (sommes connues)} \\ 4 \sum k^3 &= (n+1)^4 - n(n+1)(2n+1) \\ &\quad - 2n(n+1) - (n+1) && \text{\doublecolumnscriptsize (isolation)} \\ 4 \sum k^3 &= (n+1)\big[(n+1)^3 - n(2n+1) - 2n - 1\big] && \text{\doublecolumnscriptsize (factoriser } (n+1) \text{)} \\ 4 \sum k^3 &= (n+1)\big[n^3 + 3n^2 + 3n + 1 \\ &\quad - 2n^2 - n - 2n - 1\big] && \text{\doublecolumnscriptsize (développer } (n+1)^3, n(2n+1)\text{)} \\ 4 \sum k^3 &= (n+1)(n^3 + n^2) && \text{\doublecolumnscriptsize (regrouper les termes du crochet)} \\ 4 \sum k^3 &= n^2(n+1)^2 && \text{\doublecolumnscriptsize (factoriser } n^2 \text{).} \end{aligned} $$ D'où $\displaystyle\sum_{k=0}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^2$.
Somme géométrique --- télescopage après multiplication par $(1-x)$. Pour $x \ne 1$ : $$ \begin{aligned} (1 - x) \sum_{k=0}^{n} x^k &= \sum_{k=0}^{n} x^k - x \sum_{k=0}^{n} x^k && \text{(distribution)} \\ &= \sum_{k=0}^{n} x^k - \sum_{k=0}^{n} x^{k+1} && \text{(faire entrer dans la somme)} \\ &= \sum_{k=0}^{n} (x^k - x^{k+1}) && \text{(linéarité)} \\ &= x^0 - x^{n+1} && \text{(télescopage, } u_k = x^k \text{)} \\ &= 1 - x^{n+1}. \end{aligned} $$ On divise par $1 - x$ : $\displaystyle\sum_{k=0}^{n} x^k = \frac{1 - x^{n+1}}{1 - x}$.

Exemple

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

Correction

$\sum_{k=1}^{100} k = 100 \cdot 101 / 2 = 5050$.

Exemple

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

Correction

Somme géométrique avec $x = 2$ : $\sum_{k=0}^{n} 2^k = (2^{n+1} - 1)/(2 - 1) = 2^{n+1} - 1$.

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

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

Preuve

Posons $u_k = a^{n-k} b^k$. La distribution de $(a - b)$ sur la somme produit une somme télescopique : $$ (a - b) \sum_{k=0}^{n-1} a^{n-1-k} b^k = \sum_{k=0}^{n-1} \big( a^{n-k} b^k - a^{n-1-k} b^{k+1} \big) = \sum_{k=0}^{n-1} (u_k - u_{k+1}) = u_0 - u_n = a^n - b^n. $$

Compétences à pratiquer

Reconnaître et appliquer les formules classiques
Combiner les sommes classiques par linéarité

I.4 Sommes télescopiques

Une somme télescopique est une somme de différences consécutives $u_{k+1} - u_k$, dans laquelle tous les termes intermédiaires se simplifient deux à deux --- seuls les bords subsistent. L'astuce est de reconnaître quand un terme s'écrit comme une telle différence, car alors la somme entière s'effondre à deux termes.

Proposition — Somme télescopique

Pour toute suite $(u_k)$ et entiers $m \le n$ : $$ \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}} $$

Preuve

Trois perspectives sur le même résultat : deux démonstrations formelles et une visuelle.

Démonstration 1 --- récurrence sur $n$ (avec $m$ fixé). Initialisation. Pour $n = m$, la somme se réduit à un seul terme : $\sum_{k=m}^{m} (u_{k+1} - u_k) = u_{m+1} - u_m$, ce qui vaut $u_{n+1} - u_m$ pour $n=m$. $\checkmark$ Hérédité. On suppose la formule au rang $n$. Au rang $n+1$ : $$ \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{(Chasles, isoler le dernier terme)} \\ &= (u_{n+1} - u_m) + (u_{n+2} - u_{n+1}) && \text{(hypothèse de récurrence)} \\ &= u_{n+2} - u_m && \text{(simplification).} \end{aligned} $$ L'hérédité est établie ; le résultat suit pour tout $n \ge m$.
Démonstration 2 --- changement d'indice. $$ \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{(changement d'indice } j = k+1 \text{)} \\ &= u_{n+1} + \sum_{j=m+1}^{n} u_j - \sum_{k=m}^{n} u_k && \text{(Chasles, isoler } j=n+1\text{)} \\ &= u_{n+1} + \sum_{j=m+1}^{n} u_j - u_m - \sum_{k=m+1}^{n} u_k && \text{(Chasles, isoler } k=m\text{)} \\ &= u_{n+1} - u_m && \text{(les deux sommes intérieures sont égales --- indice muet).} \end{aligned} $$
Idée visuelle --- développer et regarder les termes se simplifier. En écrivant la somme terme à terme : $$ \sum_{k=m}^{n} (u_{k+1} - u_k) = (u_{m+1} - u_m) + (u_{m+2} - u_{m+1}) + \dots + (u_{n+1} - u_n). $$ Tout $u_j$ avec $m+1 \le j \le n$ apparaît exactement deux fois --- une fois avec un signe $+$, une fois avec un signe $-$ --- et les deux occurrences se compensent. Seuls $-u_m$ au début et $+u_{n+1}$ à la fin survivent : la somme se réduit à $u_{n+1} - u_m$.

Exemple

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

Correction

On décompose : $\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}$. En posant $u_k = -\frac{1}{k}$, le terme général est $u_{k+1} - u_k$. Par la formule télescopique $$ \sum_{k=1}^{n} \frac{1}{k(k+1)} = u_{n+1} - u_1 = -\frac{1}{n+1} + 1 = \frac{n}{n+1}. $$

Exemple

Calculer $\displaystyle \sum_{k=1}^{n} \ln\!\left(1 + \frac{1}{k}\right)$.

Correction

$\ln(1 + 1/k) = \ln((k+1)/k) = \ln(k+1) - \ln(k)$. En posant $u_k = \ln(k)$, le terme général est $u_{k+1} - u_k$. D'où $$ \sum_{k=1}^{n} \ln\!\left(1 + \frac{1}{k}\right) = \ln(n+1) - \ln(1) = \ln(n+1). $$

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

Repérer le motif $u_{k+1} - u_k$ (différence d'un seul pas). Deux déclencheurs fréquents :

Fraction rationnelle $\dfrac{1}{k(k+1)}$ : décomposition en éléments simples qui donne $\dfrac{1}{k(k+1)} = \dfrac{1}{k} - \dfrac{1}{k+1}$, différence d'un pas avec $u_k = -\dfrac{1}{k}$. (Pour des écarts plus larges $\dfrac{1}{k(k+a)}$ avec $a \ge 2$, la décomposition donne une différence à $a$ pas --- traité dans le « pour aller plus loin » des exercices.)
Logarithme d'un rapport : $\ln\!\big(f(k+1)/f(k)\big) = \ln f(k+1) - \ln f(k)$.

Une fois le terme général reconnu sous la forme $u_{k+1} - u_k$, la formule effondre la somme à deux termes : $u_{n+1} - u_m$.

Compétences à pratiquer

Décomposer puis télescoper

I.5 Sommes doubles

Une somme double $\sum_{i,j}$ parcourt un rectangle (ou un triangle) de couples $(i \,;\, j)$. Trois simplifications : quand le rectangle est plein et que le terme général se factorise, la somme est un produit de deux sommes simples ; on peut permuter l'ordre des sommations (Fubini pour les sommes) ; pour les triangles, on échange les rôles des variables interne et externe.

Proposition — Identités sur les sommes doubles

Permutation (Fubini) : $$ \textcolor{colorprop}{\sum_{i=m}^{n} \sum_{j=p}^{q} a_{i,j} = \sum_{j=p}^{q} \sum_{i=m}^{n} a_{i,j}}. $$
Factorisation (terme séparable) : si $a_{i,j} = b_i c_j$ $$ \textcolor{colorprop}{\sum_{i=m}^{n} \sum_{j=p}^{q} b_i c_j = \left(\sum_{i=m}^{n} b_i\right)\!\left(\sum_{j=p}^{q} c_j\right)}. $$
Triangle : échange interne/externe : $$ \textcolor{colorprop}{\sum_{1 \le i \le j \le n} a_{i,j} = \sum_{j=1}^{n} \sum_{i=1}^{j} a_{i,j} = \sum_{i=1}^{n} \sum_{j=i}^{n} a_{i,j}}. $$

Preuve

Les trois identités reposent toutes sur la commutativité et l'associativité de l'addition sur $\mathbb{R}$ --- qui permettent de réordonner une somme finie librement --- combinées à la linéarité de $\sum$.

Permutation (Fubini) --- développer et re-collecter. La somme double rectangulaire énumère chaque case $(i,j)$ du rectangle d'indices $(n - m + 1) \times (q - p + 1)$ exactement une fois. Les deux imbrications listent les mêmes cases ; les sommes finies des mêmes nombres sont égales : $$ \sum_{i=m}^{n} \sum_{j=p}^{q} a_{i,j} = \sum_{\substack{m \le i \le n \\ p \le j \le q}} a_{i,j} = \sum_{j=p}^{q} \sum_{i=m}^{n} a_{i,j}. $$
Factorisation (terme séparable). Fixons $i$ dans la somme interne et appliquons la linéarité ($b_i$ est constant par rapport à $j$) : $$ \begin{aligned} \sum_{i=m}^{n} \sum_{j=p}^{q} b_i c_j &= \sum_{i=m}^{n} \left[ b_i \sum_{j=p}^{q} c_j \right] && \text{(linéarité, } b_i \text{ ne dépend pas de } j\text{)} \\ &= \left(\sum_{j=p}^{q} c_j\right) \sum_{i=m}^{n} b_i && \text{(linéarité, le facteur entre parenthèses ne dépend pas de } i\text{)} \\ &= \left(\sum_{i=m}^{n} b_i\right) \left(\sum_{j=p}^{q} c_j\right). \end{aligned} $$
Triangle : échange interne/externe. L'ensemble $\{(i,j) : 1 \le i \le j \le n\}$ se partitionne de deux manières équivalentes :
- en ordonnant sur $j$ à l'extérieur : pour chaque $j \in \{1, \dots, n\}$, l'indice interne $i$ parcourt $\{1, \dots, j\}$, donnant $\sum_{j=1}^{n} \sum_{i=1}^{j} a_{i,j}$ ;
- en ordonnant sur $i$ à l'extérieur : pour chaque $i \in \{1, \dots, n\}$, l'indice interne $j$ parcourt $\{i, \dots, n\}$, donnant $\sum_{i=1}^{n} \sum_{j=i}^{n} a_{i,j}$.
Les deux partitions énumèrent chaque couple $(i,j)$ avec $1 \le i \le j \le n$ exactement une fois, donc les deux sommes doubles sont égales à $\sum_{1 \le i \le j \le n} a_{i,j}$.

Exemple

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

Correction

Le terme $ij$ se sépare. Factorisation : $$ \sum_{i=1}^{n} \sum_{j=1}^{n} ij = \left(\sum_{i=1}^{n} i\right)\!\left(\sum_{j=1}^{n} j\right) = \left(\frac{n(n+1)}{2}\right)^2. $$

Exemple

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

Correction

Triangle des couples $(i \,;\, j)$ avec $1 \le i \le j \le n$. Somme de $1$ sur ce triangle = nombre de couples = $n(n+1)/2$. Vérification en ordonnant sur $j$ : $\sum_{j=1}^{n} \sum_{i=1}^{j} 1 = \sum_{j=1}^{n} j = n(n+1)/2$.

Méthode — Calculer une somme double

Trois réflexes, dans cet ordre :

Terme séparable : si $a_{i,j} = b_i c_j$, on factorise $\sum_{i,j} b_i c_j = \bigl(\sum_i b_i\bigr)\bigl(\sum_j c_j\bigr)$ --- deux sommes simples.
Domaine triangulaire : on choisit la somme interne de sorte que les bornes de la variable interne soient visibles. Avec $1 \le i \le j \le n$, ordonner sur $j$ à l'extérieur donne $\sum_{j=1}^{n} \sum_{i=1}^{j} a_{i,j}$ ; ordonner sur $i$ à l'extérieur donne $\sum_{i=1}^{n} \sum_{j=i}^{n} a_{i,j}$. Choisir celle qui rend la somme interne reconnaissable parmi les sommes classiques.
Rectangle bloqué : si aucun des deux points précédents ne suffit, on permute l'ordre de sommation (Fubini) et on réessaie --- souvent la forme permutée révèle une structure séparable ou une somme interne reconnaissable.

Compétences à pratiquer

Permuter et factoriser des sommes doubles

II Produits

La notation $\prod$ est la cousine multiplicative de $\sum$. La même machinerie s'applique : indice muet, changement d'indice, simplification télescopique. Le seul changement structurel est la convention du produit vide (qui vaut $1$, pas $0$). Le produit le plus utile est la factorielle.

II.1 Notation pi et factorielle

La factorielle $n!$ compte le nombre d'ordres distincts de $n$ objets. Algébriquement, c'est le produit des $n$ premiers entiers strictement positifs. Elle apparaîtra partout : coefficients binomiaux, développements de Taylor, dénombrement.

Définition — Notation pi$\virgule$ factorielle

Pour $m, n \in \mathbb{Z}$ et une famille $(a_k)$ de réels indexée par les entiers, le produit $\prod_{k=m}^{n} a_k$ est défini comme suit.
- Si $m \le n$ : $$ \prod_{k=m}^{n} a_k = a_m \cdot a_{m+1} \cdot \dots \cdot a_n. $$
- Si $m > n$ (cas du produit vide) : $\prod_{k=m}^{n} a_k = 1$.
Pour $n \in \mathbb{N}$, la factorielle de $n$ est $$ \textcolor{colordef}{n!} = \prod_{k=1}^{n} k = 1 \cdot 2 \cdot 3 \cdots n. $$ Par convention, $\textcolor{colordef}{0!} = 1$ (produit vide).

Exemple

$0! = 1$, $1! = 1$, $2! = 2$, $3! = 6$, $4! = 24$, $5! = 120$.
$10! = 3628800$ (déjà grand).

Proposition — Récurrence et rapports de factorielles

Pour $n \in \mathbb{N}$ : $$ \textcolor{colorprop}{(n+1)! = (n+1) \cdot n!}. $$ Pour $n \ge p \ge 0$ : $$ \textcolor{colorprop}{\frac{n!}{p!} = (p+1)(p+2)\cdots n = \prod_{k=p+1}^{n} k}. $$

Compétences à pratiquer

Manipuler produits et factorielles

II.2 Produits télescopiques

Analogue multiplicatif de la somme télescopique : un produit de rapports $u_{k+1}/u_k$ s'effondre à deux termes aux bornes. Utile lorsqu'une fraction se réécrit comme un tel rapport.

Proposition — Produit télescopique

Pour une suite $(u_k)$ de réels non nuls et $m \le n$ : $$ \textcolor{colorprop}{\prod_{k=m}^{n} \frac{u_{k+1}}{u_k} = \frac{u_{n+1}}{u_m}}. $$

Exemple

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

Correction

En posant $u_k = k$, le terme général est $u_{k+1}/u_k$. Par le produit télescopique $$ \prod_{k=1}^{n} \frac{k+1}{k} = \frac{u_{n+1}}{u_1} = \frac{n+1}{1} = n+1. $$

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

Repérer le motif $u_{k+1}/u_k$. Cas fréquents :

Rapport explicite de valeurs consécutives : $\dfrac{f(k+1)}{f(k)}$ pour une suite $(f(k))$.
Rapport de factorielles consécutives : $\dfrac{(k+1)!}{k!} = k+1$, donc $\prod_{k=1}^{n}\dfrac{(k+1)!}{k!} = (n+1)!$.
Détour logarithmique : lorsque les facteurs sont positifs, on passe au $\ln$ pour convertir le produit en une somme télescopique de $\ln u_{k+1} - \ln u_k$, puis on ré-exponentie.

Une fois reconnu, le produit s'effondre en $u_{n+1}/u_m$ --- seuls les bords subsistent.

Compétences à pratiquer

Téléscoper un produit

III Coefficients binomiaux

Le coefficient binomial $\binom{n}{k}$ compte le nombre de façons de choisir $k$ objets parmi $n$ (sans ordre). Le même nombre apparaît comme coefficient de $a^{n-k}b^k$ dans le développement de $(a+b)^n$. Les deux visages --- combinatoire et algébrique --- sont équivalents, et l'on utilisera celui qui convient. La section culmine sur la formule du binôme, l'identité algébrique la plus célèbre des mathématiques élémentaires.

III.1 Définition et propriétés

On définit $\binom{n}{k}$ par sa formule factorielle, puis on observe ses trois propriétés fondamentales : il apparaîtra (dans la formule du binôme prouvée plus bas) comme coefficient de $a^{n-k} b^k$ dans le polynôme symétrique $(a+b)^n$, il est symétrique en $k$ et $n-k$, et il satisfait une relation de récurrence qui donne le triangle de Pascal.

Définition — Coefficient binomial

Pour $n \in \mathbb{N}$ et $k \in \mathbb{Z}$, le coefficient binomial $\binom{n}{k}$ est défini par : $$ \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$ ». L'expression factorielle ci-dessus est la définition ; le fait que ce nombre soit aussi égal au nombre de parties à $k$ éléments d'un ensemble à $n$ éléments est l'interprétation combinatoire, établie séparément par un argument de dénombrement (elle ne fait pas partie de la définition).

Proposition — Valeurs standards des coefficients binomiaux

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

$\textcolor{colorprop}{\binom{n}{0} = \binom{n}{n} = 1}$ (une façon de ne rien choisir ou tout choisir) ;
$\textcolor{colorprop}{\binom{n}{1} = \binom{n}{n-1} = n}$ ($n$ singletons ou $n$ parties auxquelles il manque un élément) ;
pour $n \ge 2$, $\textcolor{colorprop}{\binom{n}{2} = \binom{n}{n-2} = \dfrac{n(n-1)}{2}}$.

Exemple

$\binom{5}{2} = \dfrac{5!}{2!\,3!} = \dfrac{5 \cdot 4}{2} = 10$ --- il y a dix façons de choisir une paire dans un ensemble à $5$ éléments.

Proposition — Symétrie$\virgule$ Pascal$\virgule$ absorption

Pour $n \in \mathbb{N}$ et $k \in \mathbb{Z}$ avec $0 \le k \le n$ :

Symétrie : $\textcolor{colorprop}{\binom{n}{k} = \binom{n}{n-k}}$.
Identité de Pascal : pour $1 \le k \le n-1$, $\textcolor{colorprop}{\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}}$.
Absorption : pour $1 \le k \le n$, $\textcolor{colorprop}{k\binom{n}{k} = n\binom{n-1}{k-1}}$.

Preuve

Le c\oe ur des trois démonstrations est le même : mettre les fractions au même dénominateur à l'aide des identités factorielles $k \cdot (k-1)! = k!$ et $(n-k) \cdot (n-k-1)! = (n-k)!$.

Symétrie. On applique la formule factorielle et on simplifie le second facteur : $$ \begin{aligned} \binom{n}{n-k} &= \frac{n!}{(n-k)! \, \big(n - (n-k)\big)!} && \text{(formule factorielle à l'indice } n-k \text{)} \\ &= \frac{n!}{(n-k)! \, k!} && \text{(simplification : } n - (n-k) = k\text{)} \\ &= \frac{n!}{k! \, (n-k)!} && \text{(échange des facteurs au dénominateur)} \\ &= \binom{n}{k} && \text{(formule factorielle à l'indice } k\text{).} \end{aligned} $$
Pascal. Le dénominateur commun visé est $k!\,(n-k)!$. On multiplie chaque fraction par $1$ de manière à étendre les factorielles : $$ \begin{aligned} \binom{n-1}{k-1} + \binom{n-1}{k} &= \frac{(n-1)!}{(k-1)!\,(n-k)!} + \frac{(n-1)!}{k!\,(n-k-1)!} && \text{\doublecolumnscriptsize (formule factorielle)} \\ &= \frac{k \cdot (n-1)!}{k \cdot (k-1)!\,(n-k)!} + \frac{(n-1)!}{k!\,(n-k-1)!} && \text{\doublecolumnscriptsize (multiplier la 1\textsuperscript{re} fraction par } k/k \text{)} \\ &= \frac{k \cdot (n-1)!}{k!\,(n-k)!} + \frac{(n-1)!}{k!\,(n-k-1)!} && \text{\doublecolumnscriptsize (}k \cdot (k-1)! = k! \text{ au 1\textsuperscript{er} dénom.)} \\ &= \frac{k \cdot (n-1)!}{k!\,(n-k)!} \\ &\quad + \frac{(n-k) \cdot (n-1)!}{k!\,(n-k) \cdot (n-k-1)!} && \text{\doublecolumnscriptsize (multiplier la 2\textsuperscript{e} fraction par } (n-k)/(n-k) \text{)} \\ &= \frac{k \cdot (n-1)!}{k!\,(n-k)!} + \frac{(n-k) \cdot (n-1)!}{k!\,(n-k)!} && \text{\doublecolumnscriptsize (}(n-k) \cdot (n-k-1)! = (n-k)! \text{ au 2\textsuperscript{e} dénom.)} \\ &= \frac{k \cdot (n-1)! + (n-k) \cdot (n-1)!}{k!\,(n-k)!} && \text{\doublecolumnscriptsize (dénominateur commun atteint)} \\ &= \frac{(n-1)! \, \big[k + (n-k)\big]}{k!\,(n-k)!} && \text{\doublecolumnscriptsize (factoriser } (n-1)! \text{)} \\ &= \frac{n \cdot (n-1)!}{k!\,(n-k)!} && \text{\doublecolumnscriptsize (}k + (n-k) = n\text{)} \\ &= \frac{n!}{k!\,(n-k)!} && \text{\doublecolumnscriptsize (}n \cdot (n-1)! = n!\text{)} \\ &= \binom{n}{k}. \end{aligned} $$
Absorption. Même idée, plus simple : faire entrer ou sortir un facteur dans une factorielle. $$ \begin{aligned} k \binom{n}{k} &= \frac{k \cdot n!}{k! \, (n-k)!} && \text{(formule factorielle)} \\ &= \frac{k \cdot n!}{k \cdot (k-1)! \, (n-k)!} && \text{(}k! = k \cdot (k-1)!\text{)} \\ &= \frac{n!}{(k-1)! \, (n-k)!} && \text{(simplifier le facteur } k\text{)} \\ &= \frac{n \cdot (n-1)!}{(k-1)! \, (n-k)!} && \text{(}n! = n \cdot (n-1)!\text{)} \\ &= n \binom{n-1}{k-1}. \end{aligned} $$

Compétences à pratiquer

Démontrer des identités par calcul

III.2 Triangle de Pascal

L'identité de Pascal donne une procédure récursive pour calculer $\binom{n}{k}$ : chaque entrée est la somme des deux au-dessus. Le tableau obtenu est le triangle de Pascal, monument de combinatoire élémentaire.

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 (identité de Pascal).

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

Pour calculer $\binom{n}{k}$ pour de petits $n$, utiliser la récurrence de Pascal :

commencer avec la ligne $0$ : $\binom{0}{0} = 1$ ;
chaque nouvelle ligne commence et finit par $1$ ;
les entrées intérieures sont la somme des deux entrées diagonalement au-dessus.

Pour de plus grands $n$ ou des entrées précises, préférer la formule factorielle.

Compétences à pratiquer

Construire et exploiter le triangle

III.3 Formule du binôme

La formule du binôme exprime $(a+b)^n$ comme combinaison linéaire explicite des monômes $a^{n-k}b^k$ avec coefficients exactement les coefficients binomiaux. C'est l'identité-clef qui relie combinatoire, algèbre et analyse : elle sous-tend les développements de Taylor et de nombreux arguments de dénombrement.

Theorem — Formule du binôme (Newton)

Pour $a, b \in \mathbb{R}$ (ou $\mathbb{C}$) et $n \in \mathbb{N}$ : $$ \textcolor{colorprop}{(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k}. $$

Preuve

Récurrence sur $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} = 1$. $\checkmark$
Hérédité. On suppose la formule au rang $n$. On calcule $(a+b)^{n+1}$ étape par étape : $$ \begin{aligned} (a+b)^{n+1} &= (a+b)\,(a+b)^n && \text{\doublecolumnscriptsize (isoler un facteur)} \\ &= (a+b) \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k && \text{\doublecolumnscriptsize (d'après l'hypothèse de récurrence)} \\ &= a \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k \\ &\quad + b \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k && \text{\doublecolumnscriptsize (distribuer)} \\ &= \sum_{k=0}^{n} \binom{n}{k} a^{n+1-k} b^k \\ &\quad + \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^{k+1} && \text{\doublecolumnscriptsize (faire entrer dans les sommes)} \\ &= \sum_{k=0}^{n} \binom{n}{k} a^{n+1-k} b^k \\ &\quad + \sum_{k=1}^{n+1} \binom{n}{k-1} a^{n+1-k} b^k && \text{\doublecolumnscriptsize (changement d'indice } k \to k+1\text{ dans la 2e somme)} \\ &= a^{n+1} + \sum_{k=1}^{n} \binom{n}{k} a^{n+1-k} b^k \\ &\quad + \sum_{k=1}^{n+1} \binom{n}{k-1} a^{n+1-k} b^k && \text{\doublecolumnscriptsize (isoler } k=0 \text{ dans la 1re somme)} \\ &= a^{n+1} + \sum_{k=1}^{n} \binom{n}{k} a^{n+1-k} b^k \\ &\quad + \sum_{k=1}^{n} \binom{n}{k-1} a^{n+1-k} b^k + b^{n+1} && \text{\doublecolumnscriptsize (isoler } k=n+1 \text{ dans la 2e somme)} \\ &= a^{n+1} + \sum_{k=1}^{n} \Big[\binom{n}{k} + \binom{n}{k-1}\Big] a^{n+1-k} b^k + b^{n+1} && \text{\doublecolumnscriptsize (combiner les deux sommes sur } k=1\text{..}n\text{)} \\ &= a^{n+1} + \sum_{k=1}^{n} \binom{n+1}{k} a^{n+1-k} b^k + b^{n+1} && \text{\doublecolumnscriptsize (identité de Pascal)} \\ &= \sum_{k=0}^{n+1} \binom{n+1}{k} a^{n+1-k} b^k && \text{\doublecolumnscriptsize (réabsorber }a^{n+1}\text{ et }b^{n+1}\text{).} \end{aligned} $$ L'hérédité est établie. Le résultat suit pour tout $n \in \mathbb{N}$.

Exemple

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

Correction

Lire la ligne $n=4$ du triangle de Pascal : $1, 4, 6, 4, 1$. D'où $$ (a+b)^4 = a^4 + 4 a^3 b + 6 a^2 b^2 + 4 a b^3 + b^4. $$

Exemple

Calculer $\sum_{k=0}^{n} \binom{n}{k}$ et $\sum_{k=0}^{n} (-1)^k \binom{n}{k}$.

Correction

On applique la formule du binôme avec $a = b = 1$ : $$ 2^n = (1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^{n-k} 1^k = \sum_{k=0}^{n} \binom{n}{k}. $$ Avec $a = 1, b = -1$, pour $n \ge 1$ : $$ 0 = (1-1)^n = \sum_{k=0}^{n} \binom{n}{k} (-1)^k. $$

Méthode — Appliquer la formule du binôme

Pour un développement $(a+b)^n$ :

lire les coefficients binomiaux dans le triangle de Pascal (petits $n$) ou les calculer par la formule factorielle ;
écrire chaque terme $\binom{n}{k} a^{n-k} b^k$ pour $k = 0, \dots, n$.

Pour une identité de somme faisant intervenir $\binom{n}{k}$, essayer d'évaluer $(a+b)^n$ en des valeurs astucieuses : $a = b = 1$ donne $\sum \binom{n}{k} = 2^n$ ; $a = 1, b = -1$ donne la somme alternée.

Compétences à pratiquer

Appliquer et inverser la formule de Newton