Calcul de sommes classiques

Cours/Algorithmie/Calcul de sommes classiques

Lors de calculs de complexité, on va de nombreuses fois avoir les mêmes sommes à estimer, voir à calculer.

Cette série d'exercice va vous montrer les plus classiques et leur usage dans les calculs de complexité. On aura presque jamais besoin de les calculer explicitement, seul les équivalence en $\Theta$ ou en $\mathcal{O}$ vont nous intéresser.

Séries

Séries des premiers entiers

Classiques et se démontrent aisément par récurrence (mais faite tout de même les calculs pour vous en rendre compte). Montrez que :

$$ \sum_{i=0}^{n}i = \frac{n(n+1)}{2} = \Theta(n^2) $$

$$ \sum_{i=0}^{n}i^2 = \frac{n(n+1/2)(n+1)}{3}=\frac{n(n+1)(2n+1)}{6}= \Theta(n^3) $$

$$ \sum_{i=0}^{n}i^3 = (\sum_{i=0}^{n}i)^2 = \frac{n^2(n+1)^2}{4} = \Theta(n^4) $$

Et pour finir :

$$ \sum_{i=0}^{n}i^k = \Theta(n^{k+1}) $$

corrigé

Par récurrence. On suppose $\sum_{i=0}^{n}i^{k-1} = \Theta(n^{k}) = \Omega(n^{k})$.

Puis :

$\sum_{i=0}^{n}i^k\leq n \cdot \sum_{i=0}^{n}i^{k-1} = n \mathcal{O}(n^k) = \mathcal{O}(n^{k+1})$
$\sum_{i=0}^{n}i^{k} \geq \sum_{i=n/2}^{n}i^k \geq \frac{n}{2}\sum_{i=n/2}^{n}i^{k-1} = \frac{n}{2}\sum_{i=0}^{n/2}(i+n/2)^{k-1} \geq \frac{n}{2} \cdot \sum_{i=0}^{n/2}(i)^{k-1} = \frac{n}{2}\Omega((n/2)^k) = \Omega(n^{k+1})$

Séries géométriques

On considère la série suivante :

Montrez que :

$$ S_n = \sum_{i=0}^{n}r^i = \frac{1-r^{n+1}}{1-r} $$

Si $r \neq 1$.

corrigé

Trivial par récurrence.

En déduire que :

$$ S_n = \begin{cases} \mathcal{O}(1) \text{ si } |r| < 1\\ \Theta(r^n) \text{ si } |r| > 1\\ \end{cases} $$

En complexité c'est souvent avec des puissance de 2 que l'on va jouer. Por le coup, il est utile de connaître les valeurs des sommes car elles sont souvent des calculs intermédiaires :

Montrez que :

$$ \sum_{i=0}^{n}2^i = 2^{n+1} - 1 $$

et que :

$$ \lim_{n\to +\infty} \sum_{i=0}^{n}\frac{1}{2^i} = 2 $$

corrigé

La première égalité est uniquement une application numérique et la seconde résulte de $\frac{1}{2^n} \to_{+\infty} 0$.

La seconde série a une interprétation géométrique

Une variation classique de la série géométrique, vue par exemple dans le calcul du tri rapide pour $r=2$ est :

$$ S'_n = \sum_{i=1}^{n}i\cdot r^i $$

Montrez que :

$$ S'_n = \sum_{i=1}^{n}i\cdot r^i = \frac{r^{n+1}(n(r-1) - 1) + r}{(1-r)^2} $$

Vous pourrez utiliser le polynôme $P(x) = \sum_{i=1}^nx^i$ et le dériver.

corrigé

On a : $S'_n = rP'(r)$ et donc e n utilisant la formule de l'exercice précédent :

$$ \begin{array}{lcl} S'_n &=& r\cdot \frac{-(n+1)r^n(1-r)+(1-r^{n+1})}{(1-r)^2}\\ &=& r\cdot \frac{r^{n}((n+1)(r-1) -r^{n+1} + 1) + r}{(1-r)^2}\\ &=& r\cdot \frac{r^{n}((n+1)(r-1)-r) + 1}{(1-r)^2}\\ &=& \frac{r^{n+1}(n(r-1)-1) + r}{(1-r)^2}\\ \end{array} $$

En déduire que :

$$ S'_n = \begin{cases} \mathcal{O}(1) \text{ si } |r| < 1\\ \Theta(r^n) \text{ si } |r| > 1\\ \end{cases} $$

Et pour le cas souvent intéressant en complexité :

Montrez que :

$$ \sum_{i=0}^{n}i2^i = (n-1)2^{n+1} + 2 $$

et que :

$$ \lim_{n\to +\infty} \sum_{i=0}^{n}\frac{i}{2^i} = 2 $$

Avez vous remarqué que :

$$ \lim_{n\to +\infty} \sum_{i=0}^{n}\frac{1}{2^i} = \lim_{n\to +\infty} \sum_{i=0}^{n}\frac{i}{2^i} = 2 $$

Surprenant, non ?

Série harmonique

