Trois sommes doubles, trois découpages du carré

La stratégie : lire le domaine avant le terme général. Dans une somme double, ce qui commande le calcul est l'ensemble des couples $(i,j)$ sur lesquels on somme. Les trois questions découpent le même carré $\{1,\dots ,n{\}}^2$ de trois façons : en diagonale et deux triangles, en lignes ou en colonnes, en diagonales parallèles. Ce qu'on a le droit d'utiliser : les sommes de référence $\sum k=\frac{n(n+1)}{2}$ et $\sum k^2=\frac{n(n+1)(2n+1)}{6}$, et la factorisation d'une somme double à variables séparées.

a) La diagonale et les deux triangles. Sur le carré, $i$ et $j$ varient indépendamment, et la somme se factorise : $$\sum _{1\le i,j\le n}ij=\left(\sum _{i=1}^{n}i\right)\left(\sum _{j=1}^{n}j\right)=\frac{n^2(n+1{)}^2}{4}.$$ Le carré se partage en trois parties disjointes : la diagonale $i=j$, où le terme vaut $i^2$ ; le triangle $i<j$ ; le triangle $i>j$. L'échange des noms $(i,j)\mapsto (j,i)$ envoie le second triangle sur le premier et laisse $ij$ inchangé : les deux triangles portent la même somme. Donc $$\frac{n^2(n+1{)}^2}{4}=\frac{n(n+1)(2n+1)}{6}+2\sum _{1\le i<j\le n}ij.$$ En isolant la somme cherchée, puis en mettant $\frac{n(n+1)}{4}$ en facteur : $$\sum _{1\le i<j\le n}ij=\frac{n(n+1)}{4}\left[\frac{n(n+1)}{2}-\frac{2n+1}{3}\right]=\frac{n(n+1)(3n^2-n-2)}{24}=\frac{(n-1)n(n+1)(3n+2)}{24},$$ puisque $3n^2-n-2=(n-1)(3n+2)$ : $n=1$ l'annule, et l'on vérifie en développant.

Le point délicat. Le facteur $2$ vient de la symétrie du terme : $ij=ji$. Pour un terme non symétrique, comme $i^{2}j$, les deux triangles ne porteraient pas la même somme, et l'argument tomberait.

b) Un triangle, dans les deux sens. Le domaine est $\{(i,j):1\le i\le j\le n\}$.

En sommant d'abord sur $i$, à $j$ fixé : $i$ décrit $\{1,\dots ,j\}$, et la somme intérieure vaut $\frac{j(j+1)}{2}$. Donc $$S=\frac{1}{2}\sum _{j=1}^n\left(j^2+j\right)=\frac{1}{2}\left(\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}\right)=\frac{n(n+1)(2n+4)}{12}=\frac{n(n+1)(n+2)}{6}.$$

En intervertissant, c'est-à-dire en fixant d'abord $i$ : la condition $i\le j\le n$ dit que $j$ décrit $\{i,\dots ,n\}$, soit $n-i+1$ valeurs, et le terme $i$ ne dépend pas de $j$. Donc $$S=\sum _{i=1}^{n}i(n+1-i)=\frac{n(n+1{)}^2}{2}-\frac{n(n+1)(2n+1)}{6}=\frac{n(n+1)(3(n+1)-(2n+1))}{6}=\frac{n(n+1)(n+2)}{6}.$$ Intervertir, ce n'est pas échanger les deux signes somme : c'est redécrire le même domaine dans l'autre ordre, et les bornes changent.

c) Les diagonales du carré. Regroupons les couples selon $d=j-i$, qui va de $-(n-1)$ à $n-1$. Pour $d\ge 0$ fixé, les couples $(i,i+d)$ du carré sont ceux pour lesquels $1\le i\le n-d$ : il y en a $n-d$ ; de même, il y a $n-|d|$ couples pour $d<0$. Sur chacun, le terme vaut $|d|$. La diagonale $d=0$ ne contribue pas, et les valeurs $d$ et $-d$ contribuent autant : $$\sum _{1\le i,j\le n}|i-j|=2\sum _{d=1}^{n-1}d(n-d)=2\left[\frac{n^2(n-1)}{2}-\frac{(n-1)n(2n-1)}{6}\right]=\frac{(n-1)n(n+1)}{3}.$$ (Dans le crochet, on met $\frac{(n-1)n}{6}$ en facteur : il reste $3n-(2n-1)=n+1$.)

Contrôles. Pour $n=3$ : a) les couples $(1,2),(1,3),(2,3)$ donnent $2+3+6=11$, et la formule donne $\frac{2\times 3\times 4\times 11}{24}=11$ ; b) $1+(1+2)+(1+2+3)=10=\frac{3\times 4\times 5}{6}$ ; c) quatre couples à distance $1$ et deux à distance $2$ donnent $8=\frac{2\times 3\times 4}{3}$. Les trois formules sont vérifiées par le calcul direct pour tous les $n<60$.

Ce que l'exercice installe. Une somme double se lit sur son domaine : un produit se factorise, un triangle se somme dans l'ordre le plus commode, un triangle strict se complète en carré, et le carré se range aussi par diagonales. Le carré est la diagonale plus deux fois le triangle : c'est la formule qui donnera, en probabilités, la variance d'une somme, $V(X_1+\cdots +X_n)={\sum }_{i}V(X_i)+2{\sum }_{i<j}\mathrm{Cov}(X_i,X_j)$. Et le c) dit que la distance moyenne entre deux des points $1,2,\dots ,n$, pris au hasard, vaut $\frac{n^2-1}{3n}$ : environ le tiers de la longueur du segment.