Une page de Wikiversité, la communauté pédagogique libre.
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
)
{\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 }}{\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}}
.