Exercice corrigé : Formule d’inversion de Pascal

Découvrez la formule d’inversion de Pascal !
Blaise Pascal

Voici l’énoncé d’un exercice qui va démontrer une inégalité sur la formule d’inversion de Pascal. On va mettre cet exercice dans le chapitre des sommes et du dénombrement, ainsi que des suites ! C’est un exercice faisable en première année dans le supérieur.

En voici l’énoncé :

Enoncé

Formule d'inversion de Pascal

Corrigé

Première démonstration

On dispose de très peu d’informations sur ces suites, on avance donc sans réfléchir. On pose,

\forall n \in \mathbb N,\quad a_n=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}x_i 

Donc,

\forall n\in\mathbb N,\quad a_n = \sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}\left(\sum_{j=0}^{i}\binom{i}{j}y_j\right) = \sum_{i=0}^{n}\sum_{j=0}^{i}(-1)^{n-i}\binom{n}{i}\binom{i}{j}y_j

En utilisant les propriétés d’inversion des sommes doubles (finies)

\forall n\in\mathbb N,\quad a_n = \sum_{j=0}^{n}\sum_{i=j}^{n} (-1)^{n-i}\binom{n}{i}\binom{i}{j}y_j

On réindexe ensuite la seconde somme :

\forall n\in\mathbb N,\quad a_n = \sum_{j=0}^{n}\sum_{i=0}^{n-j} (-1)^{n-i-j}\binom{n}{i+j}\binom{i+j}{j}y_j

Jetons à présent un coup d’œil au produit des coefficients binomiaux : on aimerait faire apparaître la formule du binôme de Newton, il faudrait par exemple réécrire ce produit de manière à obtenir un coefficient indépendant de l’indice ” i “. Essayons,

\binom{n}{i+j}\binom{i+j}{j} = \frac{n!}{(i+j)!(n-i-j)!}\times\frac{(i+j)!}{j!\;i!} =\frac{n!}{(n-i-j)!\,j!\;i!}

On multiplie artificiellement par (n-j)! afin de faire apparaître un coefficient binomial indépendant de ” i “

\binom{n}{i+j}\binom{i+j}{j}=\frac{n!}{j!(n-j)!}\times\frac{(n-j)!}{i!(n-i-j)!}=\binom{n}{j}\binom{n-j}{i}

Ainsi,

\forall n\in\mathbb N,\quad a_n = \sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}y_j\left(\sum_{i=0}^{n-j} (-1)^{i}\binom{n-j}{i}\right)

En appliquant la formule du binôme sur la deuxième somme, on remarque qu’elle est toujours nulle, sauf lorsque j vaut n (où elle vaut 1)

Donc,

\forall n\in\mathbb N,\quad a_n = \sum_{j=0}^{n}(-1)^{n-j}\binom{n}{j}y_j\textbf{1}_{j=n} = y_n

C’est ce qu’on voulait !

Seconde démonstration

Merci à Jean Caspar pour cette proposition !

On peut écrire, pour n fixé, le système correspondant pour k \in \{0, \dots, n\} :

\begin{cases}
\binom{0}{0} x_0 &= y_0 \\
\binom{1}{0}x_0 + \binom{1}{1} x_1 &= y_1 \\
\binom{2}{0} x_0 + \binom{2}{1}x_1 + \binom{2}{2} x_2 &= y_2 \\
\vdots &= \vdots\\
\binom{n}{0} x_0 + \cdots + \binom{n}{n} x_n &= y_n \\
\end{cases} 

Matriciellement, ce système s’écrit :

\begin{pmatrix}
\binom{0}{0} & 0 & \cdots & \cdots & 0 \\
\binom{1}{0} & \binom{1}{1} & 0 & \cdots & 0 \\
\vdots & \vdots & \ddots & \ddots & \vdots \\
\vdots & \vdots & \ddots & \ddots & 0 \\
\binom{n}{0} & \binom{n}{1} & \cdots & \cdots & \binom{n}{n} \\
\end{pmatrix} \begin{pmatrix}
x_0 \\ x_1 \\  \vdots \\ \vdots \\ x_n
\end{pmatrix} = \begin{pmatrix}
y_0 \\ y_1 \\ \vdots \\ \vdots \\ y_n
\end{pmatrix}

On note S la matrice de ce système, X = \begin{pmatrix} x_0 \\ x_1 \\  \vdots \\ \vdots \\ x_n \end{pmatrix} et Y = \begin{pmatrix} y_0 \\ y_1 \\ \vdots \\ \vdots \\ y_n \end{pmatrix}. On a alors SX = Y.

