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

MPSI 4 – Mathématiques
A. Troesch

DM no 2 : Récurrences, ensembles

Correction de l’exercice –
1. Les 10 premières valeurs de Fn (c’est-à-dire de 0 à 9) :
F0 = 0 F1 = 1 F2 = 1 F3 = 2 F4 = 3
F5 = 5 F6 = 8 F7 = 13 F8 = 21 F9 = 34
2. Une récurrence immédiate montre que pour tout n ∈ N, Fn > 0. Alors, pour tout n ∈ N, Fn+1 = Fn +Fn−1 > Fn ,
donc (Fn )n∈N est croissante .
On a F0 > −1, F1 > 0 et F2 > 1. Ainsi, on peut débuter la récurrence au rang 2, l’initialisation venant d’être
faite.
Soit, pour tout n dans N \ {0, 1}, la propriété P(n): Fn > n − 1.
On vient de montrer P(2).
Soit n > 2. Supposons que P(n) soit vrai. Comme (Fn )n∈N est croissante et n − 1 > 1, on a Fn−1 > F1 > 1.
Ainsi,
Fn+1 = Fn + Fn−1 > (n − 1) + 1 > n.
D’où P(n + 1).
Par conséquent, P(2) est vraie, et pour tout n dans N \ {0, 1}, P(n) entraîne P(n + 1). D’après le principe de
récurrence, P(n) est vraie pour tout n dans N \ {0, 1}.
On peut conclure : pour tout n ∈ N, Fn > n − 1.
Puisque lim(n − 1) = +∞ le théorème de minoration amène lim Fn = +∞.
n
X
3. (a) Soit, pour tout n dans N∗ , la propriété P(n): Fk2 = Fn Fn+1 .
k=1
1
X
Pour n = 1 : Fk2 = F12 = 1 = F1 F2 , d’où P(1).
k=1
Soit donc n ∈ N∗ , et supposons que P(n) est vraie. Alors :
n+1
X n
X
Fk2 = Fk2 + Fn+1
2

k=1 k=1
2
= Fn Fn+1 + Fn+1 (d’après P(n))
= Fn+1 (Fn + Fn+1 )
= Fn+1 Fn+2 (d’après la relation de récurrence)

D’où P(n + 1).

Par conséquent, P(1) est vraie, et pour tout n dans N∗ , P(n) entraîne P(n + 1). D’après le principe de
récurrence, P(n) est vraie pour tout n dans N∗ .
n
X
Conclusion : ∀n ∈ N∗ , Fk2 = Fn Fn+1
k=1

(b) Nous montrons les deux identités en même temps.


Fn (Fn−1 + Fn+1 ) = F2n
Soit, pour tout n dans N∗ , la propriété P(n): .
Fn2 + Fn+1
2
= F2n+1
On vérifie sans problème P(1).
Soit n ∈ N∗ . Supposons que P(n) soit vrai. On a alors :

F2n+2 = F2n+1 + F2n

= Fn2 + Fn+1
2
+ Fn (Fn−1 + Fn+1 ) (d’après P(n))
= Fn+1 (Fn + Fn+1 ) + Fn (Fn + Fn−1 )
= Fn+1 Fn+2 + Fn Fn+1 = Fn+1 (Fn+2 + Fn ).

1
 Par ailleurs :

F2n+3 = F2n+2 + F2n+1

= Fn+1 (Fn+2 + Fn ) + F2n+1 (d’après l’égalité qu’on vient de démontrer)
= Fn+1 (Fn+2 + Fn ) + Fn2 + 2
Fn+1 (d’après P(n))
2
= Fn+1 + (Fn+2 − Fn )(Fn+2 + Fn ) + Fn2
2 2
= Fn+1 + Fn+2 .

Ainsi, P(n + 1) est vérifié.

Par conséquent, P(1) est vraie, et pour tout n dans N∗ , P(n) entraîne P(n + 1). D’après le principe de
récurrence, P(n) est vraie pour tout n dans N∗ .

Fn (Fn−1 + Fn+1 ) = F2n
Conclusion : ∀n ∈ N∗ ,
Fn2 + Fn+1
2
= F2n+1
Il est nécessaire dans cet argument de considérer les deux identités dans la propriété de récurrence, puisqu’on
les utilise en les croisant : l’une sert pour prouve l’autre au rang suivant.
On pourrait aussi démontrer séparément chacune des deux égalités, en montrant d’abord que pour tout
n ∈ N, Fn+4 = 3Fn+2 − Fn . C’est un bon exercice, que je vous laisse faire.
Enfin une troisième méthode, si on a un peu l’habitude du calcul matriciel, consiste à partir de l’égalité :
    
Fn 0 1 Fn
∀n ∈ N, = .
Fn+1 1 1 Fn−1
 n  
0 1 b
On en tire respectivement, en notant = :
1 1 d
   n    n    
Fn 0 1 F0 0 1 0 b
• ∀n ∈ N, = = = ,
Fn+1 1 1 F1 1 1 1 d
   n    n    
Fn+1 0 1 F1 0 1 1 a+b
• ∀n ∈ N, = = = ,
Fn+2 1 1 F 1 1 1 c+d
 n  2   
0 1 Fn+1 − Fn Fn Fn−1 Fn
• de quoi il vient : = = ;
1 1 Fn+2 − Fn+1 Fn+1 Fn Fn+1
• Il vient alors :
   n       
F2n+1 0 1 Fn+1 Fn−1 Fn Fn+1 Fn−1 Fn + Fn Fn+1
= = =
F2n 1 1 Fn Fn Fn+1 Fn Fn2 + Fn+1
2

