Formule d'inversion de Pascal/Démonstration polynomiale

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Nous avons démontré par diverses méthodes, dans les trois premiers chapitres :

Début d’un théorème

Formule d'inversion de Pascal

Pour tous $u_{0},\dots ,u_{N},v_{0},\dots ,v_{N}\in G$ où $\left(G,+\right)$ est un groupe abélien (par exemple $G=\mathbb {R}$) :

$\left(\forall n\leq N\quad u_{n}=\sum _{k=0}^{n}{\binom {n}{k}}v_{k}\right)\Leftrightarrow \left(\forall n\leq N\quad v_{n}=\sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}u_{k}\right)$.

Fin du théorème

Redémontrons ce théorème par une technique bien plus efficace : celle des fonctions génératrices (qui sont en général des séries formelles mais seront ici des polynômes on ne peut plus simples).

Début d'une démonstration

Démonstration

Il s'agit de montrer (pour $n$ fixé) que

1. $\forall v_{0},\dots ,v_{n}\in G\quad \sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}\left(\sum _{j=0}^{k}{\binom {k}{j}}v_{j}\right)=v_{n}$ ;
2. $\forall u_{0},\dots ,u_{n}\in G\quad \sum _{k=0}^{n}{\binom {n}{k}}\left(\sum _{j=0}^{k}(-1)^{k-j}{\binom {k}{j}}u_{j}\right)=u_{n}$.

Démontrons le point 1 (le point 2 se démontre de la même façon, ou se déduit du point 1 comme au chapitre 1).

Par interversion de l'ordre de sommation, on a

$\sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}\left(\sum _{j=0}^{k}{\binom {k}{j}}v_{j}\right)=\sum _{j=0}^{n}d_{n,j}v_{j}$

avec (pour $0\leq j\leq n$)

$d_{n,j}=\sum _{k=j}^{n}(-1)^{n-k}{\binom {n}{k}}{\binom {k}{j}}$.

Il s'agit donc simplement de vérifier que $d_{n,n}=1$ et $\forall j<n\quad d_{n,j}=0$.

Or (par construction même)

$\sum _{j=0}^{n}d_{n,j}X^{j}=\sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}\left(\sum _{j=0}^{k}{\binom {k}{j}}X^{j}\right)$

donc (d'après la formule du binôme)

$\sum _{j=0}^{n}d_{n,j}X^{j}=\sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}\left(1+X\right)^{k}=\left(\left(1+X\right)-1\right)^{n}=X^{n}$,

ce qui (par identification des coefficients) prouve le résultat.

Fin de la démonstration