Lycée Louis-Le-Grand, Paris Pour le 03/01/2017

MPSI 4 – Mathématiques
A. Troesch

DM no 11 : Intégration, suites

Exercice –
1. Intégrales de Wallis.
Z π
2
Soit, pour n ∈ N, In = sinn x dx.
0
n
(a) Montrer que pour tout n > 1, In+1 = · In−1 .
n+1
(b) En déduire une expression explicite de I2p et de I2p+1 à l’aide de factorielles.
In+1 n
(c) Montrer que pour tout n ∈ N, 1 > > .
In n+1
(d) En déduire la formule de Wallis :
√ (2p)! 1
lim p · 2p = √ .
p→+∞ 2 (p!)2 π
2. Formule de Stirling.
n!en
Soit, pour n ∈ N∗ , Sn = ln √ . On admettra que pour toute suite (un ) de limite nulle,
nn n

u2n u3
ln(1 + un ) = un − + n + O(u4n ).
2 3
α
(a) Montrer qu’il existe un réel α non nul qu’on déterminera tel que Sn − Sn−1 ∼
+∞ n2
+∞
X 1
(b) À l’aide d’une comparaison avec une intégrale, montrer que est convergente.
k2
k=1
(c) En déduire que (Sn ) admet une limite finie S dans R.
n!en σ2
(d) Soit, pour n ∈ N∗ , σn = n √ . En considérant n , déterminer la valeur de S.
n n σ2n
n −n
√
(e) En déduire la formule de Stirling : n! = n e 2πn(1 + o(1)).

Dans le problème qui suit, on pourra admettre que si (un ) est une suite récurrence linéaire, vérifiant pour tout n ∈ N,
un+k = ak−1 un+k−1 + · · · + a0 un , et si le polynôme P (X) = X k − ak−1 X k−1 − · · · − a0 admet k racines distinctes
r1 , . . . , rk , alors (un ) peut s’écrire comme combinaison linéaire des suites (rin ).

Problème 1 –

PARTIE I – Étude d’une suite définie par une récurrence linéaire.

1. On considère l’équation P (x) = x3 − x2 − 2x + 1 = 0. Montrer qu’elle admet trois racines réelles distinctes
x1 < x2 < x3 vérifiant −2 < x1 < −1 < 0 < x2 < 1 < x3 < 2 et x1 + x2 + x3 = 1.
2. Montrer que |x2 | < |x1 | < |x3 |.
3. Soit (an )n∈N la suite définie par les conditions initiales a0 = 0, a1 = 0 et a2 = 1 et la relation an+3 =
an+2 + 2an+1 − an . Montrer que la suite (an )n∈N est croissante, et que pour tout n > 2, an > 0.
4. Expliciter en fonction de x1 , x2 et x3 des coefficients λ1 , λ2 et λ3 tels que

∀n ∈ N, an = λ1 xn1 + λ2 xn2 + λ3 xn3 ,

et vérifier que les coefficients λ1 , λ2 et λ3 sont non nuls.

Dans la suite du problème, il est demandé de ne pas utiliser les expressions explicites de λ1 , λ2 et λ3 .
5. Montrer que an est équivalente à une suite géométrique, qu’on exprimera en fonction de x1 , x2 , x3 , λ1 , λ2 et
λ3 .

1
 an+1
6. Déterminer, en fonction de x1 , x2 et x3 , la limite de bn = .
an

PARTIE II – Étude et amélioration de la vitesse de convergence de (bn )n∈N .

 n
λ1 x1
1. Soit pour tout n ∈ N, εn = bn − x3 . Montrer que εn ∼ (x1 − x3 ) .
+∞ λ3 x3
 n 
x1
2. En déduire que |bn − x3 | = O .
x3
!
2
x2 x2 x1 x1 x1
3. On pose β = max , , . Vérifier que β < , et montrer que
x3 x23 x3 x3
 n
λ1 x1
bn − x3 − (x1 − x3 ) = O(β n ).
λ3 x3
 n 
bn+1 − bn x1 βx3
4. Pour tout n > 3, on pose cn = . Justifier que cn − =O .
bn − bn−1 x3 x1
bn+1 − cn bn
5. Pour tout n > 3, on pose dn = . Montrer que dn − x3 = O(β n ). En quoi peut-on dire qu’on a
1 − cn
accéléré la convergence de la suite ?
6. Écrire une fonction en Python prenant en paramètre un entier n, et retournant la valeur de dn .