n
X
(c) Soit, pour tout n dans N, la propriété P(n): Fk = Fn+2 − 1.
k=0
Pour n = 0, la relation à prouver est F0 = F2 − 1, qui est immédiate d’après les valeurs trouvées dans la
première question.
Soit n ∈ N. Supposons que P(n) est vraie. Alors :
n+1
X
Fk = Fn+2 − 1 + Fn+1 (d’après P(n))
k=0
= Fn+3 − 1 (d’après la relation de récurrence)

D’où P(n + 1).

Par conséquent, P(0) est vraie, et pour tout n dans N, P(n) entraîne P(n + 1). D’après le principe de
récurrence, P(n) est vraie pour tout n dans N.
n
X
On peut conclure : ∀n ∈ N, Fk = Fn+2 − 1.
k=0
Une façon plus rapide de procéder est de se ramener à une somme télescopique en utilisant la relation de
récurrence définissant (Fn ) :
n
X n
X
Fk = (Fk+2 − Fk+1 ) = Fn+2 − F1 = Fn+2 − 1.
k=0 k=0

2
 n−1
X
(d) Soit, pour tout n dans N, la propriété P(n): F2k+1 = F2n .
k=0
Pour n = 1, la relation à prouver est F1 = F2 , qui est immédiate d’après les valeurs trouvées dans la première
question, d’où P(1).
Soit n ∈ N∗ tel que P(n) soit vraie. Alors :
n
X
F2k+1 = F2n + F2n+1 (d’après P(n))
k=0
= F2n+2 .

D’où P(n + 1).

Par conséquent, P(0) est vraie, et pour tout n dans N, P(n) entraîne P(n + 1). D’après le principe de
récurrence, P(n) est vraie pour tout n dans N.
n−1
X
On conclut donc : ∀n ∈ N∗ , F2k+1 = F2n .
k=0
Ici aussi, on peut s’en sortir par une somme télescopique, en s’arrangeant pour avoir une progression de pas
égal à 2, donc en voyant le terme de la somme initiale comme le terme du milieu de la relation de récurrence :
n−1
X n−1
X
F2k+1 = F2k+2 − F2k = F2n − F0 = F2n .
k=0 k=O

(e) C’est exactement pareil, soit par récurrence, soit grâce à une suite télescopique, en remarquant que l’on
peut commencer la somme à 1.
n
X n
X
F2k = F2k+1 − F2k−1 = F2n+1 − F1 = F2n+1 − 1 .
k=0 k=1

(f) Un peu plus intéressant. On a ici deux variables. On fait le choix de faire une récurrence sur p (l’initialisation
d’une récurrence sur n nécessiterait de toute façon une récurrence sur p).
p  
X p
Soit, pour tout p dans N, la propriété Q(p): ∀n > 0, Fn+k = Fn+2p ..
k
k=0
Pour p = 0, la relation à montrer est Fn = Fn , d’où Q(0).
Soit p ∈ N. Supposons que Q(p) est vraie.
Soit donc n > 0 quelconque. Alors,
p+1   p  
X p+1 X p+1
Fn+k = Fn+k + Fn+p+1
k k
k=0 k=0
p   p  
X p X p
= Fn+k + Fn+k + Fn+p+1 (formule de Pascal)
k k−1
k=0 k=0
p  
X p
= Fn+2p + Fn+k + Fn+p+1 (Q(p) et suppression d’un terme nul)
k−1
k=1
p−1  
X p
= Fn+2p + Fn+1+k + Fn+p+1 (réindexation)
k
k=0
p  
X p
= Fn+2p + Fn+1+k
k
k=0
= Fn+2p + Fn+1+2p (Q(p), avec n′ = n + 1)
= Fn+2p+2 .

D’où Q(p + 1).

Par conséquent, Q(0) est vraie, et pour tout p dans N, Q(p) entraîne Q(p + 1). D’après le principe de
récurrence, Q(p) est vraie pour tout p dans N.
L’avant dernière étape nous empêche de faire une récurrence sur p à n fixé : il faut pouvoir considérer la
propriété simultanément pour plusieurs valeurs de n. C’est pour cela que nous avons quantifié n à l’intérieur
de la propriété Q.

3
 p  
X p
Nous pouvons conclure : ∀p ∈ N, ∀n ∈ N, Fn+k = Fn+2p .
k
k=0

Remarquez que la relation Q(1) n’est autre que la relation de récurrence de la suite.
(g) Encore une récurrence...
Soit, pour tout n dans N∗ , la propriété P(n): Fn2 = Fn−1 Fn+1 + (−1)n+1 .
On vérifie sans problème P(1).
Soit n ∈ N∗ . Supposons que P(n) est vraie. Alors :
2
Fn+1 − Fn Fn+2 = Fn+1 (Fn + Fn−1 ) − Fn (Fn+1 + Fn )
= Fn+1 Fn−1 − Fn2 (d’après la relation de récurrence)
n+1
= −(−1) (d’après P(n))
n+2
= (−1) .

Par conséquent, P(1) est vraie, et pour tout n dans N∗ , P(n) entraîne P(n + 1). D’après le principe de
récurrence, P(n) est vraie pour tout n dans N∗ .
Conclusion : ∀n ∈ N∗ , Fn2 = Fn−1 Fn+1 + (−1)n+1 .
Ici aussi, la méthode matricielle est efficace et découle directement de l’identité
 n  
0 1 Fn−1 Fn
= ,
1 1 Fn Fn+1

en écrivant l’égalité des déterminants de ces matrices et en utilisant le fait que le déterminant d’un produit
est le produit des déterminants (donc pour le terme de gauche, on obtient le déterminant
  puissance n, qui
a b
nous donne notre facteur (−1)n ). On rappelle que le déterminant d’une matrice est ad − bc. Les
c d
propriétés utilisées se vérifient facilement.
(h) On fait une récurrence sur m.
Soit, pour tout m dans N, la propriété P(m): ∀n > 1, Fm+n = Fm+1 Fn + Fm Fn−1 .
Pour m = 0, la relation à montrer est Fn = F1 Fn + F0 Fn−1 , ce qui est vrai pour tout n > 1, puisque F1 = 1
et F0 = 0. Ainsi, P(0) est vérifié.
Soit m ∈ N. Supposons que P(m) est vrai. Soit n ∈ N∗ . On a alors :

