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é
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_jEn 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_jOn 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_jJetons à 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_nC’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.
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)\rbraceDe 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\rbracePour simplifier, on pose :
F_k = \lbrace\phi\in \mathcal{F}(\llbracket1,n\rrbracket,\llbracket1,p\rrbracket),\;\#\phi(\llbracket1,n\rrbracket)=k\rbracePour 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^nCe qui conclut cet exercice d’application de la formule d’inversion de Pascal !
