Coefficient binomial

Souki · January 2012

Bonsoir,
je voudrai montrer que $\sum_{k=q+1}^{n-p+q+1} C_{n-k}^{p-q-1}C_{k-1}^q = C_n^p$, avec p,q,n des entiers tels que $0 \le q \le p \le n$ pour en déduire que $\sum_{k=0}^n 2^k C_{2n-k}^{n} = 2^{2n}$
Avez vous des indices ..
Merci.

Souki · January 2012

j'ai effectué un changement d'indice, mais bon, ça n'avance pas les choses ...
de même pour la formule de Pascal...

Souki · January 2012

bon, pour déduire la deuxième somme, je procède comme suit :
$2^k=\sum_{q=0}^k C_k^q$ donc $\sum_{k=0}^n2^k C_{2n-k}^n=\sum_{k=0}^n \sum_{q=0}^kC_{2n-k}^nC_k^q = \sum_{q=0}^n \sum_{k=q}^n C_{2n-k}^n C_k^q= \sum_{q=0}^n \sum_{k=q}^{N-p+q} C_{N-q}^{p-q} C_k^q$ en posant $N=2n$ et $n=p-q$,
ça se rapproche de l'égalité qu'il faut établir mais ce n'est pas tout à fait ça, car même si je fait un changement de variable à savoir $\sum_{k=q}^{N-p+q} C_{N-k}^{p-q} C_k^q}=\sum_{k=q+1}^{N-p+q+1} C_{N-k+1}^{p-q} C_{k-1}^q$, je ne peux pas utiliser l'égalité précédente.

jandri · January 2012

Bonjour,

Ce n'est pas un exercice facile.
Je préfère écrire la première égalité sous la forme plus simple: $\displaystyle\sum_{k=0}^n {a+n-k\choose a}{b+k\choose b}={a+b+n+1\choose n}$ avec $\displaystyle{b+k\choose b}=C_{b+k}^b$. Pour retrouver l'égalité proposée par Souki il faut remplacer $a$ par $p-q-1$, $b$ par $q$, $n$ par $n-p$ et $k$ par $k-q-1$.

Elle peut se démontrer en utilisant un produit de Cauchy avec la série entière $(1-x)^{-a-1}=\displaystyle\sum_{k=0}^{+\infty}{a+k\choose a}x^k$.

On en déduit la seconde égalité par $\displaystyle \sum_{k=0}^n 2^k {2n-k\choose n} = \sum_{k=0}^n \sum_{j=0}^k {k\choose j}{2n-k\choose n}= \sum_{j=0}^n \sum_{k=j}^n {j+k-j\choose j}{n+n-k\choose n}=\sum_{j=0}^n {2n+1\choose n-j}=\frac12 2^{2n+1}=2^{2n}$.

Souki · January 2012

je suis d'accord avec vous pour la second égalité, par contre, on a pas encore étudié le produit de Cauchy que vous avez mentionné, ainsi je ne peux pas l'utiliser, je pense que je vais voir du côté du dénombrement.
Cordialement

Cidrolin · January 2012

Bonjour, pour la formule de Jandri $\displaystyle\sum_{k=0}^n {a+n-k\choose a}{b+k\choose b}={a+b+n+1\choose n}$,

il est peut-être possible de compter les chemins de $O(0;0)$ à $E(a+b+1; n)$ : il y en a $ \displaystyle {a+b+n+1\choose n}$.

Un tel chemin coupe la droite $x=b$ en $B(b;k)$

Les chemins de $O$ à $B$ sont au nombre de $ \displaystyle {b+k\choose k}$

Et ceux de $B$ à$E$ . . . . .

Guego · January 2012

Cidrolin a écrit:

Bonjour, pour la formule de Jandri $ \displaystyle\sum_{k=0}^n {a+n-k\choose a}{b+k\choose b}={a+b+n+1\choose n}$...

Ce ne serait pas la formule de Vandermonde, plutôt ?

Cidrolin · January 2012

J'ai déja dit que je ne la connaissais pas

----> http://www.les-mathematiques.net/phorum/read.php?3,667362,669078#msg-669078

jandri · January 2012

Très bien Cidrolin, c'est une belle démonstration combinatoire.
Il faut cependant modifier un tout petit peu ce que tu as écrit.
Un chemin croissant de $ O(0;0)$ à $ E(a+b+1; n)$ peut couper la droite $x=b$ en plusieurs points.
Mais il y a un unique $k$ tel qu'un chemin de $0$ à $E$ contienne le segment qui joint les points $B(b,k)$ et $C(b+1,k)$.
Le nombre des chemins croissants contenant le segment $BC$ est égal à $\displaystyle{b+k\choose b}{a+n-k\choose a}$.

La formule de Vandermonde peut aussi se démontrer avec des chemins croissants.
Un chemin croissant de $ O(0;0)$ à $ E(a+b-n; n)$ coupe la droite $x+y=b$ en un seul point $B(b-k;k)$.
Le nombre de chemins croissants de $ O(0;0)$ à $ E(a+b; n)$ passant par $B(b-k;k)$ est égal à $\displaystyle{b\choose k}{a\choose n-k}$.
On a donc $ \displaystyle\sum_{k=0}^n {a\choose n-k}{b\choose k}={a+b\choose n}$