Fm+1+n = Fm+1 Fn+1 + Fm Fn (d’après P(m) pour n’=n+1)

= Fm+1 (Fn + Fn−1 ) + Fm Fn
= (Fm+1 + Fm )Fn + Fm+1 Fn−1
= Fm+2 Fn + Fm+1 Fn−1 .

D’où P(m + 1).

Par conséquent, P(0) est vraie, et pour tout m dans N, P(m) entraîne P(m + 1). D’après le principe de
récurrence, P(m) est vraie pour tout m dans N.
Conclusion : ∀m ∈ N, ∀n ∈ N∗ , Fm+n = Fm+1 Fn + Fm Fn−1
 n+m  n  m
0 1 0 1 0 1
Matriciellement, cela découle de l’étude de la matrice = et des expressions
1 1 1 1 1 1
de ces 3 matrices.
(i) Lorsqu’on cherche à prouver le caractère héréditaire de la formule à démontrer, on se rend compte, après une
utilisation du théorème de Pascal, et un réarrangement des sommes, qu’on parvient à prouver le caractère
héréditaire, à condition qu’une certaine somme de produits de coefficients binomiaux soit
égale à F2n+3 .
Nous montrons alors les deux identités simultanément. On adopte la convention usuelle np = 0 si p > n ou
si p < 0.
 n n−i   
X X n − i n − j

 = F2n+2


i=0 j=0
j i
Soit, pour tout n dans N, la propriété P(n): ∀n > 0, n n+1−i .
 X X n + 1 − in − j 
= F2n+3 − 1




i=0 j=0
j i
Pour n = 0, on obtient :

4
 n X
n−i    0 X
0   
X n−i n−j X 0 0
• = = 1 = F2 .
i=0 j=0
j i i=0 j=0
0 0
n n+1−i
X    X 0 X 1   
X n+1−i n−j 1 0−j
• m = = 1 = F3 − 1.
i=0 j=0
j i i=0 j=0
j 0
Ainsi, P(0) est vrai.
Soit n ∈ N, et supposons P(n). On a :
n+1
X n+1−i
X    n+1 X n + 1 − in + 1 − j  n+1
X n+1−i X n + 1
n+1−i n+1−j
= +
i=0 j=0
j i i=1 j=0
j i j=0
j
n+1
X n+1−i
X    n+1 X n + 1 − in − j  n+1
X n+1−i X n + 1
n+1−i n−j
= + +
i=1 j=0
j i i=1 j=0
j i−1 j=0
j
(formule de Pascal)
n n+1−i  
X n+1−i n−j  n Xn−i    n+1
X n + 1
X X n−i n−j
= + +
i=1 j=0
j i i=0 j=0
j i j=0
j
(suppression de 0 et réindexation)
n n+1−i  
X n+1−i n−j  n Xn−i   
X X n−i n−j
= + +1
i=0 j=0
j i i=0 j=0
j i
(réintégration de la dernière somme)
= F2n+2 + F2n+3
(d’après P(n))
= F2n+4

Le 1 apparaissant de façon

un peu mystérieuse au moment de réintégrer la troisième somme dans la première
provient du fait que n−j
0 = 1 pour tout j ∈ [[0, n + 1]] (ce qui nous permet de considérer la dernière somme
comme le terme correspondant à l’indice i = 0 de la première somme) SAUF pour j = n + 1...
La deuxième identité se montre de la même manière, en inversant le rôle des deux variables :
n+1
X n+2−i
X    n+1 X n + 2 − in + 1 − j  n+1
X n+2−i X n + 1
n+2−i n+1−j
= +
i=0 j=0
j i i=0 j=1
j i i=0
i
n+1
X n+2−i
X    n+1 X n + 1 − in + 1 − j  n+1
X n+2−i X n + 1
n+1−i n+1−j
= + +
i=0 j=1
j i i=0 j=1
j−1 i i=0
i
X n+1−i
n+1 X    X X n + 1 − in + 1 − j  n+1
n n+2−i X n + 1
n+1−i n+1−j
= + +
i=0 j=1
j i i=0 j=1
j−1 i i=0
i
n+1
X n+1−i
X    X n n+1−i
X n + 1 − in − j 
n+1−i n+1−j
= +
i=0 j=0
j i i=0 j=0
j i
= F2n+3 − 1 + F2n+4
= F2n+5 − 1,

l’avant-dernière égalité provenant de l’hypothèse de récurrence, et de la première étape du calcul. Ainsi, on

a prouvé P(n + 1).
Par conséquent, P(0) est vraie, et pour tout n dans N, P(n) entraîne P(n + 1). D’après le principe de
récurrence, P(n) est vraie pour tout n dans N.
n Xn−i   
X n−i n−j
En isolant ce qui nous intéresse, on obtient donc : ∀n ∈ N, = F2n+2 .
i=0 j=0
j i

4. Soit pour tout n ∈ N, Gn le nombre de disposition de carrés et dominos pour obtenir une ligne de longueur n.
• Si n = 0, seule la disposition vide convient, donc G0 = 1
• Si n = 1, une ligne de longueur 1 ne peut être couverte que par un carré. Donc G1 = 1.
• Soit n > 3. On sépare l’ensemble des dispositions possibles donnant une ligne de longueur n suivant la
nature de la première pièce :

5
 ∗ si la première pièce est un carré, il reste ensuite à contruire une ligne de longueur n − 1 avec des carrés
