Sommations

Parmi les outils mathématiques permettant d'évaluer la complexité d'un algorithme se trouvent les sommations. Commençons par rappeler quelques propriétés :

1. $$\sum_{i = p}^n 1 = n - p + 1$$
2. $$\sum_{i = p}^n u_i = (\sum_{i = p}^{n - 1} u_i) + u_{n} = u_{p} + \sum_{i = p + 1}^{n} u_i$$
3. $$\sum_{i = p}^n (a.u_i) = a\sum_{i = p}^n u_i$$
4. $$\sum_{i = p}^n (a_i + b) = \sum_{i = p}^n a_i + \sum_{i = p}^n b = (\sum_{i = p}^n a_i) + (n - p + 1)b$$
5. $$\sum_{i = p}^n (a_i + b_i) = \sum_{i = p}^n a_i + \sum_{i = p}^n b_i$$
6. $$\sum_{i = p}^n u_i = \sum_{i = p + 1}^{n + 1} u_{i - 1} = \sum_{i = p - 1}^{n - 1} u_{i + 1}$$
7. $$\sum_{i = 1}^n \sum_{j = 1}^m u_{ij} =\sum_{j = 1}^m \sum_{i = 1}^n u_{ij}$$

Bien que le $\sum$ soit prioritaire sur le $+$ mais pas sur le $\times$, il usuel pour éviter toute confusion de rajouter des parenthèses, même inutiles. Parmi les sommes que vous devez maîtriser parfaitement figurent les deux suivantes :

1. $$\sum_{i = 1}^n i = \frac{n(n + 1)}{2}$$ (série arithmétique)
2. $$\sum_{i = 0}^n r^i =\frac{r^{n + 1} - 1}{r - 1}$$ (série géométrique)

On se ramène souvent à ce type de formule en algorithmique.