\input bruno

\titre{R{\'e}currences \emph{diviser pour r{\'e}gner}}

\subpart{Notations}

Soient $(x_n)_{n�1}$ et $(y_n)_{n�1}$ deux suites de r{\'e}els; 
on note $x_n = \Omega(y_n)$ lorsque $y_n = {\cal O}(x_n)$; 
on note $x_n = \Theta(y_n)$ lorsque l'on a simultan{\'e}ment 
$x_n = {\cal O}(y_n)$ et $x_n = \Omega(y_n)$.
\smallskip

La partie enti{\`e}re du r{\'e}el $x$ est not{\'e}e $\lfloor x \rfloor$.
\smallskip

On note $\lceil x \rceil$ la "partie enti{\`e}re sup{\'e}rieure" de $x$, 
\idest: le plus petit relatif sup{\'e}rieur ou {\'e}gal {\`a} $x$; 
on a donc $\lceil x \rceil \in \Z$ et 
$\lceil x \rceil - 1 < x � \lceil x \rceil$.
\smallskip

Soient: $p\in\N^*$; $(\lambda_k)_{1�k�p}$ une famille de r{\'e}els 
strictement positifs; $(\alpha_k)_{1�k�p}$ une famille de r{\'e}els 
strictement sup{\'e}rieurs {\`a} 1; $a$ un r{\'e}el positif ou nul. 
On note $\displaystyle S = \sum_{1�k�p} \lambda_k$.
\smallskip

\centerline{\encadre{\bf Dans toute la suite, on suppose $S>1$.}}
\smallskip

On constate alors que l'application $\displaystyle \varphi: t�0 
 \mapsto \sum_{1�k�p} {\lambda_k \over \alpha_k{}^t}$ est 
continue et strictement d{\'e}croissante, donc r{\'e}alise une bijection de 
$[1,+�\mathclose[$ sur $\mathopen]0,S]$. 
Par cons{\'e}quent, il existe un et un seul exposant $\gamma>0$ tel que 
$\displaystyle \sum_{1�k�p} {\lambda_k \over \alpha_k{}^\gamma} = 1$.
\smallskip

\subpart{Premi{\`e}re partie}

\textbf{Th{\'e}or{\`e}me 1}: si une suite $(u_n)_{n�1}$ de r{\'e}els v{\'e}rifie 
$\displaystyle u_n � a + \sum_{1�k�p} \lambda_k u_{\lfloor n/\alpha_k \rfloor}$ 
pour tout $n�2$, alors $u_n = {\cal O}(n^\gamma)$.
\smallskip

\textbf{Preuve}
\smallskip

� Quitte {\`a} remplacer la suite de terme g{\'e}n{\'e}ral $u_n$ par 
celle  de terme g{\'e}n{\'e}ral 
$\displaystyle u_n + {a \over S-1 \lambda_k}$, 
on peut supposer $a=0$.
\smallskip

� Notons $B = u_1$, et 
{\'e}tablissons la majoration $u_n � B n^\gamma$ par r{\'e}currence sur $n$. 
Pour $n=1$, la majoration r{\'e}sulte du choix de $B$. 
Supposons-la acquise jusqu'au rang 
$n$ inclus; pour tout $k\in\cro[1,p]$, on aura 
$\displaystyle 
 \Bigl\lfloor {n+1 \over \alpha_k} \Bigr\rfloor � {n+1 \over \alpha_k} 
 < n+1$. 
D'o{\`u} $\displaystyle \Bigl\lfloor {n+1 \over \alpha_k} \Bigr\rfloor � n$ 
et par suite 
$\displaystyle u_{\lfloor (n+1)/\alpha_k \rfloor} 
 � B \Bigl( \Bigl\lfloor {n+1 \over \alpha_k} \Bigr\rfloor \Bigr)^\gamma$. 
Alors:
$$\eqalign{
 u_{n+1} 
 & = \sum_{1�k�p} \lambda_k u_{\lfloor (n+1)/\alpha_k \rfloor} 
   � \sum_{1�k�p} \lambda_k B \Bigl( \Bigl\lfloor 
     {n+1 \over \alpha_k} \Bigr\rfloor \Bigr)^\gamma \cr 
 & � B \sum_{1�k�p} \lambda_k \Bigl( {n+1 \over \alpha_k} \Bigr)^\gamma 
   = B \biggl( \sum_{1�k�p} {\lambda_k \over \alpha_k{}^\gamma} 
     \biggr) (n+1)^\gamma 
   = B (n+1)^\gamma \cr 
}$$

Ceci {\'e}tablit l'assertion au rang $n+1$.
\smallskip

\textbf{Exemple 2}: recherche dans un $2d$-arbre (Bentley, \emph{CACM} 1975). 
On est amen{\'e} {\`a} {\'e}tudier une suite v{\'e}rifiant la relation 
de r{\'e}currence $C_n � 2 + 2 C_{\lfloor n/4 \rfloor}$. 
Ici, $p=1$, $\lambda_1=2$ et $\alpha_1=4$ si bien que 
$\gamma = 1/2$ et $C_n = O(\sqrt n)$. 
\smallskip

\textbf{Th{\'e}or{\`e}me 2}: si une suite $(u_n)_{n�1}$ de r{\'e}els v{\'e}rifie 
$\displaystyle u_n � a + \sum_{1�k�p} \lambda_k u_{\lfloor n/\alpha_k \rfloor}$ 
pour tout $n�2$, alors $u_n = \Omega(n^\gamma)$.
\smallskip

\textbf{Preuve}: notons $A = 2^{-\gamma} u_1$; nous allons {\'e}tablir 
la minoration $u_n � A (n+1)^\gamma$ par r{\'e}currence sur $n$. 
On aura {\`a} plus forte raison $u_n � A n^\gamma$.
\smallskip

Pour $n=1$, la minoration r{\'e}sulte du choix de $A$. 
Supposons-la acquise jusqu'au rang 
$n$ inclus; pour tout $k\in\cro[1,p]$, on aura comme pr{\'e}c{\'e}demment 
$\displaystyle  \Bigl\lfloor {n+1 \over \alpha_k} \Bigr\rfloor � n$, 
donc: 
$$
 u_{\lfloor {(n+1)/\alpha_k} \rfloor} 
 � A \Bigl( \Bigl\lfloor {n+1 \over \alpha_k} \Bigr\rfloor + 1 \Bigr)^\gamma 
 > A \Bigl( {n+1 \over \alpha_k} \Bigr)^\gamma 
$$

ceci car $\lfloor x \rfloor + 1 > x$. On en d{\'e}duit:
$$\eqalign{
 u_{n+1} 
 & = \sum_{1�k�p} \lambda_k u_{\lfloor (n+1)/\alpha_k \rfloor} 
   � \sum_{1�k�p} \lambda_k A \Bigl( \Bigl\lfloor 
     {n+1 \over \alpha_k} \Bigr\rfloor + 1 \Bigr)^\gamma \cr 
 & � A \sum_{1�k�p} \lambda_k \Bigl( {n+1 \over \alpha_k} \Bigr)^\gamma 
   = A \sum_{1�k�p} \biggl( {\lambda_k \over \alpha_k{}^\gamma} 
       \biggr) (n+1)^\gamma 
   = A (n+1)^\gamma \cr 
}$$

Ceci {\'e}tablit l'assertion au rang $n+1$.
\smallskip

\textbf{Th{\'e}or{\`e}me 3}: la donn{\'e}e de $u_1>0$ et la relation de r{\'e}currence 
$$
 u_n 
 = a + \sum_{1�k�p} \lambda_k u_{\lfloor n/\alpha_k \rfloor} 
$$

d{\'e}finissent une suite $(u_n)_{n�1}$ de r{\'e}els positifs; 
cette suite v{\'e}rifie $u_n = \Theta(n^\gamma)$.
\smallskip

\textbf{Exemple}: l'{\'e}tude de la \emph{suite de Hamming} (Dijkstra, 
\emph{A Discipline of Programming}) am{\`e}ne {\`a} 
la r{\'e}currence $\displaystyle T(n) = a + T(n/2) + T(n/3) + T(n/5)$; 
avec les notations de l'{\'e}nonc{\'e}, $p=3$, $\lambda_1=\lambda_2=\lambda_3 = 1$, 
$\alpha_1=2$, $\alpha_2=3$, $\alpha_3=5$. 
Avec une calculatrice, on trouve $\gamma \approx 1.032812266$ 
(merci {\`a} Michel Quercia), et $T_n = \Theta(n^\gamma)$.
\smallskip

\subpart{Deuxi{\`e}me partie}

Nous allons nous int{\'e}resser maintenant aux suites $(u_n)_{n�1}$ v{\'e}rifiant 
la relation de r{\'e}currence 
$\displaystyle u_n = a + \sum_{1�k�p} \lambda_k u_{\lceil n/\alpha_k \rceil}$.
\smallskip

Commen{\c c}ons par r{\'e}gler un probl{\`e}me urgent: quels sont les termes 
dont il faut disposer pour "amorcer" la r{\'e}currence? On constate que, pour 
$\alpha>1$:
$$
 \lceil n/\alpha \rceil < n 
 \Leftrightarrow 
 \lceil n/\alpha \rceil � n - 1 
 \Leftrightarrow 
 {n \over \alpha} � n - 1 
 \Leftrightarrow 
 1 � \Bigl( 1 - {1 \over \alpha} \Bigr) n 
 \Leftrightarrow 
 n � {1 \over 1 - {1 \over \alpha}} = {\alpha \over \alpha - 1} 
 \Leftrightarrow 
 n � \Bigl\lceil {\alpha \over \alpha - 1} \Bigr\rceil 
$$

Notons $\displaystyle s(\alpha) 
 = \Bigl\lceil {\alpha \over \alpha - 1} \Bigr\rceil$ 
et $\displaystyle N = s(\alpha_1) = \max_{1�k�p} s(\alpha_k)$. 
Pour {\^e}tre {\`a} m{\^e}me de calculer les termes de la suite, 
il est n{\'e}cessaire et suffisant de conna{\^\i}tre les termes d'indice 
$n$ compris entre 1 (inclus) et $N$ (exclus).
\smallskip

\textbf{Th{\'e}or{\`e}me 4}: si une suite $(u_n)_{n�1}$ de r{\'e}els v{\'e}rifie 
$\displaystyle u_n � a + \sum_{1�k�p} \lambda_k u_{\lceil n/\alpha_k \rceil}$ 
pour tout $n�2$, alors $u_n = \Omega(n^\gamma)$.
\smallskip

\textbf{Preuve}: notons $\displaystyle A = \min_{1�n<N} {u_n \over n^\gamma}$ 
et prouvons que $u_n � A n^\gamma$ pour tout $n�1$. 
Pour $1�n<N$, la minoration r{\'e}sulte du choix de $A$. 
Supposons cette minoration acquise jusqu'au rang $n�N-1$ inclus. 
Alors, en utilisant 
$\displaystyle \Bigl\lceil {n+1 \over \alpha_k} \Bigr\rceil � n$ 
et $\lceil x \rceil � x$:
$$\eqalign{
 u_{n+1} 
 & = \sum_{1�k�p} \lambda_k u_{\lceil (n+1)/\alpha_k \rceil} 
   � \sum_{1�k�p} \lambda_k A \Bigl( \Bigl\lceil 
     {n+1 \over \alpha_k} \Bigr\rceil \Bigr)^\gamma 
   � A \sum_{1�k�p} \lambda_k \Bigl( {n+1 \over \alpha_k} \Bigr)^\gamma \cr 
 & = A \biggl( \sum_{1�k�p} {\lambda_k \over \alpha_k{}^\gamma} \biggr)  
     (n+1)^\gamma 
   = A (n+1)^\gamma \cr 
}$$

Ceci {\'e}tablit l'assertion au rang $n+1$.
\smallskip

\textbf{Th{\'e}or{\`e}me 5}: si une suite $(u_n)_{n�1}$ de r{\'e}els v{\'e}rifie 
$\displaystyle u_n � a + \sum_{1�k�p} \lambda_k u_{\lceil n/\alpha_k \rceil}$ 
pour tout $n�2$, alors $u_n = {\cal O}(n^\gamma)$.
\smallskip

\textbf{Preuve}: pour {\'e}tablir cette majoration, il faut travailler un peu plus. 
Notons $N' = \lfloor \alpha_p (N-1) \rfloor + 1$; pour 
$k\in\cro[1,p]$, on a:
$$
 n � N' 
 \Rightarrow 
 n > \alpha_p (N-1) 
 \Rightarrow 
 n > \alpha_k (N-1) 
 \Rightarrow 
 {n \over \alpha_k} > N-1 
 \Rightarrow 
 \Bigl\lceil {n \over \alpha_k} \Bigr\rceil � N 
$$

Soit $C$ un r{\'e}el strictement sup{\'e}rieur {\`a} 
$\displaystyle {\alpha_1 \over \alpha_1 - 1}$; on a certainement $C>1$. 
\emph{Remarque}: en fait, on peut prendre 
$\displaystyle C = {\alpha_1 \over \alpha_1 - 1}$ sauf dans le cas 
o{\`u} $\alpha_1=2$. 
Notons $\displaystyle B = \max_{N�n<N'} {u_n \over (n-C)^\gamma}$ 
et prouvons que 
$u_n � B (n-C)^\gamma$ pour tout $n�N$. 
Pour $N�n<N'$, cette majoration r{\'e}sulte du choix de $B$. 
Supposons la majoration acquise pour tout indice compris entre $N$ et 
$N'-1$ inclus. Alors, pour tout $k\in\cro[1,p]$, on a 
$\displaystyle N � \Bigl\lceil {n+1 \over \alpha_k} \Bigr\rceil �n$, 
donc:
$$\eqalign{
 u_{n+1} 
 & = \sum_{1�k�p} \lambda_k u_{\lceil (n+1)/\alpha_k \rceil} 
   �  \sum_{1�k�p} \lambda_k B \Bigl( \Bigl\lceil 
     {n+1 \over \alpha_k} \Bigr\rceil - C \Bigr)^\gamma 
   � B \sum_{1�k�p} \lambda_k \Bigl( 
     {n+1 \over \alpha_k} + 1 - C \Bigr)^\gamma \cr 
 & = B \sum_{1�k�p} {\lambda_k \over \alpha_k{}^\gamma} 
     \bigl( n + 1 + (1-C) \alpha_k \bigr) \cr 
}$$

Mais 
$\displaystyle 1 - C < 1 - {\alpha_1 \over \alpha_1 - 1} 
 = - {1 \over \alpha_1 - 1} < 0$; donc 
 $\displaystyle (1-C) \alpha_k � (1-C) \alpha_1 
 � - {\alpha_1 \over \alpha_1 - 1} < - C$ 
si bien que $n + 1 + (1-C) \alpha_k � n + 1 - C$. On en d{\'e}duit 
$$
 u_{n+1} 
 � B \biggl( \sum_{1�k�p} {\lambda_k \over \alpha_k{}^\gamma} \biggr) 
   (n+1-C)^\gamma 
 = B  (n+1-C)^\gamma 
$$

ce qui {\'e}tablit la majoration au rang $n+1$.
\smallskip

\textbf{Th{\'e}or{\`e}me 5}: si une suite $(u_n)_{n�1}$ de r{\'e}els v{\'e}rifie 
$\displaystyle u_n 0 a + \sum_{1�k�p} \lambda_k u_{\lceil n/\alpha_k \rceil}$ 
pour tout $n�2$, alors $u_n = \Theta(n^\gamma)$.

\textbf{Exemple}: l'exercice 8.3 du monumental 
\emph{Introduction to Algorithms} de Cormen, Leiserson et Rivest 
propose d'{\'e}tudier une curieuse m{\'e}thode de tri, baptis{\'e}e 
\emph{Stooges Sort} (r{\'e}f{\'e}rence cin{\'e}matographique {\`a} des 
comiques am{\'e}ricains des ann{\'e}es trente, connus en France comme 
les \emph{Trois Nigauds}). 
On est amen{\'e} {\`a} {\'e}tudier la suite $(C_n)_{n�2}$ d{\'e}finie 
par $C_2=1$ et $C_n = 3 C_{\lceil 2n/3 \rceil}$ pour $n�3$. 
Avec nos notations, $p=1$, $\lambda_1=3$ et $\alpha_1=3/2$; 
donc $\gamma = {\ln 3 \over \ln 3/2}$. 
Id{\'e}e reprise dans l'exercice IV.10 du \emph{Cours et Exercices d'Informatique}, 
qui attribue cette m{\'e}thode aux \emph{Pieds Nickel{\'e}s}, plus connus 
du public fran{\c c}ais.Question apparue {\'e}galement 
au contr{\^o}le du 2 f{\'e}vrier 1997 du Magist{\`e}re MMFAI de l'{\'E}cole 
Normale Sup{\'e}rieure de Paris, sous le nom de \emph{Strangesort}. 
\smallskip

\endsignal