et des dominos, ce qui laisse Gn−1 configurations possibles ;
∗ si la première pièce est un domino, il reste ensuite à contruire une ligne de longueur n − 2 avec des carrés
et des dominos, ce qui laisse Gn−2 configurations possibles ;
Ainsi, on obtient Gn = Gn−1 + Gn−2 .
• Par conséquent, puisque G0 = F1 et G1 = F2 , les suites (Gn )n∈N∗ et (Fn+1 )n∈N∗ vérifient la même relation
de récurrence, et sont initialisées de la même façon, donc pour tout n ∈ N∗ , Gn = Fn+1 .
5. Des essais pour des petites valeurs de n laissent penser que pour tout n > 1,
3
Fn+1 + Fn3 − Fn−1
3
= F3n .

Nous allons le montrer par récurrence, mais pour cela, nous devons d’abord établir une relation entre les termes
d’indices multiples de 3. Soit n ∈ N. On a :

F3n+6 = F3n + 3F3n+1 + 3F3n+2 + F3n+3 (question 3e)

= F3n + 3F3n+1 + 3(F3n+3 − F3n+1 ) + F3n+3 (d’après la relation de récurrence)
= 4F3n+3 + F3n .

Ainsi : ∀n ∈ N, F3n+6 = 4F3n+3 + F3n .

Nous démontrons maintenant la relation annoncée, à l’aide d’une récurrence d’ordre 2.
3
Soit, pour tout n dans N∗ , la propriété P(n): Fn+1 + Fn3 − Fn−1
3
= F3n .
Les propriétés P(1) et P(2) se vérifient bien à l’aide des valeurs trouvées dans la première question.
Soit n ∈ N∗ . Supposons que P(n) et P(n + 1) sont vérifiés. On a alors, d’après la relation prouvée en début de
question :

F3n+6 = 4F3n+3 + F3n

3 3
= 4Fn+2 + 4Fn+1 − 4Fn3 + Fn+1
3
+ Fn3 − Fn−1
3
(utilisation de P(n) et P(n + 1))
3 3
= 4Fn+2 + 5Fn+1 − 3Fn3 − Fn−1
3

= (Fn+3 − Fn+1 )3 + Fn+2

3
+ 2(Fn + Fn+1 )3 + 5Fn+1
3 3
− 3Fn3 − Fn−1 (bidouillage sur le premier terme)
3 3 2 2 3 3
= Fn+3 + Fn+2 + 3Fn+3 Fn+1 − 3Fn+3 Fn+1 − Fn+1 + 2Fn+1
2
+ 6Fn Fn+1 + 6Fn2 Fn+1 + 2Fn3 + 5Fn+1
3
− 3Fn3 − Fn−1
3
(développement)
3 3 2
= Fn+3 + Fn+2 + 3(2Fn+1 + Fn )Fn+1 − 3(2Fn+1 + Fn )2 Fn+1
3 2
+ 6Fn+1 + 6Fn+1 Fn + 6Fn+1 Fn2 − Fn3 − Fn−1
3
(car Fn+3 = 2Fn+1 + Fn )
3 3 2
= Fn+3 + Fn+2 − 3Fn+1 Fn + 3Fn+1 Fn2 − Fn3 − Fn−1
3
(simplification)
3 3 3
= Fn+3 + Fn+2 − Fn+1 + (Fn+1 − Fn )3 − Fn−1
3

3 3 3
= Fn+3 + Fn+2 − Fn+1 (d’après la relation de récurrence)

Par conséquent, P(1) et P(2) sont vraies, et pour tout n dans N∗ , P(n) et P(n + 1) entraînent P(n + 2). D’après
le principe de récurrence, P(n) est vraie pour tout n dans N∗ .
3
Conclusion (et on peut en être fier) : ∀n > 1, Fn+1 + Fn3 − Fn−1
3
= F3n .
Voici deux autres égalités, exprimant F3n+1 et F3n+2 .
2 2
F3n+1 = Fn+1 (Fn+1 + Fn Fn+2 ) − Fn Fn−1
2
F3n+2 = Fn+1 (Fn+2 + Fn2 ) + Fn Fn−1
2
.

On peut s’amuser à démontrer simultanément les trois relations (pour F3n , F3n+1 et F3n+2 ), à la manière de la
question 3b. C’était une autre façon de répondre à la question : le plus dur consistait alors à deviner les deux
relations pour F3n+1 et F3n+2 . Vous pouvez aussi constater que matriciellement, deux de ces trois relations
correspondent au calcul de
   n  n    2  
F3n 0 1 0 1 Fn Fn−1 Fn Fn
= = ,
F3n+1 1 1 1 1 Fn+1 Fn Fn+1 Fn+1

suivi de
  quelques manipulations simples (la troisième égalité se démontre en multipliant une fois de plus par
0 1
).
1 1

6
6. Soit, pour tout n dans N, la propriété P(n): « n se décompose de façon unique comme somme de nombres de
Fibonacci non nuls distincts et non consécutifs ».
• Pour n = 0, n est une somme vide de nombres de Fibonacci, forcément distincts et non consécutifs ! Cette
décomposition est nécessairement unique. Ainsi, P(0) est vraie.
• Soit n ∈ N∗ . On suppose que P(k) est vrai pour tout k ∈ [[0, n − 1]]. L’ensemble A = {p ∈ N | Fp 6 n} est
un sous-ensemble borné de N car Fp → +∞. Il est non vide, car 1 ∈ A. On peut donc considérer son plus
grand élément k. Alors Fk 6 n < Fk+1 .
• Toute décomposition admissible comprend le terme Fk . En effet, sinon, son plus grand terme est au plus
égal à Fk−1 . En notant alors Fj1 + · · · + Fjℓ = n une telle décomposition, alors j1 < j2 < · · · < jℓ , on a
alors jℓ 6 k − 1, puis jℓ−1 6 jℓ − 2 6 k − 3, puis jℓ−2 6 k − 5 etc. La suite de Fibonacci étant croissante et
positive, il vient alors :
k−1
X
n 6 Fk−1 + Fk−3 + Fk−5 = Fℓ < Fk 6 n,
ℓ=2
ℓ et k de même parité