On remarque que {}^tS est la matrice d’une application bien connue : c’est la matrice de l’endomorphisme f : P \mapsto P(X + 1) de R_n[X], écrit dans la base canonique \mathcal{C} = (1, X, X^2, \cdots, X^n). En effet, pour tout k \in \{0, \cdots, n\}, f(X^k) = (X + 1)^k =\displaystyle \sum_{i = 0}^k \binom{k}{i} X^i, par le binôme de Newton. De plus, l’endomorphisme f est en fait un automorphisme, d’inverse g : P \mapsto P(X - 1). On a M_\mathcal{C}(f) = {}^tS et f est un autormorphisme d’inverse g, donc {}^tS est inversible, d’inverse {}^tS^{-1} = M_\mathcal{C}(g). De plus, pour tout k \in \{0, \cdots, n\}, g(X^k) = (X - 1)^k = \displaystyle \sum_{i = 0}^k (-1)^{k - i} \binom{k}{i} X^i, par le même binôme. Donc on a :

S^{-1} = \begin{pmatrix}
(-1)^{0 - 0} \binom{0}{0} & 0 & \cdots & \cdots & 0 \\
(-1)^{1 - 0} \binom{1}{0} & (-1)^{1 - 1}\binom{1}{1} & 0 & \cdots & 0 \\
\vdots & \vdots & \ddots & \ddots & \vdots \\
\vdots & \vdots & \ddots & \ddots & 0 \\
(-1)^{n - 0}\binom{n}{0} & (-1)^{n - 1}\binom{n}{1} & \cdots & \cdots & (-1)^{n - n}\binom{n}{n} \\
\end{pmatrix}

Ainsi, X = S^{-1}Y.
On trouve donc en particulier x_n =\displaystyle \sum_{i = 0}^n  (-1)^{n - i} \binom{n}{i}y_i, ce qui conclut l’exercice !

Exercice d’application

Enoncé

On propose un exercice d’application, pour voir à quoi peut bien servir cette formule.

Formule du nombre de surjections

Corrigé de l’exercice d’application

On notera,

\mathcal{F}(I,J)

L’ensemble des applications de I dans J.

On laissera la question 1 au lecteur

Question 2

On remarque déjà que :

p^n = \#\lbrace\mathcal{F}(\llbracket1,n\rrbracket,\llbracket1,p\rrbracket)\rbrace

De plus,

\mathcal{F}(\llbracket1,n\rrbracket,\llbracket1,p\rrbracket) = \bigsqcup_{k=1}^{p}\lbrace\phi\in \mathcal{F}(\llbracket1,n\rrbracket,\llbracket1,p\rrbracket),\;\#\phi(\llbracket1,n\rrbracket)=k\rbrace

Pour simplifier, on pose :

F_k = \lbrace\phi\in \mathcal{F}(\llbracket1,n\rrbracket,\llbracket1,p\rrbracket),\;\#\phi(\llbracket1,n\rrbracket)=k\rbrace

Pour construire une application de F_{k}, il suffit :

\begin{align*}
&\bullet \text{De choisir k éléments qui constitueront} \;\;\phi(\llbracket1,n\rrbracket)\\
&\hookrightarrow \text{On a} \;\; \binom{p}{k} \;\text{possibilités}\\
&\bullet \text{De relier chacune des k images à des antécédents}\\
&\hookrightarrow \text{On a} \;\; S(n,k) \;\text{possibilités.} \;\; (\phi: \llbracket1,n\rrbracket \rightarrow \phi(\llbracket1,n\rrbracket) \;\;\text{est surjective})
\end{align*}

Finalement,

\forall k \in \llbracket1,p\rrbracket, \;\;\#F_k = \binom{p}{k}S(n,k)

Et puisque l’union est disjointe,

p^n = \sum_{k=1}^{p}\binom{p}{k}S(n,k)=\sum_{k=0}^{p}\binom{p}{k}S(n,k)

Question 3

On utilise maintenant la formule d’inversion de Pascal, en posant :

\forall (n,p)\in\mathbb{N^*}^{2},\;\forall k\in\llbracket1,p\rrbracket, \;\; x_p = p^n \;\; \text{et} \;\; y_k = S(n,k)

On a alors :

S(n,p)=\sum_{k=0}^{p}(-1)^{p-k}\binom{p}{k}k^n

Ce qui conclut cet exercice d’application de la formule d’inversion de Pascal !

Total
0
Shares

Laisser un commentaire

Articles similaires
Des idées de cadeaux pour Noël ? Vous voulez profiter du Black Friday ? Voici nos propositions de livres et objets mathématiques !
Découvrez nos idées