Problème 2 – Estimation de la complexité d’algorithmes de type diviser pour régner

Un algorithme de type « diviser pour régner » est un algorithme récursif ramenant la résolution d’un problème de taille
n à la résolution d’un ou plusieurs problèmes de taille nb (à ±1 près pour avoir un entier). Ainsi, la complexité d’un
tel algorithme vérifiera une relation du type :
j n k l n m
∀n > 2, T (n) = αT + βT + un , (1)
b b
initialisée par la donnée de T (0) et T (1). Dans cette expression, ⌊x⌋ désigne la partie entière (par défaut) de x, et
⌈x⌉ désigne la partie entière par excès de x, b est un certain entier supérieur ou égal à 2, et α et β sont des entiers
naturels tels que α + β > 1.
Le but du problème est d’étudier le comportement asymptotique de suites vérifiant la relation de récurrence (1). Ce
comportement dépendra fortement de l’ordre de grandeur de un .
On note dans tout le problème a = α + β et γ = logb (a). Ainsi, bγ = a. Par ailleurs, on note, pour tout n ∈ N,
ℓ(n) = ⌊logb (n)⌋ et ℓ′ (n) = ⌈logb (n)⌉.
Enfin, on suppose que T (0) > 0 et T (1) > 0 et pour tout n ∈ N∗ , un > 0.
Question préliminaire
Montrer que pour tout n ∈ N, T (n) > 0.

Partie I – Cas où un = Θ(nγ )

Nous supposons dans cette partie que un = Θ(nγ ). Nous rappelons que ceci signifie que un = O(nγ ) et nγ = O(un ),
donc qu’il existe des réels m et M strictement positifs tels que

∀n ∈ N, mnγ 6 un 6 M nγ .

Les inégalités peuvent être prises pour tout n ∈ N∗ , car les deux suites ne s’annulent pas. Nous nous donnons deux
tels réels m et M .
logb (n) − ℓ(n)
1. Montrer que lim = 0.
n→+∞ ℓ(n)
En déduire que ℓ(n) ∼ logb (n).
+∞
On admettra qu’on a de même ℓ′ (n) ∼ logb (n).
+∞
j n k l n m
2. Montrer que ℓ = ℓ(n) − 1 et ℓ′ = ℓ′ (n) − 1
b b

2
 3. On note, pour tout k ∈ N,
k  
Y b−1
P (k) = 1+ i .
i=1
b
k
X b−1
Montrer que pour tout k ∈ N, ln(P (k)) 6 , et en déduire que P (k) est majorée.
i=1
bi
4. On note, pour n ∈ N∗ , Qn = P (ℓ′ (n) − 1).
 
b−1
Montrer que pour tout n > b, 1 + Q⌈ n ⌉ 6 Qn .
n b
 
T (n)
5. On définit K = max γ − M (ℓ ′
(n) − 1) . Montrer que pour tout n ∈ N∗ ,
n∈[[1,b−1]] nγ Qn

T (n)
6 Qγn (K + M (ℓ′ (n) − 1))
nγ
6. En déduire que T (n) = O(nγ logb (n)) puis T (n) = O(nγ ln(n)).
7. Adapter le raisonnement précédent pour prouver que T (n) = Ω(nγ ln(n)).
Ainsi, on a obtenu T (n) = Θ(nγ ln(n)).
8. L’algorithme d’exponentiation rapide étudié en cours d’informatique a une complexité vérifiant la relation
j n k
T (n) = T + un ,
2
où un = Θ(1). Déterminer le comportement asymptotique de T
9. L’algorithme de tri fusion a une complexité vérifiant la relation
j n k l n m
T (n) = T +T + un ,
2 2
où un = Θ(n). Montrer que le tri fusion a un coût en Θ(n ln(n)).

Partie II – Le cas un = O(nγ−ε ).

On suppose qu’il existe ε > 0 tel que un = O(nγ−ε ).
1. La suite Qn étant définie comme dans la partie 1, montrer qu’il existe K tel que pour tout n > 1,
 