l’avant dernière inégalité provenant de 3(d) ou 3(e) suivant la parité de n, et du fait que la somme ne
commence qu’à 2 (les termes de la décomposition de Zeckendorff étant au moins d’indice 2).
Cette contradiction nous assure que le plus grand terme de la décomposition de Zeckendorff, si elle existe,
est Fk .
• Les autres termes de la décomposition constitue alors une décomposition admissible de n − Fk , et sont donc
déterminés de façon unique par hypothèse de récurrence, puisque n − Fk < n.
Cela prouve l’unicité de la décomposition de Zeckendorff, sous réserve d’existence.
• L’existence se prouve alors en vérifiant que la décomposition obtenue en ajoutant Fk à une décomposition
admissible de n − Fk est aussi admissible, c’est-à-dire constituée de termes 2 à 2 non consécutifs. C’est le
cas si n = Fk (la partie provenant de n − Fk est alors vide, et la décomposition ne comporte qu’un terme).
Supposons alors n 6= Fk . La décomposition de n − Fk est alors non vide et constituée de termes de Fibonacci
deux à deux non consécutifs. Il suffit alors de vérifier que son plus grand terme Fℓ vérifie ℓ 6 k − 2. Ceci
provient du fait que sinon,
n > Fℓ + Fk > Fk−1 + Fk = Fk+1 ,
ce qui contredit la définition de k. Ainsi, la décomposition obtenue en considérant Fk et les termes d’une
décomposition de n − Fk répond au problème, d’où l’existence.
Par conséquent, P(0) est vraie, et pour tout n dans N∗ , P(0), . . . , P(n − 1) entraînent P(n). D’après le principe
de récurrence forte, P(n) est vraie pour tout n dans N.
7. Application : un jeu d’allumettes.

• Si le nombre initial d’allumettes n’est pas un nombre de Fibonacci, le joueur 1 peut retirer un nombre
d’allumettes égal au plus petit nombre de Fibonacci de la décomposition (il retirera ainsi au moins une
allumette, et pas la totalité)
• Supposons que lors d’une étape, le joueur 1 retire un nombre d’allumettes égal au plus petit nombre de la
décomposition, disons Fi1 , où
n = Fi1 + Fi2 + · · · + Fis .
∗ Si s = 1, alors il ne reste plus d’allumettes, et le joueur 1 a gagné.
∗ Sinon il reste Fi2 + · · · + Fis allumettes. Alors le joueur 2 doit retirer un nombre d’allumettes au plus égal
à 2Fi1 < Fi1 + Fi1 +1 = Fi1 +2 6 Fi2 . Donc il tire strictement moins de Fi2 allumettes. En particulier, il
ne peut pas retirer la totalité des allumettes, donc le joueur 2 ne peut pas gagner à cette étape.
∗ Soit m < Fi2 le nombre d’allumettes que le joueur 2 retire. Il reste donc

Fi2 − m + Fi3 + · · · + Fis .

Pour montrer que la stratégie du joueur 1 est gagnante, il faut montrer que cette situation le ramène à une
situation simimaire à celle de son coup précédent, à savoir qu’il pourra retirer un nombre d’allumettes égal
au plus petit terme de la décomposition de Zeckendorff de Fi2 − m + Fi3 + · · · + Fis . Cette décomposition
étant obtenue de cette expression en décomposant Fi2 − m, il suffit de montrer que le plus petit terme
Ft de la décomposition de Zeckendorff de Fi2 − m est inférieur à 2m. Si ce n’est pas le cas, le plus grand
terme Fs de la décomposition de m vérifie 2Fs 6 2m < Ft . Il en résulte que Fs+1 = Fs−1 + Fs < Ft ,
donc s + 1 < t. En mettant bout-à-bout une décomposition de Zeckendorff de m et une décomposition
de Zeckendorff de Fi2 − m, on obtient une décomposition de Zeckendorff de leur somme Fi2 , constituée
d’au moins deux termes (chaque membre étant non nul). Cela contredit l’unicité de la décomposition de
Fi2 , l’unique décomposition étant celle constituée d’un unique nombre.

7
 • Ainsi, la boucle est bouclée : en tirant initialement le plus petit terme de la décomposition de Zeckendorff,
le joueur 1 est assuré que le joueur 2 ne pourra pas gagner, et que quoi que joue le joueur 2, il pourra à
nouveau tirer, à chaque étape, le plus petit terme de la décomposition de Zeckendorff, ce qui soit le fait
gagner, soit empêche l’adversaire de gagner au tour suivant et l’assure de pouvoir continuer sa stratégie.
Comme on tire à chaque fois au moins une allumette, il y a un vainqueur, et comme cela ne peut être le
joueur 2, c’est le joueur 1. Ainsi, la stratégie est gagnante.
• Si le nombre initial d’allumettes est un nombre de Fibonacci, le joueur 1 ne pouvant pas tirer toutes
les allumettes, est obligé d’en tirer strictement moins. Il se retrouve donc dans la situation du joueur 2
précédemment, qui se voyait obligé de tirer moins d’allumettes que le plus petit terme dans la décomposition
de Fibonacci du nombre d’allumettes restantes. Le raisonnement fait plus haut assure alors que le joueur
2 pourra tirer le plus petit terme de la décomposition de Fibonacci du nombre d’allumettes restantes, puis
poursuivre cette stratégie jusqu’à ce qu’il gagner. Ainsi, maintenant, c’est le joueur 2 qui gagne .
Remarquez que dès que le joueur qui a la stratégie gagnante fait une erreur (ce qui peut tout-à-fait arriver
lorsqu’on calcule de tête le plus petit terme de la décomposition de Zeckendorff...), l’autre joueur peut rattraper
une stratégie gagnante. Tout n’est donc pas perdu : il faut guetter l’erreur de l’autre.