On définie la série harmonique comme :

$$ H(n) = \sum_{i=1}^{n}\frac{1}{i} $$

Montrez que $H(2^n) \geq 1 + \frac{n}{2}$

corrigé

$$ \begin{array}{lcl} H(2^{n+1}) &=& H(2^{n}) + \sum_{i=2^n+1}^{2^{n+1}}\frac{1}{i}\\ &=& H(2^{n}) + \sum_{i=1}^{2^{n}}\frac{1}{2^n+i} = H(2^{n}) + \frac{1}{2^n}\sum_{i=1}^{2^{n}}\frac{1}{1 + \frac{i}{2^n}} \\ &\geq& H(2^{n}) + \frac{1}{2^n}\sum_{i=1}^{2^{n}}\frac{1}{2}\\ &\geq& H(2^{n}) + \frac{1}{2} \end{array} $$

Et on conclut par une récurrence (devenue) triviale.

En déduire que $H(n)$ diverge lorsque $n$ tend vers $+\infty$.

corrigé

Si $H(n)$ converge, alors toute suite extraite également. Cela n'est donc pas possible puisque l'exercice précédent montre que $H(2^n)$ diverge en $+\infty$.

Si la série harmonique arrive dans le calcul des complexités c'est que l'on cherche à montrer que cette dernière va se comporter comme une fonction logarithmique (ou plus généralement polylogarithmique).

Montrons le en utilisant le fait que comme $f(x) = \frac{1}{x}$ est une fonction décroissante sur $\mathbb{R}^+$ on peut utiliser, on a pour tout entier $i> 1$ :

$$ \frac{1}{i} \leq \int_{i-1}^{i}\frac{1}{x}dx $$

Et a pour tout entier $i> 0$ :

$$ \int_{i}^{i+1}\frac{1}{x}dx \leq \frac{1}{i} $$

On peut alors utiliser la comparaison série-intégrale pour en déduire que pour tout $n> 0$ :

$$ \ln(n) \leq H(n) \leq \ln(n) + 1 $$

corrigé

L'inégalité de droite est claire en sommant de $i=2$ à $i=n$.

Pour l'inégalité de gauche, la première inégalité donne en sommant de $i=1$ à $i=n$ : $\ln(n+1) \leq H(n)$ et on conclut puisque $\ln$ est une fonction croissante.

Ce qui doit amener à :

$$ H(n) = \Theta(\ln(n)) $$

corrigé

L'encadrement de l'exercice précédent montre que $H(n) / \ln(n) \to_{+\infty} 1$ les deux fonctions sont donc équivalentes en $+\infty$ (ce qui est plus fort que ce qu'on demande)

Problème de Bâle et variante

Problème de Bâle

La somme suivante à un nom car le calcul exact de sa limite elle a résisté pendant plusieurs années avant qu'Euler n'en vienne à bout. Son résultat est diablement surprenant :

$$ \lim_{n \to {+\infty}}\sum_{i=1}^{n}\frac{1}{i^2} = \frac{\pi^2}{6} $$

5 preuves différentes du résultat et les détails dans voyage en Analystan

On ne va pas ici démontrer la valeur exacte de la limite (qui a plus sa place dans un cours d'analyse), juste qu'elle converge et que c'est donc un $\mathcal{O}(1)$. On va pour cela utiliser une série proche mais admirablement facile à calculer.

Montrez que :

$$ \sum_{i=1}^n\frac{1}{i(i+1)} = \frac{n}{n+1} $$

corrigé

Clair par récurrence :

$$ \sum_{i=1}^{n+1}\frac{1}{i(i+1)} = \frac{n}{n+1} + \frac{1}{(n+1)(n+2)} = \frac{n(n+2) + 1}{(n+1)(n+2)} = \frac{(n+1)^2}{(n+1)(n+2)} $$

En déduire que pour tout $n$ :

$$ 1 \leq \sum_{i=1}^n\frac{1}{i^2} \leq 2 $$

Indice

Pour $i> 1$ vous pourrez remarquer que : $\frac{1}{i(i+1)} \leq \frac{1}{i^2} \leq \frac{1}{i(i-1)}$

corrigé

En sommant l'indice on obtient :

$$ \sum_{i=1}^{n}\frac{1}{i(i+1)} \leq \sum_{i=1}^{n}\frac{1}{i^2} \leq 1 + \sum_{i=2}^{n}\frac{1}{i(i-1)} $$

Et l'encadrement final vient du fait que :

$$ \lim_{n\to +\infty}\frac{n}{n+1} = \lim_{n\to +\infty}\frac{n+1}{n+1} - \frac{1}{(n+1)} = 1 $$

En déduire que :

$$ \sum_{i=1}^n\frac{1}{i^2} = \mathcal{O}(1) $$

corrigé

La série est croissante et bornée, elle converge.

Classiquement en analyse on aurait aussi utilisé la comparaison série-intégrale pour faire la même chose. C'est moins élégant dans ce cas là, mais cela vous servira dans bien d'autres calcul de sommes (gardez la sous le coude).