Une page de Wikiversité, la communauté pédagogique libre.
En raison de limitations techniques, la typographie souhaitable du titre, «
Exercice : Sommation de combinaisonsSommation/Exercices/Sommation de combinaisons », n'a pu être restituée correctement ci-dessus.
On rappelle (Exercice 5-1 ou 5-6) :
∑
k
=
0
n
k
(
n
k
)
=
n
2
n
−
1
{\displaystyle \sum _{k=0}^{n}k{\binom {n}{k}}=n2^{n-1}}
;
∑
k
=
0
n
k
(
k
−
1
)
(
n
k
)
=
n
(
n
−
1
)
2
n
−
2
{\displaystyle \sum _{k=0}^{n}k(k-1){\binom {n}{k}}=n(n-1)2^{n-2}}
;
∑
k
=
0
n
k
(
k
−
1
)
(
k
−
2
)
(
n
k
)
=
n
(
n
−
1
)
(
n
−
2
)
2
n
−
3
{\displaystyle \sum _{k=0}^{n}k(k-1)(k-2){\binom {n}{k}}=n(n-1)(n-2)2^{n-3}}
.
En déduire l'expression (en fonction de
n
{\displaystyle n}
) de :
a
)
∑
k
=
0
n
k
2
(
n
k
)
b
)
∑
k
=
0
n
k
3
(
n
k
)
{\displaystyle a)\,\sum _{k=0}^{n}k^{2}{\binom {n}{k}}\qquad \qquad b)\,\sum _{k=0}^{n}k^{3}{\binom {n}{k}}}
.
Solution
a)
k
2
=
k
(
k
−
1
)
+
k
{\displaystyle k^{2}=k(k-1)+k}
donc
∑
k
=
0
n
k
2
(
n
k
)
=
n
(
n
−
1
)
2
n
−
2
+
n
2
n
−
1
=
n
(
n
+
1
)
2
n
−
2
{\displaystyle \sum _{k=0}^{n}k^{2}{\binom {n}{k}}=n(n-1)2^{n-2}+n2^{n-1}=n(n+1)2^{n-2}}
.
b)
k
3
=
k
(
k
−
1
)
(
k
−
2
)
+
3
k
(
k
−
1
)
+
k
{\displaystyle k^{3}=k(k-1)(k-2)+3k(k-1)+k}
donc
∑
k
=
0
n
k
3
(
n
k
)
=
n
(
n
−
1
)
(
n
−
2
)
2
n
−
3
+
3
n
(
n
−
1
)
2
n
−
2
+
n
2
n
−
1
=
n
2
(
n
+
3
)
2
n
−
3
{\displaystyle \sum _{k=0}^{n}k^{3}{\binom {n}{k}}=n(n-1)(n-2)2^{n-3}+3n(n-1)2^{n-2}+n2^{n-1}=n^{2}(n+3)2^{n-3}}
.
Calculer successivement :
a
)
∑
k
=
0
n
1
k
+
1
(
n
k
)
b
)
∑
k
=
0
n
1
k
+
2
(
n
k
)
{\displaystyle a)\,\sum _{k=0}^{n}{\frac {1}{k+1}}{\binom {n}{k}}\qquad \qquad b)\,\sum _{k=0}^{n}{\frac {1}{k+2}}{\binom {n}{k}}}
.
Solution
a) Voir Combinatoire/Exercices/Combinaisons#Exercice 4-2 :
∑
k
=
0
n
1
k
+
1
(
n
k
)
=
2
n
+
1
−
1
n
+
1
{\displaystyle \sum _{k=0}^{n}{\frac {1}{k+1}}{\binom {n}{k}}={\frac {2^{n+1}-1}{n+1}}}
.
b) On en déduit, après application de la formule de Pascal :
∑
k
=
0
n
1
k
+
2
(
n
k
)
=
∑
k
=
0
n
1
k
+
2
(
n
+
1
k
+
1
)
−
∑
k
=
0
n
−
1
1
k
+
2
(
n
k
+
1
)
=
∑
j
=
1
n
+
1
1
j
+
1
(
n
+
1
j
)
−
∑
j
=
1
n
1
j
+
1
(
n
j
)
=
∑
j
=
0
n
+
1
1
j
+
1
(
n
+
1
j
)
−
∑
j
=
0
n
1
j
+
1
(
n
j
)
=
2
n
+
2
−
1
n
+
2
−
2
n
+
1
−
1
n
+
1
=
n
2
n
+
1
+
1
(
n
+
1
)
(
n
+
2
)
.
{\displaystyle {\begin{aligned}\sum _{k=0}^{n}{\frac {1}{k+2}}{\binom {n}{k}}&=\sum _{k=0}^{n}{\frac {1}{k+2}}{n+1 \choose k+1}-\sum _{k=0}^{n-1}{\frac {1}{k+2}}{n \choose k+1}\\&=\sum _{j=1}^{n+1}{\frac {1}{j+1}}{\binom {n+1}{j}}-\sum _{j=1}^{n}{\frac {1}{j+1}}{\binom {n}{j}}\\&=\sum _{j=0}^{n+1}{\frac {1}{j+1}}{\binom {n+1}{j}}-\sum _{j=0}^{n}{\frac {1}{j+1}}{\binom {n}{j}}\\&={\frac {2^{n+2}-1}{n+2}}-{\frac {2^{n+1}-1}{n+1}}\\&={\frac {n2^{n+1}+1}{(n+1)(n+2)}}.\end{aligned}}}
On rappelle la formule de Pascal (chapitre 4) :
(
n
k
)
+
(
n
k
+
1
)
=
(
n
+
1
k
+
1
)
{\displaystyle {\binom {n}{k}}+{\binom {n}{k+1}}={n+1 \choose k+1}}
.
En déduire la formule des colonnes :
∀
m
≥
n
≥
0
∑
k
=
n
m
(
k
n
)
=
(
m
+
1
n
+
1
)
{\displaystyle \forall m\geq n\geq 0\quad \sum _{k=n}^{m}{\binom {k}{n}}={\binom {m+1}{n+1}}}
.
Solution
D'après la formule de Pascal (et avec, par convention,
(
n
n
+
1
)
=
0
{\displaystyle {\binom {n}{n+1}}=0}
) :
∑
k
=
n
m
(
k
n
)
=
∑
k
=
n
m
(
(
k
+
1
n
+
1
)
−
(
k
n
+
1
)
)
{\displaystyle \sum _{k=n}^{m}{\binom {k}{n}}=\sum _{k=n}^{m}\left({k+1 \choose n+1}-{\binom {k}{n+1}}\right)}
.
Par télescopage, il reste :
∑
k
=
n
m
(
k
n
)
=
(
m
+
1
n
+
1
)
−
0
=
(
m
+
1
n
+
1
)
{\displaystyle \sum _{k=n}^{m}{\binom {k}{n}}={m+1 \choose n+1}-0={m+1 \choose n+1}}
.
Pour d'autres méthodes, voir Combinatoire/Exercices/Combinaisons#Exercice 4-1 , question d).
On rappelle la formule de Vandermonde (chapitre 1 et exercice 5-4) :
∑
j
(
n
j
)
(
m
r
−
j
)
=
(
m
+
n
r
)
{\displaystyle \sum _{j}{\binom {n}{j}}{\binom {m}{r-j}}={\binom {m+n}{r}}}
ainsi que la formule (élémentaire : Combinatoire/Exercices/Combinaisons#Exercice 4-1 , c) :
(
n
k
)
(
k
t
)
=
(
n
t
)
(
n
−
t
k
−
t
)
{\displaystyle {\binom {n}{k}}{\binom {k}{t}}={\binom {n}{t}}{n-t \choose k-t}}
.
Calculer :
∑
k
(
k
t
)
(
n
k
)
(
m
k
+
s
)
{\displaystyle \sum _{k}{\binom {k}{t}}{\binom {n}{k}}{\binom {m}{k+s}}}
.
Solution
∑
k
(
k
t
)
(
n
k
)
(
m
k
+
s
)
=
(
n
t
)
∑
k
(
n
−
t
k
−
t
)
(
m
m
−
s
−
k
)
=
(
n
t
)
∑
j
(
n
−
t
j
)
(
m
m
−
s
−
t
−
j
)
=
(
n
t
)
(
m
+
n
−
t
m
−
s
−
t
)
=
(
n
t
)
(
m
+
n
−
t
n
+
s
)
.
{\displaystyle {\begin{aligned}\sum _{k}{\binom {k}{t}}{\binom {n}{k}}{\binom {m}{k+s}}&={\binom {n}{t}}\sum _{k}{n-t \choose k-t}{\binom {m}{m-s-k}}\\&={\binom {n}{t}}\sum _{j}{\binom {n-t}{j}}{\binom {m}{m-s-t-j}}\\&={\binom {n}{t}}{m+n-t \choose m-s-t}\\&={\binom {n}{t}}{m+n-t \choose n+s}.\end{aligned}}}
Soit
n
∈
N
{\displaystyle n\in \mathbb {N} }
. En utilisant le nombre complexe
j
=
e
2
i
π
/
3
{\displaystyle \mathrm {j} =\operatorname {e} ^{2\mathrm {i} \pi /3}}
et en procédant comme dans l'exercice 5-2, calculer :
S
0
:=
∑
k
(
n
3
k
)
,
S
1
:=
∑
k
(
n
3
k
+
1
)
,
S
2
:=
∑
k
(
n
3
k
+
2
)
{\displaystyle S_{0}:=\sum _{k}{\binom {n}{3k}},\quad S_{1}:=\sum _{k}{\binom {n}{3k+1}},\quad S_{2}:=\sum _{k}{\binom {n}{3k+2}}}
.
Solution
S
0
+
S
1
+
S
2
=
∑
i
(
n
i
)
=
2
n
{\displaystyle S_{0}+S_{1}+S_{2}=\sum _{i}{\binom {n}{i}}=2^{n}}
.
Sachant que
j
3
=
1
{\displaystyle \mathrm {j} ^{3}=1}
et même
1
+
j
+
j
2
=
0
{\displaystyle 1+\mathrm {j} +\mathrm {j} ^{2}=0}
, on obtient de même :
S
0
+
j
S
1
+
j
2
S
2
=
∑
i
(
n
i
)
j
i
=
(
1
+
j
)
n
=
(
−
j
2
)
n
=
(
−
j
)
−
n
{\displaystyle S_{0}+\mathrm {j} S_{1}+\mathrm {j} ^{2}S_{2}=\sum _{i}{\binom {n}{i}}\mathrm {j} ^{i}=(1+\mathrm {j} )^{n}=(-\mathrm {j} ^{2})^{n}=(-\mathrm {j} )^{-n}}
;
S
0
+
j
2
S
1
+
j
S
2
=
∑
i
(
n
i
)
j
2
i
=
(
1
+
j
2
)
n
=
(
−
j
)
n
{\displaystyle S_{0}+\mathrm {j} ^{2}S_{1}+\mathrm {j} S_{2}=\sum _{i}{\binom {n}{i}}\mathrm {j} ^{2i}=(1+\mathrm {j} ^{2})^{n}=(-\mathrm {j} )^{n}}
.
En résolvant le système
{
S
0
+
S
1
+
S
2
=
2
n
S
0
+
j
S
1
+
j
2
S
2
=
(
−
j
)
−
n
S
0
+
j
2
S
1
+
j
S
2
=
(
−
j
)
n
,
{\displaystyle {\begin{cases}S_{0}+S_{1}+S_{2}&=2^{n}\\S_{0}+\mathrm {j} S_{1}+\mathrm {j} ^{2}S_{2}&=(-\mathrm {j} )^{-n}\\S_{0}+\mathrm {j} ^{2}S_{1}+\mathrm {j} S_{2}&=(-\mathrm {j} )^{n},\end{cases}}}
on en déduit :
{
S
0
=
2
n
+
(
−
1
)
n
(
j
−
n
+
j
n
)
3
S
1
=
2
n
+
(
−
1
)
n
(
j
−
n
−
1
+
j
n
+
1
)
3
S
2
=
2
n
+
(
−
1
)
n
(
j
−
n
−
2
+
j
n
+
2
)
3
,
{\displaystyle {\begin{cases}S_{0}&={\frac {2^{n}+(-1)^{n}\left(\mathrm {j} ^{-n}+\mathrm {j} ^{n}\right)}{3}}\\S_{1}&={\frac {2^{n}+(-1)^{n}\left(\mathrm {j} ^{-n-1}+\mathrm {j} ^{n+1}\right)}{3}}\\S_{2}&={\frac {2^{n}+(-1)^{n}\left(\mathrm {j} ^{-n-2}+\mathrm {j} ^{n+2}\right)}{3}},\end{cases}}}
soit, si
r
∈
{
0
,
1
,
2
}
{\displaystyle r\in \{0,1,2\}}
est l'indice auquel
−
n
{\displaystyle -n}
est congru modulo 3 :
S
r
=
2
n
+
2
(
−
1
)
n
3
{\displaystyle S_{r}={\frac {2^{n}+2(-1)^{n}}{3}}}
et les deux autres sommes sont égales à
2
n
+
(
−
1
)
n
+
1
3
=
S
r
−
(
−
1
)
n
{\displaystyle {\frac {2^{n}+(-1)^{n+1}}{3}}=S_{r}-(-1)^{n}}
(ces sommes sont bien entières car
2
n
+
2
(
−
1
)
n
≡
(
−
1
)
n
−
(
−
1
)
n
mod
3
{\displaystyle 2^{n}+2(-1)^{n}\equiv (-1)^{n}-(-1)^{n}{\bmod {3}}}
).
Par exemple pour
n
=
17
{\displaystyle n=17}
:
r
=
1
{\displaystyle r=1}
(puisque –17 = –6×3 + 1) donc
∑
k
=
0
5
(
17
3
k
+
1
)
=
2
17
−
2
3
=
43
690
{\displaystyle \sum _{k=0}^{5}{17 \choose 3k+1}={\frac {2^{17}-2}{3}}=43\,690}
et
∑
k
=
0
5
(
17
3
k
)
=
∑
k
=
0
5
(
17
3
k
+
2
)
=
43
691
{\displaystyle \sum _{k=0}^{5}{17 \choose 3k}=\sum _{k=0}^{5}{17 \choose 3k+2}=43\,691}
.
Soient
n
,
p
∈
N
{\displaystyle n,p\in \mathbb {N} }
. Calculer :
∑
k
≤
p
(
−
1
)
k
(
n
k
)
{\displaystyle \sum _{k\leq p}(-1)^{k}{\binom {n}{k}}}
.
Solution
En utilisant la formule de Pascal, nous obtenons :
∑
k
≤
p
(
−
1
)
k
(
n
k
)
=
∑
k
≤
p
(
−
1
)
k
[
(
n
−
1
k
−
1
)
+
(
n
−
1
k
)
]
=
∑
j
≤
p
−
1
(
−
1
)
j
+
1
(
n
−
1
j
)
+
∑
k
≤
p
(
−
1
)
k
(
n
−
1
k
)
=
(
−
1
)
p
(
n
−
1
p
)
{\displaystyle {\begin{aligned}\sum _{k\leq p}(-1)^{k}{\binom {n}{k}}&=\sum _{k\leq p}(-1)^{k}\left[{n-1 \choose k-1}+{\binom {n-1}{k}}\right]\\&=\sum _{j\leq p-1}(-1)^{j+1}{\binom {n-1}{j}}+\sum _{k\leq p}(-1)^{k}{\binom {n-1}{k}}\\&=(-1)^{p}{\binom {n-1}{p}}\end{aligned}}}
(en particulier — cf. exercice 5-2 — si
p
≥
n
{\displaystyle p\geq n}
alors cette somme est nulle).