110
CHAPITRE 9 : FONCTIONS G ´
EN ´
ERATRICES
11. — On reprend les notations de l’exercice 8 du chapitre pr´ ec´ edent.
Soit T le plus petit entier tel que X T = a. Calculer t n = P{T > n}
(n ≥ 0). Trouver l’expression de la fonction g´ en´ eratrice H(s) =
n≥0 t n s
n .
En d´ eduire E[T ].
12. — Il est souvent possible de calculer explicitement les termes d’une
suite (u n ) (n ≥ 0) si sa fonction g´ en´ eratrice U (s) =
n≥0
u n s
n a une forme
analytique particuli` ere, par exemple si c’est une fraction rationnelle. Soit
U (s) = P (s)/Q(s) une fraction rationnelle irr´ eductible telle que Q(0) = 0.
On appelle s 1 , . . . , s m les racines (r´ eelles ou complexes) de Q(s) et r 1 , . . . ,
r m leur ordre de multiplicit´ e. On suppose d’abord que le degr´ e de P (s) est
strictement inf´ erieur `
a celui de Q(s). La d´ ecomposition de U (s) en ´ el´ ements
simples a donc la forme :
U (s) =
1≤i≤m
1≤j≤r i
a ij
(s − s i ) j .
a) Montrer que a ir i = r i ! P (s i )/Q
(r i ) (s i ).
b) Montrer que pour |s| < inf
1≤i≤m
|s i | la fonction U (s) se d´ eveloppe en
s´ erie enti` ere
U (s) =
n≥0
u n s
n , avec u n =
1≤i≤m
1≤j≤r i
a ij (−1)
j (j) n
n!
s
−n−j
i
,
o` u l’on a pos´ e (j) n = j(j + 1) . . . (j + n − 1). On obtient ainsi une expression
exacte pour u n .
c) On suppose maintenant qu’il existe une racine et une seule, s 1 , qui
soit strictement plus petite en module que les autres racines, i.e., |s 1 | < |s i |
pour i = 2, . . . , m. Montrer qu’on a alors
u n ∼ a 1r 1 (−1)
r 1
(r 1 ) n
n!
s
−n−r 1
1
,
lorsque n tend vers l’infini.
d) Montrer que le r´ esultat de c) subsiste lorsque le degr´ e de P (s) est
sup´ erieur ou ´ egal ` a celui de Q(s).
13. — On effectue une suite de parties de pile ou face. Soit u n (n ≥ 1) la
probabilit´ e de ne pas avoir trois fois face ` a la suite au cours des n premi` eres
parties.
a) On a ´ evidemment u 1 = u 2 = 1 et l’on pose u 0 = 1. Montrer que pour
n ≥ 3 on a la relation de r´ ecurrence :
u n =
1
2
u n−1 +
1
4
u n−2 +
1
8
u n−3 .
CHAPITRE 9 : FONCTIONS G ´
EN ´
ERATRICES
11. — On reprend les notations de l’exercice 8 du chapitre pr´ ec´ edent.
Soit T le plus petit entier tel que X T = a. Calculer t n = P{T > n}
(n ≥ 0). Trouver l’expression de la fonction g´ en´ eratrice H(s) =
n≥0 t n s
n .
En d´ eduire E[T ].
12. — Il est souvent possible de calculer explicitement les termes d’une
suite (u n ) (n ≥ 0) si sa fonction g´ en´ eratrice U (s) =
n≥0
u n s
n a une forme
analytique particuli` ere, par exemple si c’est une fraction rationnelle. Soit
U (s) = P (s)/Q(s) une fraction rationnelle irr´ eductible telle que Q(0) = 0.
On appelle s 1 , . . . , s m les racines (r´ eelles ou complexes) de Q(s) et r 1 , . . . ,
r m leur ordre de multiplicit´ e. On suppose d’abord que le degr´ e de P (s) est
strictement inf´ erieur `
a celui de Q(s). La d´ ecomposition de U (s) en ´ el´ ements
simples a donc la forme :
U (s) =
1≤i≤m
1≤j≤r i
a ij
(s − s i ) j .
a) Montrer que a ir i = r i ! P (s i )/Q
(r i ) (s i ).
b) Montrer que pour |s| < inf
1≤i≤m
|s i | la fonction U (s) se d´ eveloppe en
s´ erie enti` ere
U (s) =
n≥0
u n s
n , avec u n =
1≤i≤m
1≤j≤r i
a ij (−1)
j (j) n
n!
s
−n−j
i
,
o` u l’on a pos´ e (j) n = j(j + 1) . . . (j + n − 1). On obtient ainsi une expression
exacte pour u n .
c) On suppose maintenant qu’il existe une racine et une seule, s 1 , qui
soit strictement plus petite en module que les autres racines, i.e., |s 1 | < |s i |
pour i = 2, . . . , m. Montrer qu’on a alors
u n ∼ a 1r 1 (−1)
r 1
(r 1 ) n
n!
s
−n−r 1
1
,
lorsque n tend vers l’infini.
d) Montrer que le r´ esultat de c) subsiste lorsque le degr´ e de P (s) est
sup´ erieur ou ´ egal ` a celui de Q(s).
13. — On effectue une suite de parties de pile ou face. Soit u n (n ≥ 1) la
probabilit´ e de ne pas avoir trois fois face ` a la suite au cours des n premi` eres
parties.
a) On a ´ evidemment u 1 = u 2 = 1 et l’on pose u 0 = 1. Montrer que pour
n ≥ 3 on a la relation de r´ ecurrence :
u n =
1
2
u n−1 +
1
4
u n−2 +
1
8
u n−3 .