Sommations dans N²

1) Sommations sur un carré

Considérons le « carré » CC de N2\mathbb{N}^2 défini par :

C={(i ; j)∈N2∣0≤i≤n et 0≤j≤n}C = \{(i\,;\,j) \in \mathbb{N}^2 \mid 0 \le i \le n \text{ et } 0 \le j \le n\}

Soit (aij)(i ; j)∈C(a_{ij})_{(i\,;\,j)\in C} une famille de nombres.

Somme des (aij)(a_{ij}) suivant les colonnes (on fait varier l'indice de colonne ii) :

∑i=0n∑j=0naij\sum_{i=0}^{n} \sum_{j=0}^{n} a_{ij}

0 0 1 1 2 2 … … n n i j

Somme des (aij)(a_{ij}) suivant les lignes (on fait varier l'indice de ligne jj) :

∑j=0n∑i=0naij\sum_{j=0}^{n} \sum_{i=0}^{n} a_{ij}

0 0 1 1 2 2 … … n n i j

Bilan :

∑(i,j)∈Caij=∑i=0n∑j=0naij=∑j=0n∑i=0naij\sum_{(i,j)\in C} a_{ij} = \sum_{i=0}^{n} \sum_{j=0}^{n} a_{ij} = \sum_{j=0}^{n} \sum_{i=0}^{n} a_{ij}

Exemples

Exemple 1 — un calcul explicite avec n=2n = 2 et aij=i+ja_{ij} = i + j.

On dresse le tableau des valeurs (colonne ii en abscisse, ligne jj en ordonnée) et on ajoute les sommes partielles :

j\ij \backslash i001122Somme de la ligne
222349
111236
000123
Somme de la colonne36918

Sommer par colonnes donne 3+6+9=183 + 6 + 9 = 18, sommer par lignes donne 9+6+3=189 + 6 + 3 = 18 : on retrouve bien le même total.

Animation — Sommation aij = i + j sur un carré (n = 2)
Cliquez sur « Lancer » pour animer.

Exemple 2 — cas général aij=i+ja_{ij} = i + j.

∑i=0n∑j=0n(i+j)=∑i=0n((n+1) i+n(n+1)2)=(n+1)n(n+1)2+(n+1)n(n+1)2=n(n+1)2\sum_{i=0}^{n}\sum_{j=0}^{n}(i+j)=\sum_{i=0}^{n}\Big((n+1)\,i+\frac{n(n+1)}{2}\Big)=(n+1)\frac{n(n+1)}{2}+(n+1)\frac{n(n+1)}{2}=n(n+1)^2

Pour n=2n=2 : 2×32=182\times 3^2 = 18 ✓.

Exemple 3 — termes à variables séparées : aij=bi cja_{ij}=b_i\,c_j.

Dans un carré, les deux indices sont indépendants, la somme se factorise :

∑(i,j)∈Cbicj=(∑i=0nbi)(∑j=0ncj)\sum_{(i,j)\in C} b_i c_j=\Big(\sum_{i=0}^{n} b_i\Big)\Big(\sum_{j=0}^{n} c_j\Big)

Par exemple, avec aij=i ja_{ij}=i\,j : ∑i=0n∑j=0nij=(n(n+1)2)2\sum_{i=0}^{n}\sum_{j=0}^{n} ij=\Big(\frac{n(n+1)}{2}\Big)^2

et avec aij=xiyja_{ij}=x^i y^j (où x,y≠1x,y\neq 1) : ∑i=0n∑j=0nxiyj=1−xn+11−x⋅1−yn+11−y\sum_{i=0}^{n}\sum_{j=0}^{n} x^i y^j=\frac{1-x^{n+1}}{1-x}\cdot\frac{1-y^{n+1}}{1-y}

À retenir. Sur un carré, les bornes ne dépendent pas de l'autre indice : on peut échanger les deux ∑\sum sans rien changer d'autre.


2) Sommations sur un triangle

Considérons le « triangle » TT de N2\mathbb{N}^2 défini par :

T={(i ; j)∈N2∣0≤i+j≤n}T = \{(i\,;\,j) \in \mathbb{N}^2 \mid 0 \le i + j \le n\}

Soit (aij)(i ; j)∈T(a_{ij})_{(i\,;\,j)\in T} une famille de nombres.

Somme des (aij)(a_{ij}) suivant les colonnes (on fait varier l'indice de colonne ii) :

∑i=0n∑j=0n−iaij\sum_{i=0}^{n} \sum_{j=0}^{n-i} a_{ij}

0 0 1 1 2 2 … … n n i j

Somme des (aij)(a_{ij}) suivant les lignes (on fait varier l'indice de ligne jj) :

∑j=0n∑i=0n−jaij\sum_{j=0}^{n} \sum_{i=0}^{n-j} a_{ij}

0 0 1 1 2 2 … … n n i j

Somme des (aij)(a_{ij}) suivant les diagonales (on meuble un nouvel indice kk de diagonale) :

∑k=0n∑i+j=kaij\sum_{k=0}^{n} \sum_{i+j=k} a_{ij}

0 0 1 1 2 2 … … n n i j i + j = k

Bilan :

∑(i,j)∈Taij=∑i=0n∑j=0n−iaij=∑j=0n∑i=0n−jaij=∑k=0n∑i+j=kaij\sum_{(i,j)\in T} a_{ij} = \sum_{i=0}^{n} \sum_{j=0}^{n-i} a_{ij} = \sum_{j=0}^{n} \sum_{i=0}^{n-j} a_{ij} = \sum_{k=0}^{n} \sum_{i+j=k} a_{ij}

Exemples

Exemple 1 — compter les points du triangle (aij=1a_{ij}=1).

Par colonnes, la colonne ii contient n−i+1n-i+1 points :

∑i=0n∑j=0n−i1=∑i=0n(n−i+1)=(n+1)(n+2)2\sum_{i=0}^{n}\sum_{j=0}^{n-i}1=\sum_{i=0}^{n}(n-i+1)=\frac{(n+1)(n+2)}{2}

Par diagonales, la diagonale kk contient k+1k+1 points :

∑k=0n∑i+j=k1=∑k=0n(k+1)=(n+1)(n+2)2\sum_{k=0}^{n}\sum_{i+j=k}1=\sum_{k=0}^{n}(k+1)=\frac{(n+1)(n+2)}{2}

Les deux méthodes donnent le même résultat. Pour n=2n=2, il y a 66 points : (0,0),(1,0),(2,0),(0,1),(1,1),(0,2)(0,0),(1,0),(2,0),(0,1),(1,1),(0,2).

Animation — Compter les points du triangle (aij = 1, n = 2)
Choisissez la méthode de parcours.

Exemple 2 — un calcul explicite avec n=2n=2 et aij=ia_{ij}=i.

jjpoints de la lignesomme de la ligne
00a00+a10+a20=0+1+2a_{00}+a_{10}+a_{20}=0+1+233
11a01+a11=0+1a_{01}+a_{11}=0+111
22a02=0a_{02}=000
Total4

Par colonnes : i=0→0i=0 \to 0 ; i=1→1+1=2i=1 \to 1+1 = 2 ; i=2→2i=2 \to 2 ; total 0+2+2=40+2+2=4 ✓.

Exemple 3 — les diagonales : triangle de Pascal.

Posons aij=(i+ji)a_{ij}=\binom{i+j}{i}. Sur la diagonale kk, i+j=ki+j=k, donc par la formule du binôme :

∑i+j=k(ki)=2k\sum_{i+j=k}\binom{k}{i}=2^k

d'où

∑(i,j)∈T(i+ji)=∑k=0n2k=2n+1−1\sum_{(i,j)\in T}\binom{i+j}{i}=\sum_{k=0}^{n}2^k=2^{n+1}-1

Pour n=2n=2 : les valeurs sont 1,1,1,1,2,11,1,1,1,2,1, de somme 7=23−17=2^3-1 ✓. Ici, le découpage par diagonales est le seul qui donne un calcul simple.

Animation — Triangle de Pascal par Diagonales (n = 2)
Sur chaque diagonale k, la somme vaut 2k.

Exemple 4 — produit de Cauchy.

Pour deux suites (bi)(b_i) et (cj)(c_j), posons aij=bicja_{ij}=b_i c_j. En sommant sur les diagonales :

∑(i,j)∈Tbicj=∑k=0n∑i=0kbi ck−i⏟=: dk\sum_{(i,j)\in T} b_i c_j=\sum_{k=0}^{n}\underbrace{\sum_{i=0}^{k} b_i\,c_{k-i}}_{=:\,d_k}

Le terme dkd_k est le coefficient de XkX^k dans le produit de polynômes (∑biXi)(∑cjXj)\big(\sum b_iX^i\big)\big(\sum c_jX^j\big). C'est le principe du produit de Cauchy de deux séries.

Exemple 5 — intervertir des sommes à bornes dépendantes.

La somme ∑i=0n∑j=0ij\displaystyle\sum_{i=0}^{n}\sum_{j=0}^{i} j porte sur le triangle 0≤j≤i≤n0\le j\le i\le n (ici jj est borné par ii). En lisant ce triangle ligne par ligne, on inverse l'ordre : pour jj fixé, ii varie de jj à nn.

∑i=0n∑j=0ij=∑j=0n∑i=jnj=∑j=0nj (n−j+1)=n(n+1)(n+2)6\sum_{i=0}^{n}\sum_{j=0}^{i} j=\sum_{j=0}^{n}\sum_{i=j}^{n} j=\sum_{j=0}^{n} j\,(n-j+1)=\frac{n(n+1)(n+2)}{6}

Vérification pour n=2n=2 : membre de gauche 0+1+(0+1+2)=40+1+(0+1+2)=4 ; membre de droite 2⋅3⋅46=4\frac{2\cdot3\cdot4}{6}=4 ✓.

À retenir. Quand les bornes dépendent de l'autre indice, on ne peut pas simplement échanger les ∑\sum : il faut redécrire le domaine (dessiner le triangle !) et relire les nouvelles bornes.


Méthode : changer l'ordre de sommation

  1. Dessiner le domaine dans le plan (i,j)(i,j).
  2. Choisir le découpage le plus commode : colonnes, lignes ou diagonales.
  3. Lire les nouvelles bornes sur le dessin : pour le triangle 0≤i+j≤n0\le i+j\le n, une colonne ii contient 0≤j≤n−i0\le j\le n-i, une ligne jj contient 0≤i≤n−j0\le i\le n-j, une diagonale kk contient les couples (i,k−i)(i,k-i), 0≤i≤k0\le i\le k.
  4. Vérifier sur un petit cas (n=2n=2 suffit souvent).