Une belle somme binomiale
Hello,
Je viens de "découvrir" une belle formule (grâce à un exo très classique de proba) :
$$
\sum_{k=0}^n \binom{2k}{k}\binom{2n-2k}{n-k}
\ = \
4^n
$$
L'avez-vous déjà démontrée de manière élémentaire (par exemple pour vos élèves débutant avec le symbole $\sum$ et les coefficients binomiaux) ?
Il y a une belle démo dans Graham-Knuth-Patashnik, page 187, mais elle nécessite d'étendre le coeff binomial et d'utiliser Vandermonde (je trouve cette preuve très belle, mais je voulais savoir si on pouvait en présenter une plus "simple" à des élèves sans être obligé d'étendre le coeff binomial).
Voilà, c'est tout.
Intervient qui veut !
Je viens de "découvrir" une belle formule (grâce à un exo très classique de proba) :
$$
\sum_{k=0}^n \binom{2k}{k}\binom{2n-2k}{n-k}
\ = \
4^n
$$
L'avez-vous déjà démontrée de manière élémentaire (par exemple pour vos élèves débutant avec le symbole $\sum$ et les coefficients binomiaux) ?
Il y a une belle démo dans Graham-Knuth-Patashnik, page 187, mais elle nécessite d'étendre le coeff binomial et d'utiliser Vandermonde (je trouve cette preuve très belle, mais je voulais savoir si on pouvait en présenter une plus "simple" à des élèves sans être obligé d'étendre le coeff binomial).
Voilà, c'est tout.
Intervient qui veut !
Réponses
-
Je ne sais pas, mais, si $X$ est un ensemble à $n$ éléments, et $A,B \subset X$ à $k$ éléments :
$4^n$ est le nombre de parties de $X \sqcup X$
$\binom{2k}{k}$ est le nombre de parties en bijection avec $A$ dans $A \sqcup B$
$\binom{2n-2k}{n-k}$ est le nombre de parties en bijection avec $\overline A$ dans $\overline A \sqcup \overline B$
Peut-on décrire de façon biunivoque une partie $M\sqcup N$ de $X\sqcup X$ par quelque chose qui donnerait d'une manière ou d'une autre :
- pour chaque (??) couple d'ensembles $A,B \subset X$ de même cardinal $k$,
- une partie $R \subset A \sqcup B$, de cardinal $\sharp A=\sharp B$
- une partie $S \subset \overline A \sqcup \overline B$, de cardinal $\sharp\overline{A} = \sharp \overline{B}$
? -
Trouvons une évidence plus générale ?!?
S -
Par exemple, pour $n=1$, la formule donne : $2 + 2 = 4$
J'ai envie, pour $X\sqcup X = \{a_1,a_2\}$ de grouper les 4 parties comme suit :
$\emptyset , \{a_1,a_2\}$ ensemble
$\{a_1\},\{a_2\}$ ensemble
Pour $n=2$, la formule donne : $6 + 4 + 6 = 16$. J'écris $X = \{a,b\}$.
Je pense que le $4$ correspond aux parties suivantes de $X\sqcup X = \{a_1,b_1,a_2,b_2\}$ :
$\{a_1,b_1\},
\{a_1,b_2\},
\{b_1,a_2\},
\{a_2,b_2\}$. -
Le cas $k$
preuve par : je dois y aller
S -
Un autre truc, si on regarde l'asymptotique : ce sont les bords $k=0$, $k=n$ qui mangent la plus grosse partie de la masse, mais dans le plus grand des calmes !
On a $\displaystyle \binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi}n},\ $ alors que la somme contient $n+1$ termes.
Le terme du milieu, pour $k=\dfrac{n}{2}$ donne : $\displaystyle \binom{n}{\frac{n}{2}}^2 \sim \frac{4^n}{\pi \cdot n^2}$. -
Je pense, si je ne m'abuse, qu'une solution avec séries génératrices consisterait à écrire bêtement :
$$
\frac{1}{1-4x}=\left(\frac{1}{\sqrt{1-4x}}\right)^2
$$
Mais ça ne répond pas à la question de Clairon. -
Wikipedia nous souffle $$\sum_{i=0}^{\infty} \binom{2i}{i} \cdot x^i = \frac{1}{\sqrt{1-4x}}
$$ Par produit de Cauchy : $$
\frac{1}{1-4x} = \sum_{n=0}^{\infty} \sum_{k=0}^{n} \binom{2k}{k} \cdot \binom{2(n-k)}{n-k} \cdot x^n,$$ et le résultat s'ensuit.
-- Désolé, pas vu le post de Paul, deux minutes avant moi ! -
Une preuve de Marta Sved :--->https://link.springer.com/article/10.1007/BF03026737
-
Merci cidrolin pour les références.
J'ai eu du mal à chercher des infos sur internet
Ce qu'il faut chercher, c'est donc "convolution of central binomial coefficients" -
Pour des informations : ---> https://oeis.org/A067804
-
Merci infiniment marsup, Cidrolin pour vos interventions.
Qui a dit que ce n’était pas intéressant ?
Ce n’est pas Marta Sved en tout cas ! (cf. ci-dessous et https://www.math.ucdavis.edu/~deloera/TEACHING/MATH245/combinatproofident.pdf)
J’ai appris plein de choses, me suis passionnée le temps d’un après-midi sur la vie de Marta et du couple Szekeres (et les copies, pendant ce temps là ?... ).
https://fr.wikipedia.org/wiki/George_Szekeres
http://www.austms.org.au/Gazette/2005/Sep05/Szekeres.pdf
Vive les maths !
[size=x-small]Allez, les copies :-( [/size] -
Bonjour,
Je connais une démonstration élémentaire de cette formule, qui utilise une suite de polynômes plutôt qu'une série entière. Soit $P_n(X)=\sum_{k=0}^n \binom{2k}k\binom{2n-2k}{n-k}X^k$.
La symétrie des coefficients entraîne que $P_n(X)=X^nP_n(\frac 1X)$, ce qui entraîne en dérivant que $P'_n(1)=\frac n2 P_n(1)$.
Puis on dérive $P_{n+1}$ :
\begin{align*}
P'_{n+1}(X) &=\sum_{k=1}^{n+1} k\binom{2k}k\binom{2n-2(k-1)}{n-(k-1)}X^{k-1}\\
&=\sum_{k=0}^{n} (k+1)\binom{2k+2}{k+1}\binom{2n-2k}{n-k}X^k\quad\text{changement d'indice}\\
&=2\sum_{k=0}^{n} (k+1)\binom{2k+1}{k}\binom{2n-2k}{n-k}X^k\quad\text{car }\binom{2k+2}{k+1}=2\binom{2k+1}{k}\\
&=2\sum_{k=0}^{n} (k+1)\left[ \binom{2k}{k}+\frac k{k+1}\binom{2k}k \right]\binom{2n-2k}{n-k}X^k\quad\text{Pascal}\\
&=2\sum_{k=0}^{n} (k+1)\binom{2k}{k}\binom{2n-2k}{n-k}X^k+2\sum_{k=0}^{n} k\binom{2k}k\binom{2n-2k}{n-k}X^k\\
&=2[XP_n(X)]'+2XP'_n(X)=2P_n(X)+4XP'_n(X)
\end{align*}
On en déduit que $P'_{n+1}(1)=2P_n(1)+4P'_n(1)$, c'est à dire $\frac{n+1}2P_{n+1}(1)=2P_n(1)+2nP_n(1)$, ce qui entraîne que $P_{n+1}(1)=4P_n(1)$ et on termine la preuve par une récurrence.
Remarque : on en déduit aussi en intégrant la dernière égalité, que $P_{n+1}(X)=P_{n+1}(0)+4XP_n(X)-2\int_0^XP_n(t) dt$ ce qui entraîne que $2\int_0^1P_n(t) dt=P_{n+1}(0)$, soit encore :
$$\sum_{k=0}^{n} \frac1{k+1}\binom{2k}{k}\binom{2n-2k}{n-k}=\binom{2n+1}n$$ -
Merci Clairon, et merci Incognito.
La somme $\displaystyle \sum_{k=0}^n \binom{2k}k\binom{2n-2k}{n-k} (-1)^k$ est étudiée par M. Spivey dans A combinatorial Proof for the Alternating Convolution of the Central Binomial Coefficients, dans le AMM de juin-juillet 2014 page 537. Il trouve : -
Bonsoir Cidrolin,
En reprenant les polynômes $P_n$ que j'ai introduits précédemment, on a $P_n(X)=X^nP_n(\frac1X)$, on voit tout de suite que $P_n(-1)=0$ si $n$ est impair. Pour les indices pairs, en dérivant, on a $P'_{2n}(X)=2nX^{2n-1}P_{2n}(X)-X^{2n-2}P'_{2n}(\frac1X)$, d'où , $P'_{2n}(-1)=-2nP_{2n}(-1)-P'_{2n}(-1)$ et donc $P'_{2n}(-1)=-nP_{2n}(-1)$.
Puis en reprenant ma démonstration précédente, $P'_{2n+1}(X)=2P_{2n}(X)+4XP'_{2n}(X)$, d'où $P'_{2n+1}(-1)=2P_{2n}(-1)-4P'_{2n}(-1)=(4n+2)P_{2n}(-1)$. De même, $P'_{2n+2}(-1)=2P_{2n+1}(-1)-4P'_{2n+1}(-1)=-4P'_{2n+1}(-1)$ (car $P_{2n+1}(-1)=0$), et donc $P'_{2n+1}(-1)=-\frac14P'_{2n+2}(-1)=\frac{n+1}4P_{2n+2}(-1)$, il en découle que $P_{2n+2}(-1)=\frac{4(4n+2)}{n+1}P_{2n}(-1)$. Si on admet que $P_{2n}(-1)=4^n\binom{2n}n$ (récurrence), alors :
$$P_{2n+2}(-1)=\frac{4(4n+2)}{n+1}4^n\binom{2n}n=4^{n+1}\frac{(2n)!(2n+1)2}{(n+1)!n!}=4^{n+1}\binom{2n+2}{n+1}$$ -
Merci Incognito.
Remplaçons la somme par un produit et posons $u_n=\displaystyle \prod_{k=0}^n \binom{2k}k\binom{2n-2k}{n-k}$.
Posons enfin $v_n=\dfrac{u_{n-1}u_{n+1}}{u_n^2}$ (pour $n>0$). Par exemple $v_4=12,96$.
Je conjecture que $\lim v_n =16$. -
Tu veux dire... ? $$u_n = \prod_{k=0}^n \bigg[\binom{2k}{k} \cdot \binom{2(n-k)}{n-k}\bigg] = \Bigg[\prod_{k=0}^n \binom{2k}{k}\Bigg]^2
$$ Les carrés ne font qu'alourdir le problème, donc j'écris à la place $a_n = \sqrt{u_n} = \prod_{k=0}^n \binom{2k}{k}% = \frac{\prod_{k=1}^n (2k)!}{\big(\prod_{k=1}^n k!\big)^2}
$.
N'a-t-on pas tout simplement... (Stirling central = Moivre) ? $$
\frac{a_{n+1}}{a_n} = \binom{2n+2}{n+1} \sim\frac{4^{n+1}}{\sqrt{\pi n}},
$$ d'où en effet : $\dfrac{a_{n+1}\cdot a_{n-1}}{a_n^2} \to 4$.
La même chose avec des $(u_n)$ tend donc bien vers $16$. -
Bravo Marsup.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres