Lycée Louis-Le-Grand, Paris Pour le 20/09/2016

MPSI 4 – Mathématiques
A. Troesch

DM no 2 : Récurrences, ensembles

Exercice – (Autour de la suite de Fibonacci)

On définit la suite de Fibonacci (Fn )n∈N par :

F0 = 0, F1 = 1, ∀n > 2, Fn = Fn−1 + Fn−2 .

1. Calculer les 10 premiers termes de la suite de Fibonacci.

2. Montrer que (Fn )n∈N est croissante, et que pour tout n ∈ N, Fn > n − 1. Quelle est la limite de (Fn )n∈N ?
3. Montrer les relations suivantes :
Xn
(a) ∀n > 1, Fk2 = Fn Fn+1 .
k=1
(b) ∀n > 1, Fn (Fn−1 + Fn+1 ) = F2n et Fn2 + Fn+1
2
= F2n+1 .
Xn
(c) ∀n > 0, Fk = Fn+2 − 1.
k=0
n−1
X
(d) ∀n > 1, F2k+1 = F2n .
k=0
Xn
(e) ∀n > 0, F2k = F2n+1 − 1.
k=0
p  
X p
(f) ∀n > 0, ∀p > 0, Fn+k = Fn+2p .
k
k=0
(g) ∀n > 1, Fn2 = Fn−1 Fn+1 + (−1)n+1 .
(h) ∀m > 0, ∀n > 1, Fm+n = Fm+1 Fn + Fm Fn−1 .
n Xn−i   
∗
X n−i n−j
(i) ∀n > 0, = F2n+2 .
i=0 j=0
j i
(On pourra essayer de trouver une relation similaire pour F2n+3 ; cette relation peut se deviner lors des
tentatives pour prouver le caractère héréditaire de la formule à montrer)
4. Montrer que pour tout n ∈ N, Fn+1 est égal au nombre de façon de placer bout-à-bout des carrés de côté 1 et
des dominos 1 × 2 de sorte à former une rangée de longueur n (les carrés sont deux-à-deux indiscernables, ainsi
que les dominos).
Si vous le souhaitez, vous pouvez essayer de retrouver à l’aide de cette interprétation combinatoire les formules de
la question précédente (comptez certains ensembles de configurations de deux façons différentes ; pour savoir quelles
configurations rechercher, s’aider du côté simple de l’identité ; pour obtenir une somme, trier suivant un certain critère).
3 3
∗∗
5. Montrer que pour tout n, Fn+2 + Fn+1 − Fn3 est un nombre de Fibonacci (on calculera cette expression pour
des petites valeurs de n, et on comparera avec les valeurs de la question 1, afin de trouver une conjecture).
∗
6. (théorème de Zeckendorf, ou décomposition de n dans la base de Fibonacci)
Montrer que tout entier n > 0 s’écrit de manière unique comme une somme de nombres de Fibonacci non nuls,
distincts et non consécutifs (commencez par trouver les plus grands termes de la décomposition).
∗
7. Application : un jeu d’allumettes.
Deux joueurs tirent à tour de rôle des allumettes d’une boîte, avec les règles suivantes :
• Chaque joueur tire à chaque fois au moins une allumette.
• Le premier joueur ne retire pas la totalité des allumettes au premier tour.
• Un joueur tire au plus deux fois le nombre d’allumettes tirées par le joueur précédent.
• Le joueur qui retire la dernière allumette a gagné.
Montrer que si le nombre initial d’allumettes n’est pas un nombre de Fibonacci, la stratégie consistant à
tirer autant d’allumettes que le plus petit terme de la décomposition dans la base de Fibonacci du nombre
d’allumettes restantes peut être menée jusqu’au bout et constitue une stratégie gagnante pour le joueur 1.
Que dire du cas où le nombre initial d’allumettes est un nombre de Fibonacci ?

