MPSI 3 Devoir maison 2024 – 2025

DM 2 - Inversion de Pascal, TFD et formule de Faulhaber

Exercices 1 et 2 obligatoires, puis au moins un parmi 3 et 4.

Exercice 1. – Formule d’inversion de Pascal

Soit (e n )n∈N une suite de nombres. Ã !
Xn n
On définit sa transformée binomiale comme la suite ( f n )n∈N , avec f n = ek .
k=0 k

1. Soient 0 ≤ k ≤ n des entiers naturels. Calculer, selon les valeurs de k et de n, la quantité

à !à !
n−k
q n n−q
µ(k, n) =
X
(−1) .
q=0 q k

2. Soit (e n )n∈N une suite de nombres et soit ( f n )n∈N sa transformée binomiale.

Montrer la formule d’inversion de Pascal :
à !
n
n−p n
∀n ∈ N, e n =
X
(−1) fp .
p=0 p

Exercice 2. – Nombre de dérangements

Soit E un ensemble. Une permutation de E est une fonction f : E → E tel que tout élément de E
admet un unique antécédent par f : ∀y ∈ E , ∃!x ∈ E : f (x) = y.
Une permutation de E est un dérangement si elle est sans point fixe : ∀x ∈ E , f (x) ̸= x.
Pour tout n ∈ N∗ , on note D n le nombre de dérangements de l’ensemble ‚1, nƒ. On convient que
D 0 = 1.

1. On admet que ∀n ≥ 1, D n+1 = n(D n + D n−1 ). En déduire que ∀n ≥ 1, D n = nD n−1 + (−1)n .

2. On note (Tn )n∈N la transformée binomiale de (D n )n∈N .

Calculer les valeurs de D n et Tn pour n ∈ ‚0, 5ƒ.

3. Conjecturer une formule pour Tn , puis la démontrer.

4. En déduire une formule pour D n .

5. (Bonus) Si les n passagers d’un avion s’assoient au hasard sur les n sièges, quelle est la
probabilité qu’aucun ne soit à la place indiquée sur son billet ? Pour n = 500, on réalisera
en Python1 une simulation de l’expérience et on comparera au résultat théorique.
1
On pourra utiliser la méthode shuffle du module random.

1
Exercice 3. – Transformation de Fourier discrète (TFD)
2i π
Soit n ≥ 1 un entier. On note ω = e n et E = Cn . Si a est un élément quelconque de E , on note
a 0 , . . . , a n−1 ses n composantes.
Soit a dans E . On définit F a ∈ E sa transformée de Fourier discrète par
n−1
ωk j a k .
X
∀ j ∈ ‚0, n − 1ƒ, (F a) j =
k=0

³ ´ n−1
X −k j
On définit aussi F a ∈ E par ∀ j ∈ ‚0, n − 1ƒ, F a = ω ak .
j
k=0
On pourra librement utiliser l’inégalité triangulaire sur C :
¯Xn ¯ X n
∀z 1 , . . . , z n ∈ C, ¯ zk ¯ ≤ |z k |.
¯ ¯
k=1 k=1

n−1
1. Soit p ∈ Z. Calculer ωkp .
X
k=0
³ ´
2. En déduire que, pour tout a ∈ E , F F a = F (F a) = na.

n−1 n−1
a k X k un polynôme, de coefficients a k ∈ C. Pour tout z ∈ C, on note P (z) = ak z k .
X X
Soit P =
k=0 n o k=0
On note M P = max |P (ωk )|, k ∈ ‚0, n − 1ƒ .

3. Montrer que pour tout k ∈ ‚0, n − 1ƒ, |a k | ≤ M P .

Si a, b ∈ E , le produit de convolution de a et b, noté a ⋆ b, est défini par

n−1
∀k ∈ ‚0, n − 1ƒ, (a ⋆ b)k =
X
a j b k− j ,
j =0

les indices sur b étant à considérer modulo n : ∀i ∈ ‚1 − n, −1ƒ, b −i = b n−i .

4. Montrer que ∀a, b ∈ E , ∀k ∈ ‚0, n − 1ƒ, F (a ⋆ b) k = (F a)k (F b)k .

¡ ¢

5. En déduire – en limitant les calculs – que ⋆ est commutative et associative :

∀a, b, c ∈ E , a ⋆ b = b ⋆ a et (a ⋆ b) ⋆ c = a ⋆ (b ⋆ c).

Exercice 4. – Formule de Faulhaber

La suite (b n )n∈N des nombres de Bernoulli est définie de façon unique par b 0 = 1 et
à !
n n +1
∗
∀n ∈ N ,
X
b k = 0.
k=0 k

n−1
kp.
X
On utilise cette suite afin d’obtenir une expression polynomiale en n de S p (n) =
k=0

2
1. Calculer b n , pour n ≤ 4.
à !
Xn n
2. Montrer que pour tout n ≥ 2, b n−k = 0.
k=1 k
à !
p+1
p +1
3. Montrer que pour tous n, p ∈ N, S p+1 (n + 1) =
X
S j (n).
j =0 j

4. En déduire la relation de récurrence suivante :

p−1
n p+1 S j (n)
∀n, p ∈ N, S p (n) =
X
− p! .
p +1 j =0 j !(p + 1 − j )!

à !
p
p +1
b k n p+1−k .
X
Pour tous entiers naturels n et p, on définit T p (n) =
k=0 k

ℓ
!Ã ! Ã
p X
p +1 ℓ+1 j
5. Montrer que, pour tous n, p ∈ N, T p (n + 1) − T p (n) = = (p + 1)n p .
X
b p−ℓ n
ℓ=0 j =0 p − ℓ j
Pour la deuxième égalité, on pourra réécrire le produit des coefficients binomiaux en un autre
produit de coefficients binomiaux, dont un seul dépend de ℓ.
1
6. En déduire la formule de Faulhaber : ∀n, p ∈ N, S p (n) = T p (n).
p +1
n
k 4 , si n ∈ N ?
X
7. Que vaut
k=1