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