1
Problème – Lemme de classe monotone
Le but de ce problème est d’établir le lemme de classe monotone, aussi appelé lemme λ-π de Dynkin. Ce lemme est
à la base de la démontration du fait que la fonction de répartition d’une variable aléatoire caractérise la loi de cette
variable aléatoire, et d’autres résultats similaires en théorie de la mesure.
Soit Ω un ensemble. Pour tout A ⊂ Ω, on note A son complémentaire dans Ω. On appelle σ-algèbre (ou tribu) sur Ω
un sous-ensemble A de P(Ω) tel que :
• Ω∈A
• si A ∈ A, alors A ∈ A [
• pour toute famille (An )n∈N telle que pour tout n ∈ N, An ∈ A, on a aussi An ∈ A.
n∈N

On appelle classe monotone (ou λ-système) un sous-ensemble M de P(Ω) tel que :

• Ω∈M
• si A et B sont dans M, et A ⊂ B, alors B \ A est aussi dans M.
• pour toute famille (An )n∈N telle que pour tout n
[∈ N, An ∈ M, et croissante pour l’inclusion (c’est-à-dire telle
que pour tout n ∈ N, An ⊂ An+1 ), on a aussi An ∈ M.
n∈N

Partie I – Autour des σ-algèbres

1. Montrer que P(Ω) est une σ-algèbre. Quelle est la plus petite σ-algèbre sur Ω ?
2. (a) Soit A une σ-algèbre. Montrer que :
(i) ∅ ∈ A
(ii) si A et B sont dans A, alors A ∪ B aussi
(iii) si A et B sont dans A, alors A ∩ B aussi
\
(iv) si (An )n∈N est une famille d’éléments de A, alors An est aussi dans A.
n∈N
\
3. Montrer que si (Ai )i∈I est une famille de σ-algèbres, alors Ai est une σ-algèbre.
i∈I
\
4. Soit C un sous-ensemble de P(Ω), et AC l’ensemble des σ-algèbres A telles que C ⊂ A. En considérant A,
A∈AC
montrer qu’il existe une σ-algèbre σ(C), minimale au sens de l’inclusion, et contenant C. On dit que σ(C) est la
σ-algèbre (ou tribu) engendrée par C.
5. Décrire σ(C) lorsque :
• C = {A}, où A ⊂ Ω
• C est une partition (Ai )i∈I de Ω, I étant fini.
6. On définit B la σ-algèbre sur R engendrée par les intervalles ] − ∞, a], a ∈ R. La σ-algèbre B est appelée tribu
des boréliens de R.
Montrer que B est aussi la tribu engendrée par les intervalles [a, +∞[.

Partie II – Autour des classes monotones

1. Montrer qu’une σ-algèbre est une classe monotone.

2. Soit M une classe monotone.
(a) Montrer que ∅ ∈ M
(b) Montrer que si A ∈ M, alors A ∈ M.
\
(c) Montrer que si (An )n∈N est une suite d’éléments de M décroissante pour l’inclusion, alors An ∈ M.
n∈N
3. Montrer qu’une intersection (quelconque) de classes monotones est une classe monotone.
4. Soit C un sous-ensemble de P(Ω). Montrer qu’il existe une plus petite classe monotone m(C) au sens de l’inclusion
(appelée classe monotone engendrée par C), contenant C. Décrire cette classe sous forme d’une intersection.
5. Montrer que m(C) ⊂ σ(C).

2
Partie III – Lemme de classe monotone

On souhaite montrer qu’avec une hypothèse supplémentaire sur C, on peut obtenir l’égalité m(C) = σ(C).
1. Soit M une classe monotone stable par intersections finies (donc si A et B sont dans M, A ∩ B aussi)
n
\ n
[
(a) Montrer que pour toute famille finie (Ai )i∈[[1,n]] d’éléments de M, Ai et Ai sont dans M.
i=1 i=1
(b) Montrer que M est une σ-algèbre
2. Jusqu’à la fin de cette partie, on suppose que C est un π-système, c’est à dire un sous-ensemble de P(Ω) stable
par intersections finies.
(a) Soit A ∈ m(C). On définit
DA = {B ∈ m(C) | A ∩ B ∈ m(C)}.
Montrer que DA est une classe monotone.
(b) Soit C ∈ C. Montrer que C ⊂ DC , puis que DC = m(C)
(c) En déduire que DA = m(C).
3. Montrer que m(C) = σ(C).

Partie IV – Caractérisation des mesures bornées

Une mesure (positive) sur une σ-algèbre A est une application :

µ : A −→ [0, +∞],

telle que pour toute famille (An )n∈N d’éléments deux à deux disjoints de A, on ait :
+∞
! +∞
G X
µ An = µ(An ).
n=0 n=0

C’est une façon de mesurer la taille des ensembles de A. Notez que la valeur +∞ est possible.
On dit que cette mesure est bornée, si elle est à valeurs dans un intervalle [0, M ], pour M assez grand différent de
+∞.
On se donne une mesure µ sur une σ algèbre A.
1. Montrer que pour tout (A, B) ∈ A2 si A ⊂ B, alors µ(A) 6 µ(B).
2. Montrer que µ est bornée si et seulement si µ(Ω) 6= +∞. On suppose désormais que cette condition est réalisée.
3. Montrer que pour tout (A, B) ∈ A2 , si A ⊂ B, alors µ(B \ A) = µ(B) − µ(A).
4. On considère µ et ν deux mesures bornées sur A, telles que µ(Ω) = ν(Ω), et un π-système C tel que µ et ν
coïncident sur C, c’est-à-dire :
∀C ∈ C, µ(C) = ν(C).
Montrer que µ et ν coïncident sur σ(C).
On pourra commencer par montrer que {A ∈ A | µ(A) = ν(A)} est une classe monotone.
5. Soit µ et ν deux mesures bornées sur B la tribu des boréliens, et Fµ et Fν les fonctions sur R définies pour tout
x ∈ R par :
Fµ (x) = µ(] − ∞, x]), et Fν (x) = ν(] − ∞, x]).
Montrer que µ = ν si et seulement si Fµ = Fν .
Étant donnée une variable aléatoire X à valeurs réelles, si µX est la mesure définie sur un borélien B ∈ B par
µX (B) = P (X ∈ B) (on peut montrer qu’il s’agit bien d’une mesure, appelée loi de X), la fonction FµX n’est autre
que la fonction de répartition de X. On a ainsi montré que la fonction de répartition de X détermine entièrement la
loi µX de X.