Formule d'inversion de Pascal/Démonstration par récurrence

Début de la boite de navigation du chapitre

Redémontrons par récurrence forte sur $n\in \mathbb {N}$ le théorème des deux chapitres précédents :

fin de la boite de navigation du chapitre

Début d’un théorème

Formule d'inversion de Pascal

Soient $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}$), nous avons :

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

Fin du théorème

Comme au chapitre 1, il suffit de démontrer le sens direct car la réciproque s'en déduit.

Début d'une démonstration

Démonstration

L'implication est vraie pour n = 0 car elle se ramène alors à :

$u_{0}=v_{0}\Rightarrow v_{0}=u_{0}$.

Supposons l'implication vraie jusqu’à n et démontrons qu’elle est vraie jusqu’à n + 1, c’est-à-dire montrons que :

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

Supposons :

$\forall k\leq n+1\quad u_{k}=\sum _{i=0}^{k}{\binom {k}{i}}v_{i}$.

Nous avons alors, par hypothèse de récurrence :

$\forall k\leq n\quad v_{k}=\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}u_{i}$

et

$v_{n+1}=u_{n+1}-\sum _{k=0}^{n}{\binom {n+1}{k}}v_{k}=u_{n+1}-\sum _{k=0}^{n}{\binom {n+1}{k}}\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}u_{i}$.

Or pour $i\leq k\leq n+1$, ${\binom {n+1}{k}}{\binom {k}{i}}={\binom {n+1}{i}}{\binom {n+1-i}{k-i}}$ (Combinatoire/Exercices/Combinaisons#Exercice 4-1) donc

$v_{n+1}=u_{n+1}-\sum _{i=0}^{n}{\binom {n+1}{i}}u_{i}\sum _{j=0}^{n-i}(-1)^{j}{\binom {n+1-i}{j}}$.

La formule du binôme permet d’écrire :

$\sum _{j=0}^{n+1-i}(-1)^{j}{\binom {n+1-i}{j}}=(1-1)^{n+1-i}=0$

donc :

$\sum _{j=0}^{n-i}(-1)^{j}{\binom {n+1-i}{j}}=-(-1)^{n+1-i}{n+1-i \choose n+1-i}=(-1)^{n-i}$.

On a alors :

$v_{n+1}=u_{n+1}-\sum _{i=0}^{n}{\binom {n+1}{i}}u_{i}(-1)^{n-i}=\sum _{i=0}^{n+1}(-1)^{n+1-i}{\binom {n+1}{i}}u_{i}$.

Fin de la démonstration