Sommation/Exercices/Sommation de combinaisons

Exercice 6-1

On rappelle (Exercice 5-1 ou 5-6) :

$\sum _{k=0}^{n}k{\binom {n}{k}}=n2^{n-1}$ ;

$\sum _{k=0}^{n}k(k-1){\binom {n}{k}}=n(n-1)2^{n-2}$ ;

$\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$) de :

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

$\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)+3k(k-1)+k$ donc

$\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}$.

 

Exercice 6-2

Calculer successivement :

$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 : $\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 :

${\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}}$

 

Exercice 6-3

On rappelle la formule de Pascal (chapitre 4) :

${\binom {n}{k}}+{\binom {n}{k+1}}={n+1 \choose k+1}$.

En déduire la formule des colonnes :

$\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, ${\binom {n}{n+1}}=0$) :

$\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 :

$\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).

Exercice 6-4

On rappelle la formule de Vandermonde (chapitre 1 et exercice 5-4) :

$\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) :

${\binom {n}{k}}{\binom {k}{t}}={\binom {n}{t}}{n-t \choose k-t}$.

Calculer :

$\sum _{k}{\binom {k}{t}}{\binom {n}{k}}{\binom {m}{k+s}}$.

Solution

${\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}}$

 

Exercice 6-5

Soit $n\in \mathbb {N}$. En utilisant le nombre complexe $\mathrm {j} =\operatorname {e} ^{2\mathrm {i} \pi /3}$ et en procédant comme dans l'exercice 5-2, calculer :

$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}=\sum _{i}{\binom {n}{i}}=2^{n}$.

Sachant que $\mathrm {j} ^{3}=1$ et même $1+\mathrm {j} +\mathrm {j} ^{2}=0$, on obtient de même :

$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}+\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

${\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 :

${\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\in \{0,1,2\}$ est l'indice auquel $-n$ est congru modulo 3 :

$S_{r}={\frac {2^{n}+2(-1)^{n}}{3}}$ et les deux autres sommes sont égales à ${\frac {2^{n}+(-1)^{n+1}}{3}}=S_{r}-(-1)^{n}$

(ces sommes sont bien entières car $2^{n}+2(-1)^{n}\equiv (-1)^{n}-(-1)^{n}{\bmod {3}}$).

Par exemple pour $n=17$ : $r=1$ (puisque –17 = –6×3 + 1) donc

$\sum _{k=0}^{5}{17 \choose 3k+1}={\frac {2^{17}-2}{3}}=43\,690$ et $\sum _{k=0}^{5}{17 \choose 3k}=\sum _{k=0}^{5}{17 \choose 3k+2}=43\,691$.

 

Exercice 6-6

Soient $n,p\in \mathbb {N}$. Calculer :

$\sum _{k\leq p}(-1)^{k}{\binom {n}{k}}$.

Solution

En utilisant la formule de Pascal, nous obtenons :

${\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\geq n$ alors cette somme est nulle).