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 :
Et pour finir :
corrigé
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 :
corrigé
corrigé
Trivial par récurrence.
En déduire que :
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 :
et que :
corrigé
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 :
Montrez que :
Vous pourrez utiliser le polynôme $P(x) = \sum_{i=1}^nx^i$ et le dériver.
corrigé
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 :
Et donc :
Ce qui mène au résultat attendu.
En déduire que :
corrigé
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 :
et que :
Avez vous remarqué que :
Surprenant, non ?
Série harmonique
On définie la série harmonique comme :
Montrez que $H(2^n) \geq 1 + \frac{n}{2}$
corrigé
corrigé
Et on conclut par une récurrence (devenue) triviale.
En déduire que $H(n)$ diverge lorsque $n$ tend vers $+\infty$.
corrigé
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
preuve
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$ :
En sommant le tout on obtient une série télescopique :
Qui se simplifie en :
On en déduit donc l'encadrement :
Ce qui amène directement à :
Corollaire
Et à ça :
Corollaire
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 :
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 :
corrigé
corrigé
Clair par récurrence :
En déduire que pour tout $n$ :
corrigé
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 :
Et l'encadrement final vient du fait que :
En déduire que :
corrigé
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 :
preuve
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}[$ :
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 :
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 :
On utilise alors le fait que :
proposition
preuve
preuve
On pose maintenant $m = 2n + 1$ :
Et on n'en garde que la partie imaginaire pour obtenir :
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 :
Pour obtenir :
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