Formule d'inversion de Pascal/Démonstration par techniques sommatoires

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Début d’un théorème

Formule d'inversion de Pascal

Soient (u_n)_n∈ℕ et (v_n)_n∈ℕ deux suites à valeurs dans un groupe abélien $\left(G,+\right)$ (par exemple $G=\mathbb {R}$), nous avons :

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

Plus précisément : $\forall u_{0},\dots ,u_{N},v_{0},\dots ,v_{N}\in G$

$\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

Démonstration par techniques sommatoires On montre d'abord le lemme : $\forall i\in \{0,1,\dots ,n\}\quad \sum _{k=i}^{n}(-1)^{n-k}{n \choose k}{k \choose i}={n \choose i}0^{n-i}$. Démonstration Pour $i\leq k\leq n$, ${\binom {n}{k}}{\binom {k}{i}}={\binom {n}{i}}{n-i \choose n-k}$ (Combinatoire/Exercices/Combinaisons#Exercice 4-1) donc ${\begin{aligned}\sum _{k=i}^{n}(-1)^{n-k}{n \choose k}{k \choose i}&={\binom {n}{i}}\sum _{k=i}^{n}(-1)^{n-k}{n-i \choose n-k}\\&={\binom {n}{i}}(1-1)^{n-i}\qquad \qquad \qquad \qquad \qquad {\text{(Formule du binôme)}}\\&={\binom {n}{i}}0^{n-i}.\end{aligned}}$ Remarque : une autre façon de démontrer ce lemme est de remarquer que la somme à calculer est le coefficient de $x^{n-i}$ dans le développement en série de $\exp(-x)\exp(x)=1$.   Démontrons maintenant le sens direct ($\Rightarrow$) de l'équivalence. Supposons donc que : $\forall n\leq N\quad u_{n}=\sum _{k=0}^{n}{n \choose k}v_{k}$. Alors : ${\begin{aligned}\forall n\leq N\quad \sum _{k=0}^{n}(-1)^{n-k}{n \choose k}u_{k}&=\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}\sum _{i=0}^{k}{k \choose i}v_{i}\\&=\sum _{i=0}^{n}v_{i}\sum _{k=i}^{n}(-1)^{n-k}{n \choose k}{k \choose i}\qquad \qquad \qquad {\text{(Inversion de somme)}}\\&=\sum _{i=0}^{n}v_{i}{n \choose i}0^{n-i}\qquad \qquad \qquad \qquad \qquad \qquad {\text{(Lemme)}}\\&={v_{n}}{n \choose n}0^{n-n}\\&=v_{n}\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad {\text{(Car }}\textstyle {0^{0}=1}{\text{)}}\end{aligned}}$ Réciproquement ($\Leftarrow$), supposons que : $\forall n\leq N\quad v_{n}=\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}u_{k}$ c'est-à-dire, en posant (pour tout $n\leq N$) $u'_{n}=(-1)^{n}v_{n}$ et $v'_{n}=(-1)^{n}u_{n}$ : $\forall n\leq N\quad u'_{n}=\sum _{k=0}^{n}{n \choose k}v'_{k}$. Alors, d'après le sens direct : $\forall n\leq N\quad \sum _{k=0}^{n}{n \choose k}v_{k}=\sum _{k=0}^{n}{n \choose k}(-1)^{k}u'_{k}=(-1)^{n}v'_{n}=u_{n}$.