ℓ′ (n)−1
T (n) X 1 
6 nε Qγn K + M .
nγ−ε i=0
b εi

2. En déduire que T (n) = O(nγ ).

3. Démontrer de même que T (n) = Ω(nγ ).
4. En considérant que l’addition se fait en temps linéaire, l’algorithme de Karatsuba étudié en TP a une complexité
vérifiant : l n m j n k
T (n) = 2T +T + un ,
2 2
où un = Θ(n). Quel est le comportement asymptotique de cette complexité ?
Il existe aussi une règle dans le cas où un = Ω(nγ+ε ). Dans ce cas, c’est la fonction un qui détermine la complexité :
avec certaines hypothèses supplémentaires sur un , on peut montrer que T (n) = θ(un ).

Problème 3 – Autour de la moyenne arithmético-géométrique

a+b √
Soit a et b deux réels positifs. On définit ma (a, b) = la moyenne arithmétique de a et b, et mg (a, b) = ab la
2
moyenne géométrique de a et b.
Question préliminaire : Comparaison des moyennes arithmétique et géométrique
Montrer que pour tout couple (a, b) de réels positifs, mg (a, b) 6 ma (a, b).

Partie I – Définition de la moyenne arithmético-géométrique

Soit (a, b) ∈ R2+ . On définit deux suites (an )n∈N et (bn )n∈N par les relations :

( an + b n
a0 = a, 
an+1 = = ma (an , bn )
, et ∀n ∈ N, √ 2
b0 = b  bn+1 = an bn = mg (an , bn )

3
 1. Montrer que (an )n∈N et (bn )n∈N sont convergentes. On note α et β leur limite respective.
2. Montrer que α = β.
On appelle moyenne arithmético-géométrique de a et b la valeur de cette limite commune, et on la note M (a, b).
3. Comparer M (a, b), ma (a, b) et mg (a, b).

Partie II – Expression intégrale de la moyenne arithmético-géométrique

On pose, pour tout x ∈ [0, 1[, et pour tout (λ, µ) ∈ R2 :
π π
dt dt
Z 2
Z 2
I(x) = p et J(λ, µ) = q .
0 1 − x2 sin2 t 0 λ2 cos2 (t) + µ2 sin2 (t)
 √ 
2 x
1. Montrer que pour tout x ∈ [0, 1[, (1 + x)I(x) = I .
1+x
 
(1 + x) sin(t)
Indication : changement de variable u = Arcsin
1 + x sin2 (t)
1+x √
 
2. En se ramenant à l’intégrale I, montrer que pour tout x ∈]0, 1], J(1, x) = J , x .
2
3. Soit a et b deux réels strictement positifs tels que a > b, et (an )n∈N et (bn )n∈N les suites définies en début de
partie I. Montrer que (J(an , bn ))n∈N est constante.
4. Soit ε > 0 tel que ε < M (a, b). Justifier l’existence de N ∈ N tel que pour tout n > N ,
π 1 π 1
· 6 J(an , bn ) 6 · .
2 M (a, b) + ε 2 M (a, b) − ε

5. En déduire une expression de M (a, b) en fonction de J(a, b).

Partie III – Une variante de la moyenne arithmético-géométrique

Soit toujours (a, b) ∈ (R∗+ )2 . On définit cette fois (an ) et (bn ) par :

( an + b n
a0 = a 
an+1 =
et ∀n ∈ N, p 2
b0 = b b = a
n+1 b n+1 n

1. En étudiant leur monotonie, montrer que (an ) et (bn ) convergent vers une limite commune (on pourra distinguer
les cas a 6 b et b 6 a)
2. Soit α un réel de ]0, π2 [, et pour tout n ∈ N,
n
Y α
Bn = cos .
2k
k=1

1 sin(α)
Montrer que pour tout n ∈ N, Bn =
.
2n sin 2αn
a
3. On suppose que a 6 b, et α = Arccos . Montrer que
b

 b · sin(α)
si α 6= 0
lim bn = α
n→+∞ b si α = 0.

4. On suppose de a > b. Montrer l’existence d’un unique réel α tel que a = ch(α)b, et montrer que

 b · sh(α)
si α 6= 0
lim bn = α
n→+∞ b si α = 0.