Une page de Wikiversité.
Début de la boite de navigation du chapitre
fin de la boite de navigation du chapitre
En raison de limitations techniques, la typographie souhaitable du titre, «
Formule d'inversion de Pascal : Démonstration par techniques sommatoires Formule d'inversion de Pascal/Démonstration par techniques sommatoires », n'a pu être restituée correctement ci-dessus.
Début d’un théorème
Formule d'inversion de Pascal
Soient (un )n ∈ℕ et (vn )n ∈ℕ deux suites à valeurs dans un groupe abélien
(
G
,
+
)
{\displaystyle \left(G,+\right)}
(par exemple
G
=
R
{\displaystyle G=\mathbb {R} }
), nous avons :
(
∀
n
∈
N
u
n
=
∑
k
=
0
n
(
n
k
)
v
k
)
⇔
(
∀
n
∈
N
v
n
=
∑
k
=
0
n
(
−
1
)
n
−
k
(
n
k
)
u
k
)
{\displaystyle \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 :
∀
u
0
,
…
,
u
N
,
v
0
,
…
,
v
N
∈
G
{\displaystyle \forall u_{0},\dots ,u_{N},v_{0},\dots ,v_{N}\in G}
(
∀
n
≤
N
u
n
=
∑
k
=
0
n
(
n
k
)
v
k
)
⇔
(
∀
n
≤
N
v
n
=
∑
k
=
0
n
(
−
1
)
n
−
k
(
n
k
)
u
k
)
{\displaystyle \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 :
∀
i
∈
{
0
,
1
,
…
,
n
}
∑
k
=
i
n
(
−
1
)
n
−
k
(
n
k
)
(
k
i
)
=
(
n
i
)
0
n
−
i
{\displaystyle \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
≤
k
≤
n
{\displaystyle i\leq k\leq n}
,
(
n
k
)
(
k
i
)
=
(
n
i
)
(
n
−
i
n
−
k
)
{\displaystyle {\binom {n}{k}}{\binom {k}{i}}={\binom {n}{i}}{n-i \choose n-k}}
(Combinatoire/Exercices/Combinaisons#Exercice 4-1 ) donc
∑
k
=
i
n
(
−
1
)
n
−
k
(
n
k
)
(
k
i
)
=
(
n
i
)
∑
k
=
i
n
(
−
1
)
n
−
k
(
n
−
i
n
−
k
)
=
(
n
i
)
(
1
−
1
)
n
−
i
(Formule du binôme)
=
(
n
i
)
0
n
−
i
.
{\displaystyle {\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
{\displaystyle x^{n-i}}
dans le développement en série de
exp
(
−
x
)
exp
(
x
)
=
1
{\displaystyle \exp(-x)\exp(x)=1}
.
Démontrons maintenant le sens direct (
⇒
{\displaystyle \Rightarrow }
) de l'équivalence. Supposons donc que :
∀
n
≤
N
u
n
=
∑
k
=
0
n
(
n
k
)
v
k
{\displaystyle \forall n\leq N\quad u_{n}=\sum _{k=0}^{n}{n \choose k}v_{k}}
.
Alors :
∀
n
≤
N
∑
k
=
0
n
(
−
1
)
n
−
k
(
n
k
)
u
k
=
∑
k
=
0
n
(
−
1
)
n
−
k
(
n
k
)
∑
i
=
0
k
(
k
i
)
v
i
=
∑
i
=
0
n
v
i
∑
k
=
i
n
(
−
1
)
n
−
k
(
n
k
)
(
k
i
)
(Inversion de somme)
=
∑
i
=
0
n
v
i
(
n
i
)
0
n
−
i
(Lemme)
=
v
n
(
n
n
)
0
n
−
n
=
v
n
(Car
0
0
=
1
)
{\displaystyle {\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 (
⇐
{\displaystyle \Leftarrow }
), supposons que :
∀
n
≤
N
v
n
=
∑
k
=
0
n
(
−
1
)
n
−
k
(
n
k
)
u
k
{\displaystyle \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
≤
N
{\displaystyle n\leq N}
)
u
n
′
=
(
−
1
)
n
v
n
{\displaystyle u'_{n}=(-1)^{n}v_{n}}
et
v
n
′
=
(
−
1
)
n
u
n
{\displaystyle v'_{n}=(-1)^{n}u_{n}}
:
∀
n
≤
N
u
n
′
=
∑
k
=
0
n
(
n
k
)
v
k
′
{\displaystyle \forall n\leq N\quad u'_{n}=\sum _{k=0}^{n}{n \choose k}v'_{k}}
.
Alors, d'après le sens direct :
∀
n
≤
N
∑
k
=
0
n
(
n
k
)
v
k
=
∑
k
=
0
n
(
n
k
)
(
−
1
)
k
u
k
′
=
(
−
1
)
n
v
n
′
=
u
n
{\displaystyle \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}}
.