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 (on en a d'ailleurs déjà vu certaines) 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 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+2} \cdot \frac{r + (1+1/n)/(1+2/n)}{(1-r)^2} + \frac{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 explicite de $P(x) = \frac{1-x^{n+1}}{1-x}$, on a :

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

Et donc :

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

Ce qui mène au résultat attendu.

En déduire que :

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

corrigé

Clair car $\frac{r^{n+1}}{n+2}$ tend vers 0 lorsque $n$ tend vers l'infini si $r < 1$

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).

On a déjà utilisé ce résultat. On le remet ici pour référence.

Proposition

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

preuve

Soit $f(x) = \ln(1+x) - x$ définie sur $]-1, +\infty[$. Comme $f'(x) = \frac{1}{1+x} -1 = \frac{-x}{1+x}$, on a que $f$ atteint son minimum en 0 : $f(x) \geq f(0) = 0$ pour tout $x$ de $]-1, +\infty[$ : $x \geq \ln(1+x)$ sur $]-1, +\infty[$.

De là pour tout entier $i > 1$ :

  • $-\frac{1}{i} \geq \ln(1-\frac{1}{i}) = \ln(i-1) - \ln(i)$
  • $\frac{1}{i} \geq \ln(1+\frac{1}{i}) = \ln(i+1) - \ln(i)$

Ce qui donne l'encadrement pour $i > 1$ :

$$ \ln(i+1) - \ln(i) \leq \frac{1}{i} \leq \ln(i) - \ln(i-1) $$

En sommant le tout on obtient une série télescopique :

$$ \begin{array}{c} \sum\limits_{2\leq i \leq n} (\ln(i+1) - \ln(i)) \leq \sum\limits_{2\leq i \leq n}\frac{1}{i} \leq \sum\limits_{2\leq i \leq n} (\ln(i) - \ln(i-1)) \end{array} $$

Qui se simplifie en :

$$ \begin{array}{c} \ln(n+1) - \ln(2) \leq \sum\limits_{2\leq i \leq n}\frac{1}{i} \leq \ln(n) - \ln(1) \end{array} $$

On en déduit donc l'encadrement :

$$ \begin{array}{c} \ln(n+1) \leq \sum\limits_{i=1}^n\frac{1}{i} \leq \ln(n) + 1 \end{array} $$

Ce qui amène directement à :

Corollaire

$$ \sum\limits_{i=1}^{n} \frac{1}{i} \underset{+\infty}{\sim} \ln(n) $$

Et à ça :

Corollaire

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

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\limits_{n \to {+\infty}}\sum_{i=1}^{n}\frac{1}{i^2} = \frac{\pi^2}{6} $$

Utilisation en algorithmie

On ne va pas ici démontrer la valeur exacte de la limite (regardez le premier lien si vous en voulez une), 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 $$

corrigé

Pour $i> 1$ on a clairement $\frac{1}{i(i+1)} \leq \frac{1}{i^2} \leq \frac{1}{i(i-1)}$, et donc 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.

Preuve

On va donner la preuve du lien ci-dessus, que l'on doit à Papadimitriou (1973). Son intérêt est qu'elle n'a pas besoin d'intégrale ou de méthodes d'analyse, juste un petit polynôme et l'utilisation de fonction trigonométriques simple.

proposition

Pour tout $0 < x < \frac{\pi}{2}$ on a :

$$ \sin(x) < x < \tan(x) $$

preuve

Soient les deux fonctions définies sur $[0, \frac{\pi}{2}[$ :

  • $f(x) = x- \sin(x)$,
  • $g(x) = \tan(x) - x$.

On a :

  • $f'(x) = 1 - cos(x) > 0$ sur $]0, \frac{\pi}{2}[$ donc $f(x) > f(0) = 0$ sur $]0, \frac{\pi}{2}[$
  • $g'(x) = (1+\tan^2(x)) -1 = \tan^2(x) > 0$ sur $]0, \frac{\pi}{2}[$ $g(x) > g(0)$ = 0 sur $]0, \frac{\pi}{2}[$.

On en conclut que sur $]0, \frac{\pi}{2}[$ :

  • $\sin(x) < x$
  • $x < \tan(x)$

On a alors sur $]0, \frac{\pi}{2}[$ :

$$ \begin{align*} \sin(x) < x < \tan(x)\\ \frac{1}{\sin(x)} > \frac{1}{x} > \frac{1}{\tan(x)}\\ \frac{1}{\sin^2(x)} > \frac{1}{x^2} > \frac{1}{\tan^2(x)}\\ \end{align*} $$

Comme $1 + \cot^2(x) = \frac{1}{\sin^2(x)}$ ($\cot(x) = \frac{1}{tan(x)}$) sur $]0, \frac{\pi}{2}[$, l'encadrement précédent s'écrit :

$$ \begin{align*} \cot^2(x) < \frac{1}{x^2} < 1 + \cot^2(x)\\ \end{align*} $$

En posant $x_k = \frac{k\pi}{2n+1}$ pour $1\leq k \leq n$, on a $0< x_k <\frac{\pi}{2}$ et on l'injecter dans l'équation précédente :

$$ \begin{align*} \sum\limits_{k=1}^n\cot^2(x_k) < \frac{(2n+1)^2}{\pi^2}\sum\limits_{k=1}^n\frac{1}{k^2} < m + \sum\limits_{k=1}^n\cot^2(x_k)\\ \end{align*} $$

On utilise alors le fait que :

proposition

$$ \sum\limits_{k=1}^n\cot^2(\frac{k\pi}{2n+1}) = \frac{n(2n-1)}{3} $$

preuve

$$ \begin{array}{lcl} \cos(m\theta) + i\sin(m\theta) &=& (e^{im\theta}) \\ &=& (e^{i\theta})^m \\ &=& (\cos(\theta) + i\sin(\theta))^m \\ &=& \sin^m(\theta)\cdot (\cot(\theta) + i)^m\\ &=& \sin^m(\theta)\cdot (\sum\limits_{k=0}^m(\binom{m}{k}i^k\cot^{m-k}(\theta)) \end{array}{lcl} $$

On pose maintenant $m = 2n + 1$ :

$$ \sin((2n+1)\theta) = \sin^{2n+1}(\theta)\cdot (\sum\limits_{k=0}^m(\binom{2n+1}{k}i^k\cot^{2n+1-k}(\theta)) $$

Et on n'en garde que la partie imaginaire pour obtenir :

$$ \sin((2n+1)\theta) = \sin(\theta)^{2n+1} \cdot (\sum\limits_{k=0}^{n}(\binom{2n+1}{2k + 1}(-1)^k\cot^{k}(\theta)) $$

Puisque $\sin(\theta) \neq 0$ pour $0 < \theta < \frac{\pi}{2}$, l'équation précédente prouve que les $n$ racines du polynôme $P(x) = \sum\limits_{i=0}^{n}(\binom{2n+1}{2i + 1}(-1)^ix^{i})$ sont les $n$ valeurs $\cot^2(x_k)$ avec $x_k = \frac{k\pi}{2n + 1}$, $1\leq k \leq n$.

La somme des $n$ racines $r_i$ d'un polynôme $\sum\limits_{k=0}^{n}a_kx^k$ valant $-\frac{a_{n-1}}{a_n}$ (puisque $\sum\limits_{k=0}^{n}a_kz^k = \prod\limits_{k=1}^{n}(x-r_i)$) on en déduit la relation demandée :

$$ \sum\limits_{k=1}^{n}\cot^2(x_k) = \frac{n(2n -1)}{3} $$

Pour obtenir :

$$ \begin{align*} \frac{n(2n-1)}{3} < \frac{(2n+1)^2}{\pi^2}\sum\limits_{k=1}^n\frac{1}{k^2} < n + \frac{n(2n-1)}{3}\\ \frac{\pi^2}{6}\frac{2n(2n-1)}{(2n+1)^2} < \sum\limits_{k=1}^n\frac{1}{k^2} < \frac{n}{(2n+1)^2} + \frac{\pi^2}{6}\frac{2n(2n-1)}{(2n+1)^2}\\ \end{align*} $$

Comme : $\lim\limits_{n\to +\infty} \frac{2n(2n-1)}{(2n+1)^2} = 1$ et $\lim\limits_{n\to +\infty} \frac{n}{(2n+1)^2} = 0$ on a bien le résultat attendu :

Théorème

$$ \lim\limits_{n\to +\infty} \frac{1}{k^2} = \frac{\pi^2}{6} $$