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 récurrence Formule d'inversion de Pascal/Démonstration par récurrence », n'a pu être restituée correctement ci-dessus.
Redémontrons par récurrence forte sur
n
∈
N
{\displaystyle n\in \mathbb {N} }
le théorème des deux chapitres précédents :
Début d’un théorème
Formule d'inversion de Pascal
Soient
u
0
,
…
,
u
n
,
v
0
,
…
,
v
n
∈
G
{\displaystyle u_{0},\dots ,u_{n},v_{0},\dots ,v_{n}\in G}
où
(
G
,
+
)
{\displaystyle \left(G,+\right)}
est un groupe abélien (par exemple
G
=
R
{\displaystyle G=\mathbb {R} }
), nous avons :
(
∀
k
≤
n
u
k
=
∑
i
=
0
k
(
k
i
)
v
i
)
⇔
(
∀
k
≤
n
v
k
=
∑
i
=
0
k
(
−
1
)
k
−
i
(
k
i
)
u
i
)
{\displaystyle \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
⇒
v
0
=
u
0
{\displaystyle 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 :
(
∀
k
≤
n
+
1
u
k
=
∑
i
=
0
k
(
k
i
)
v
i
)
⇒
(
∀
k
≤
n
+
1
v
k
=
∑
i
=
0
k
(
−
1
)
k
−
i
(
k
i
)
u
i
)
{\displaystyle \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 :
∀
k
≤
n
+
1
u
k
=
∑
i
=
0
k
(
k
i
)
v
i
{\displaystyle \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 :
∀
k
≤
n
v
k
=
∑
i
=
0
k
(
−
1
)
k
−
i
(
k
i
)
u
i
{\displaystyle \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
−
∑
k
=
0
n
(
n
+
1
k
)
v
k
=
u
n
+
1
−
∑
k
=
0
n
(
n
+
1
k
)
∑
i
=
0
k
(
−
1
)
k
−
i
(
k
i
)
u
i
{\displaystyle 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
≤
k
≤
n
+
1
{\displaystyle i\leq k\leq n+1}
,
(
n
+
1
k
)
(
k
i
)
=
(
n
+
1
i
)
(
n
+
1
−
i
k
−
i
)
{\displaystyle {\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
−
∑
i
=
0
n
(
n
+
1
i
)
u
i
∑
j
=
0
n
−
i
(
−
1
)
j
(
n
+
1
−
i
j
)
{\displaystyle 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 :
∑
j
=
0
n
+
1
−
i
(
−
1
)
j
(
n
+
1
−
i
j
)
=
(
1
−
1
)
n
+
1
−
i
=
0
{\displaystyle \sum _{j=0}^{n+1-i}(-1)^{j}{\binom {n+1-i}{j}}=(1-1)^{n+1-i}=0}
donc :
∑
j
=
0
n
−
i
(
−
1
)
j
(
n
+
1
−
i
j
)
=
−
(
−
1
)
n
+
1
−
i
(
n
+
1
−
i
n
+
1
−
i
)
=
(
−
1
)
n
−
i
{\displaystyle \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
−
∑
i
=
0
n
(
n
+
1
i
)
u
i
(
−
1
)
n
−
i
=
∑
i
=
0
n
+
1
(
−
1
)
n
+
1
−
i
(
n
+
1
i
)
u
i
{\displaystyle 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