Correction du problème – Lemme de classe monotone

Partie I – Autour des σ-algèbres

1. • On a évidemment P(Ω) ⊂ P(Ω), et de plus, P(Ω) contient Ω, est stable par complémentation et par union
dénombrable, de façon évidente. Ainsi, P(Ω) est une σ-algèbre sur Ω .
• Une σ-algèbre sur Ω contient nécessairement Ω, et par complémentation, aussi ∅. Rciproquement, le sous-
ensemble {∅, Ω} de P(Ω) vérifie trivialement les 3 propriétés requises pour être une σ-algèbre.
Ainsi, {∅, Ω} est la plus petite σ-algèbre sur Ω.
2. (a) Soit A une σ-algèbre.
(i) Ω ∈ A, donc ∅ = Ω ∈ A .
(ii) Soient[
A et B dans A. On définit alors A0 = A, et pour tout n > 1, An = B. Les Ai sont tous dans A,
donc An aussi par stabilité par union dénombrable. Or, cette dernière union n’est autre que A ∪ B.
n∈N
Ainsi, A ∪ B ∈ A.
Remarquez que l’hypothèse porte sur une union dénombrable, et non une union de deux termes seule-
ment. Il faut donc se ramener de façon précise à cette hypothèse. Cette question avait pour but de
justifier correctement que la stabilité par union dénombable entraîne la stabilité par union finie.
(iii) Soient A, B ∈ A. On utilise le résultat précédent, et la stabilité par complémntation, montrant que
A ∪ B est dans A, et en complémentant une nouvelle fois, d’après les lois de De Morgan, A ∩ B ∈ A.
(iv) C’est la même chose, en partant [ de la stabilité par union dénombrable : si les An sont tous dans A,
alors aussi les An , puis aussi An , et en complémentant une nouvelle fois, et en utilisant les lois de
n∈N
\
De morgan, An ∈ A .
n∈N

3. • Soit (Ai )i∈I une famille de σ-algèbres. Les Ai étant des sous-ensembles de P(Ω), il en est de même de leur
intersection. \
• Comme pour tout i ∈ I, Ω ∈ Ai , on a aussi Ω ∈ Ai .
\ i∈I \
• Soit A ∈ Ai . Alors pour tout i ∈ I, A ∈ Ai , et Ai étant une σ-algèbre, A ∈ Ai . Ainsi, A ∈ Ai .
i∈I T i∈I
• Enfin, si (An )n∈N est une suite d’éléments de i∈I Ai , alors pour tout i ∈ I, les An sous tous éléments de
[ [ \
la σ-algèbre Ai , donc aussi leur union An . On en déduit que An ∈ Ai .
n∈N n∈N i∈I
T
Ainsi, i∈I Ai est une σ-algèbre.
T
4. • D’après la question précédente, A∈AC A est une σ-algèbre. T
• De plus, par définition, pour tout A ∈ AC , C ⊂ A, donc C ⊂ A∈AC .

8
 T
• Montrons que est minimal pour cette propriété, autrement dit que pour toute σ-algèbre D telle que
\A∈AC
C ⊂ D, on a ⊂ D. Cela résulte simplement du fait que dans ce cas, D est un des éléments de AC , donc
A∈AC
un des termes de l’intersection.
Ainsi, il existe une plus petite σ-algèbre σ(C) contenant C. Cette σ-algèbre est donnée explicitement par la
formule : \
σ(C) = A.
A∈AC

5. • Soit C = {A}. Une σ-algèbre contenant A contient nécessairement aussi A, ainsi que Ω et ∅. Ainsi,
{∅, A, A, Ω} ⊂ σ(C). Réciproquement, il n’est pas dur de voir que cet ensemble est bien une σ-algèbre.
Ainsi, par minimalité de σ(C), on obtient :

σ(C) = {∅, A, A, Ω} .

Remarquez que cet ensemble peut être réduit à 2 éléments si A = ∅ ou A = Ω.

• Soit C = {Ai , i ∈ I}, où (Ai )i∈I est une partition de Ω, I étant un ensemble fini. Par stabilité par union
(dénombrable ou finie d’après ce qui a été vu plus haut), on peut affirmer que pour tout J ⊂ I,
[
Aj ∈ σ(C).
j∈J
[
Définissons donc D = { Aj , J ∈ P(I)}. On a D ⊂ σ(C). De plus :
j∈J
[
∗ Ω= Ai , et I ∈ P(I), donc Ω ∈ D.
i∈I
∗ Si A ∈ D, il existe J ⊂ I tel que [
A= Aj .
j∈J

On a alors : [
A= Aj ,
j∈J

le complémentaire de J étant pris dans I (ceci résultat du fait que les Ai forment une partition de Ω).
Donc A ∈ D.
∗ Enfin, étant donnée une famille (Bn )n∈N d’éléments de D, il existe une famille (Jn )n∈N de sous-ensembles
de I tels que [
∀n ∈ N, Bn = Aj .
j∈Jn

On a alors : [ [ [ [
= Aj = Aj ∈ D.
S
n∈N n∈N j∈Jn j∈ n∈N Jn

Ainsi, D est une σ-algèbre, et par minimalité de σ(C), σ(C) = D.

Ce raisonnement reste valable si l’ensemble I des indices est dénombrable, mais pas s’il est infini non
dénombrable (car si J n’est pas dénombrable, il n’y a pas de raison que l’union correspondante soit dans
σ(C)). Il faut dans ce cas se restreindre aux sous-ensembles J au plus dénombrables, ce qui impose aussi
de garder les sous-ensembles J au moins codénombrables (de complémentaire au plus dénombrable), pour
avoir la stabilité par complémentation. Vous pouvez montrer en exercice qu’on obtient bien une σ-algèbre
en définissant D de la sorte.
6. Soit B ′ la tribu engendrée par les [a, +∞[.
• Par stabilité par complémentation, pour tout a ∈ R, ]a, +∞[∈ B. Par ailleurs,
\ 1
[a, +∞[= ]a − , +∞[.
∗
n
n∈N

Ainsi, par stabilité d’une σ-algèbre par intersection dénombrable, [a, +∞[∈ B. Ainsi, par minimalité de B ′ ,
on obtient B ′ ⊂ B
• De même, comme [a, +∞[∈ B ′ , on a aussi ] − ∞, a[∈ B ′ , donc
\ 1
] − ∞, a] = ] − ∞, a + [∈ B ′ .
∗
n
n∈N
′
Par minimalité de B, on a donc B ⊂ B .

9
 • Les deux inclusions amènent B = B ′ , donc B est aussi engendrée par les [a, +∞[.

Partie II – Autour des classes monotones

1. Soit A une σ-algèbre. Les points (i) et (iii) de la définition d’une classe monotone sont immédiats pour A.
Vérifions le point (ii). Soient A et B deux éléments de A. Alors A ∈ A, et par stabilité par intersection :

B \ A = B ∩ A ∈ A.

Ainsi, A est bien une classe monotone .

2. Soit M une classe monotone.
(a) On prend A = B = Ω dans (ii), on obtient ∅ = Ω \ Ω ∈ M .

(b) On prend B = Ω dans (ii), on obtient : A ∈ M =⇒ A ∈ M .

(c) On utilise les lois de De Morgan, la stabilité par complémentation, et le point (iii) : si (An )n∈N est[
une suite
décroissante d’éléments de M, alors (An )n∈N est une suite croissante d’éléments de M, donc An est
n∈N
\
dans M, puis par complémentation et loi de De Morgan, An ∈ M.
n∈N

3. Même principe que pour les intersections de tribus, je ne développe pas.

4. Encore le même principe que pour les tribus : on défini MC l’ensemble des classes monotones contenant C. On
pose alors \
M0 = M.
M∈MC

Le question précédente permet d’affirmer que c’est bien une classe monotone ; de façon immédiate C ⊂ M0 car
l’inclusion est vérifiée pour tous les termes de l’intersection ; enfin, toute autre classe monotone contenant C est
un des termes de l’intersection, donc est plus grosse que cette intersection.
Ainsi, M0 est la plus petite classe monotone contenant C . On la note m(C)
5. D’après ce qui précède, σ(C) est une classe monotone, et contient C par définition. Ainsi, par minimalité de
m(C), m(C) ⊂ σ(C).

Partie III – Lemme de classe monotone

1. Soit M une classe monotone stable par intersections finies (donc si A et B sont dans M, A ∩ B aussi)
(a) C’est une récurrence sur n ∈ N∗ . Soit, pour n ∈ N∗ , P(n) la propriété suivante : pour toute famille (Ai )i∈[[1,n]]
n
\ [n
d’éléments de M, Ai et Ai sont dans M.
i=1 i=1
La propriété P(1) est triviale. Nous aurons à utiliser P(2), qui découle de l’hypothèse en ce qui concerne
l’intersection, et qui se ramène au cas de l’intersection par stabilité par complémentation, et par utilisation
des lois de De Morgan, en ce qui concerne l’union.
Soit donc n > 2, et supposons P(n) vraie. Soit (Ai )i∈[[1,n+1]] une famille de n + 1 éléments de M. D’après
l’hypothèse de récurrence P(n), on a :
n
\ n
[
Ai ∈ M et Ai ∈ M.
i=1 i=1

En utilisant P(2) avec chacun de ces 2 ensembles obtenus, et l’ensemble An+1 , il vient donc :
n+1 n n+1 n
! !
\ \ [ [
Ai = Ai ∩ An+1 ∈ M et Ai = Ai ∪ An+1 ∈ M.
i=1 i=1 i=1 i=1

Cela prouve P(n + 1). D’après le principe de récurrence on en déduit que :

M est stable par union et intersection d’un nombre fini de termes.

10
 (b) Le seul point à voir est le point (iii) (stabilité par union dénombrable). Soit (An )n∈N une famille d’éléments
de M. On observe que : [ [
An = Bn ,
n∈N n∈N
n
[
où Bn = Ai . Or, (Bn ) est clairement une suite croissante pour l’inclusion, et d’après la question précé-
i=0
dente,
[ pour tout n [
∈ N, Bn ∈ M. D’après le point (iii) de la définition d’une classe monotone, il vient donc
Bn ∈ M, soit An ∈ M.
n∈N n∈N

Ainsi, M est bien stable par union dénombrable. Il en résulte 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) • Puisque A ∈ m(C), on a Ω ∈ DA
• Soient B et C dans DA , vérifiant C ⊂ B. On a A ∩ B ∈ m(C) et A ∩ C ∈ m(C). Or,

(B \ C) ∩ A = B ∩ C ∩ A = (B ∩ A ∩ C) ∪ (B ∩ A ∩ A)
= B ∩ A ∩ (C ∪ A)
= (B ∩ A) ∩ (C ∩ A) = (B ∩ A) \ (C ∩ A).

• Soit (Bn )n∈N∗ une suite croissante d’éléments de DA . L’égalité de distributivité :

!
[ [
(Bn ∩ A) = Bn ∩ A,
n∈N n∈N

et le fait que si (Bn ) est croissante pour l’inclusion, alors (Bn ∩ A) aussi, permet de montrer, en utilisant
(iii) pour la famille (Bn ∩ A) d’éléments de M, que DA vérifie aussi (iii)
Ainsi, DA est une classe monotone.

(b) Soit C ∈ C. Par hypothèse, pour tout D ∈ C, D ∩C ∈ C ⊂ m(C). Ainsi, D ∈ DC . On en déduit que C ⊂ DC .
Comme par ailleurs, DC est une classe monotone, par minimalité de m(C), il vient m(C) ⊂ DC . Par ailleurs,
par définition, DC est constituée d’éléments de m(C), donc DC ⊂ m(C).
Les deux incusions amènent donc l’égalité DC = m(C).
(c) On en déduit notamment que A ∈ DC , donc que A ∩ C ∈ m(C), donc que C ∈ DA . Ceci étant valable pour
tout C ∈ C, on obtient C ⊂ DA .
On termine comme dans la question précédente pour obtenir alors DA = m(C).
3. L’égalité de la question précédente, valable pour tout A ∈ m(C), montre que m(C) est stable par intersection
finie : étant donnés A et B dans m(C), B ∈ DA , donc A ∩ B ∈ m(C). On utilise la question 1 pour conclure que
m(C) est une σ-algèbre contenant C. Donc, par minimalité de σ(C), σ(C) ⊂ m(C).
L’inclusion réciproque étant déjà aquise (question II-5), on a m(C) = σ(C) .

Partie IV – Caractérisation des mesures bornées

1. Soit (A, B) ∈ A2 , tel que A ⊂ B. On a alors B = A ⊔ (B \ A), donc, en posant A0 = A, A1 = B \ A, et pour

tout n > 2, An = ∅, on a : X
µ(B) = µ(A) + µ(B \ A) + µ(∅).
n>2

Tous les termes de cette somme étant positifs, il vient µ(B) 6 µ(A) .
Il faut bien être conscient qu’en écrivant cela, on peut être amené à manipuler des infinis.
2. Supposons µ bornée, et M une borne associée. Alors par définition, µ(Ω) ∈ [0, M ], donc µ(Ω) < +∞.
Réciproquement, si µ(Ω) < +∞, posons M = µ(Ω). Comme µ est positive, on a bien pour tout A ∈ A,
µ(A) > 0, et par ailleurs, A ⊂ Ω implique µ(A) 6 µ(Ω) = M . Ainsi, µ(A) ∈ [0, M ], et µ est bornée.
Ainsi, µ est bornée si et seulement si µ(Ω) 6= +∞ .

11
 3. La mesure µ étant bornée, en considérant la suite (An )n∈N telle que pour tout n ∈ N, An = ∅, on constate que
la seule valeur possible de µ(∅) est µ(∅) = 0 (dans tout autre cas, la somme serait infinie)
X
Ainsi, en reprenant l’argument de la question 1, la somme µ(∅) étant nulle, il vient :
n>2

µ(A) + µ(B \ A) = µ(B) soit: µ(B \ A) = µ(B) − µ(A) .

4. On considère M = {A ∈ A | µ(A) = ν(A)}.

• L’hypothèse µ(Ω) = ν(Ω) amène Ω ∈ M
• Si A et B sont dans M et vérifient A ⊂ B, on a
µ(B \ A) = µ(B) − µ(A) = ν(B) − ν(A) = ν(B \ A).
• Soit (An )n∈N une suite croissante d’éléments de M. On a alors pour tout n ∈ N, µ(An ) = ν(An ). De plus,
la croissance de la suite implique [ G
An = An \ An−1 ,
n∈N n∈N
en posant par convention A−1 = ∅ (les An \ An−1 sont les anneaux concentriques qu’on obtient lorsqu’on
représente les ensembles An en respectant la contrainte d’inclusion). On peut montrer cette égalité par
double inclusion
S :
∗ Si x ∈ n∈N An , on prend k minimal (existe par propriété fondamentale de N) tel que x ∈ Ak . Alors
x ∈ Ak \ Ak−1 , donc x est dans l’union de droite.
∗ Si x est dans l’union de droite, il est dans un des Ak \ Ak−1 , dons dans Ak , donc dans l’union de gauche.
∗ Par ailleurs, l’union de droite est disjointe, car si k < ℓ, on ne peut pas avoir simultanément x ∈
Aell ‘priveAell−1 et x ∈ Ak \ Ak−1 . En effet, l’inégalité k < ℓ implique k 6 ℓ − 1, donc la seconde
appartenance implique x ∈ Aℓ−1 (par croissance de la suite) ce qui contredit la première appartenance.
On utilise maintenant ce qu’on a démontré dans le point précédent : les An \ An−1 sont dans M, donc, par
σ additivité :
! ! +∞ +∞
[ G X X
µ An = µ An \ An−1 = µ(An \ An−1 ) = ν(An \ An−1 ),
n∈N n∈N n=0 n=0

puis, en refaisant la démarche inverse sur ν :

! !
[ [
µ An =ν An .
n∈N n∈N
[
On a bien obtenu An ∈ M.
n∈N
Ainsi, M est une classe monotone, contenant
On considère µ et ν deux mesures bornées sur A, vérifiant de plus µ(Ω) = ν(Ω) 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 contenant C. Elle
contient en particulier m(C). Comme µ et ν coïncident sur M, elles coïncident aussi sur m(C).
Par ailleurs, C étant un π-système, la partie III permet d’affirmer que m(C) = σ(C).
Ainsi, µ et ν coïncident sur σ(C) .
5. • Si µ = ν, on a évidemment Fµ = Fν .
• Si Fµ = Fν , alors µ et ν coïncident sur tous les intervalles ]− ∞, a], a ∈ R. Comme ces intervalles engendrent
B, pour montrer que µ et ν coïncident sur B, il suffit, en vertu de la question précédente, de justifier que
l’ensemble C des intervalles ] − ∞, a], a ∈ R, est un π-système. Ceci est une évidence puisque si ] − inf ty, a]
et ] − ∞, b] sont deux intervalles de C, on a
] − ∞, a]∩] − ∞, b] =] − ∞, min(a, b)],
qui est encore un intervalle de C.
Ainsi, µ et ν coïncident sur B.
On a montré que µ = nu 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.

12