Somme de coefficients binomiaux

Gon · September 2019

Bonjour, pouvez-vous me donner une indication pour cette somme.
J'ai essayé de réécrire le membre de gauche, mais rien qui pourrait me faire avancer, donc si vous avez une indication.

Merci d'avance pour votre réponse. 89938

ev · September 2019

Ici ?

e.v.

Gon · September 2019

Je viens à peine de le trouver, j'ai utilisé le tableau de [large]P[/large]ascal pour exprimer le membre de gauche en une somme télescopique.
Merci aussi @ev, je vais regarder d'autres méthodes sur ce post.

[Blaise Pascal (1623-1662) prend toujours une majuscule. AD]

Gon · September 2019

Sinon, voici comment je le fais :
l'expression ${n+k\choose n}={n+k+1\choose n}-{n+k\choose n}$ en utilisant le tableau de [large]P[/large]ascal.
D'où $\sum_{k=0}^p{n+k\choose n}=\sum_{k=0}^p{({n+k+1\choose n+1}-{n+k\choose n+1})}=1+\sum_{k=1}^p{({n+k+1\choose n+1}-{n+k\choose n+1})}$.

Considérons la suite $(U_k)_{k\geq 1}$ de terme général $U_{k}={n+k\choose n+1}$, alors $U_{k+1}={n+k+1\choose n+1}$.
Ainsi : $\sum_{k=0}^p{n+k\choose n}=1 +\sum_{k=1}^p{U_{k+1} -U_{k}}$=$1+(U_{p+1}-U_{1})$,
et comme $U_{1}=1$, on obtient que $\sum_{k=0}^p{n+k\choose n}=U_{p+1}={n+p+1\choose n+1}$.

[Blaise Pascal (1623-1662) prend toujours une majuscule. AD]

Gon · September 2019

Merci @AD.

Une indication pour cette somme svp. 89942

Math Coss · September 2019

$k^2=k(k-1)+k$ et $k\binom{n}{k}=n\binom{n-1}{k-1}$ (me semble-t-il).

ev · September 2019

Peux tu calculer

\[ \sum_{k=0} \dbinom{n}{k} x^k, \; \qquad \sum_{k=0} k\dbinom{n}{k} x^k \; \qquad \text{ et } \sum_{k=0} k^2 \dbinom{n}{k} x^k ? \]

e.v.

Gon · September 2019

Oui, je l'ai fait, n'existe-t-il pas d'autre méthodes calculatoires pour le faire.

Gon · September 2019

Soit $x\in \mathbb{R}$. La fonction : $$\begin{array}{ccccc}
f & : & \mathbb{R} & \to & \mathbb{R} \\
& & x & \mapsto & \sum_{k=0}^n{{n\choose k}}.x^{k} \\
\end{array}
$$ est 2 fois dérivables sur $\mathbb{R}$ car somme de fonctions polynomiales 2 fois dérivables sur $\mathbb{R}$.
Alors pour tout $x \in \mathbb{R}$, on a $f'(x)=\sum_{k=1}^n{k.{n\choose k}}.x^{k-1}$ et $f''(x)=\sum_{k=2}^n{k(k-1).{n\choose k}}.x^{k-2}$.

Par ailleurs on remarque que pour tout $x \in \mathbb{R}$, $~f(x)=(x+1)^{n}$ en utilisant la formule du binôme de Newton.
Ainsi on a aussi pour tout $x \in \mathbb{R}$, $~f'(x)=n(x+1)^{n-1}$ et $f''(x)=n(n-1)x^{n-2}$.
Après calcul, on a $\sum_{k=0}^n{k^{2}.{n\choose k}}.x^{k}=x^{2}.f''(x)+f'(x)$.

Pour $x=1$, on a $\sum_{k=0}^n{k^{2}.{n\choose k}}=f''(1)+f'(1)$.
$\sum_{k=0}^n{k^{2}.{n\choose k}}=n(n-1)2^{n-2}+n2^{n-1}=n(n+1)2^{n-2}$.

Gon · September 2019

@Math Coss, ta méthode aussi est bonne,j'ai trouvé le même résultat.

Math Coss · September 2019

Félicitations – pour la méthode du polynôme, pour l'autre, et pour ta volonté de faire la deuxième quand même.

jean lismonde · September 2019

bonjour

Math Coss te suggère la méthode combinatoire
et ev préfère la méthode analytique avec la double dérivation du binôme développé de degré n

la seconde méthode est semble-t-il plus rapide, elle donne le résultat : $n(n+1).2^{n-2}$

je ne connais pas d'autres démonstrations

cordialement

Gon · September 2019

on peut l'adapter aussi pour cette somme n'est-ce pas? Concernant la méthode analytique. 89952

Math Coss · September 2019

Voici une troisième méthode, « vraiment » combinatoire. La somme \[\sum_{k=0}^nk\binom{n}{k}\] est le cardinal de l'ensemble $F$ des couples $(x,A)$ où $x$ est un élément de $E=\{1,\dots,n\}$ et $A$ une partie de $E$ qui contient $x$. En effet, on réalise une partition de $F$ selon le cardinal de $A$. Pour $k$ entre $0$ et $n$, il y a $\binom{n}{k}$ parties $A$ de cardinal $k$ et, pour chacune d'entre elles, $k$ éléments $x$ possibles.

On peut calculer le cardinal de $F$ en choisissant d'abord l'élément $x$ – il y a $n$ choix possibles – puis une partie $A'$ dans l'ensemble $E\setminus\{x\}$, qui a $n-1$ éléments – il y a $2^{n-1}$ choix – et former $A=\{x\}\cup A'$. En justifiant proprement les choses, on voit qu'il y a $n2^{n-1}$ éléments dans $F$.

Pour la somme \[\sum_{k=0}^n\frac{k(k-1)}{2}\binom{n}{k}\] on introduit l'ensemble $G$ des triplets $(x,y,A)$ où $x$ et $y$ sont des éléments distincts de $E$ et $A$ une partie de $E$ qui les contient tous deux. On a facilement une formule sans somme pour le cardinal de $G$, c'est $\frac{n(n-1)}{2}2^{n-2}$. De là à la somme des $k^2\binom{n}{k}$ sans difficulté.

Pourrait-on calculer directement la somme des $k^2\binom{n}{k}$ avec l'ensemble $H$ des triplets $(x,y,A)$ où $x$ et $y$ sont des éléments distincts ou non de $E$ et $A$ une partie qui les contient ? Dans le comptage sans somme, on est amené à ajouter $n(n-1)2^{n-2}$ et $n2^{n-1}$, ce qui revient essentiellement au même que précédemment.

Math Coss · September 2019

Oui, on peut adapter le calcul du polynôme pour la somme $\sum_{k=0}^nk^2\binom{2n}{2k}$. Qu'est-ce que tu proposes ?

Gon · September 2019

je voulais faire un changement d'indice en posant $p=2k$ mais,si je fais ainsi,ça signifie que p prendra seulement les valeurs paires,ce qui est faux à mon avis(les seuls changements d'indice qu'on utilise sont la translation et la symétrie).
C'est bien ça?

Rawlanovitch Silgaëv · September 2019

Ce n'est pas très génial mais une simple récurrence sur p résout rapidement le problème.

Gon · September 2019

Bonsoir, svp Je peux avoir une indication pour ma dernière somme que j'ai postée.

Gon · September 2019

@Raw je ne vois pas trop où tu veux en venir. Peux-tu mieux m'éclairer?

Math Coss · September 2019

Suggestion : reprendre le calcul de $f(x)=\sum_{j=0}^{2n}\bigl(\frac{j}2\bigr)^2\binom{2n}{j}x^j$ et jouer entre $f(1)$ et $f(-1)$ (ou $f(x)$ et $f(-x)$) pour éliminer les termes d'indice $j$ impair.

Edit : Grmbl, j'ai oublié $x^j$ !

Rawlanovitch Silgaëv · September 2019

Récurrence forte: pour $n \in \mathbb{N}$ quelconque fixé, si on appelle $(H_p)$ la relation que vous voulez établir, alors $(H_0)$ est triviale. On suppose ensuite que $(H_i)$ est vraie pour $i$ allant de $0$ à $p-1$ et on montre qu'alors $(H_p)$ est vraie.
NB: il faudra remarquer pour utiliser l'hypothèse de récurrence, que $C_n^{k+1}+C_n^k = C_{n+1}^{k+1}$. Je l'avais fait et c'est assez simple !

Gon · September 2019

@Raw, je n’ai pas de récurrence à faire, c’est un calcul qu’on me demande.
Je n’ai qu’une seule expression comment établir la récurrence ici?

bd2017 · September 2019

Bonjour
Toujours avec le même principe $p(x)=(1+x)^{2n}+(1-x)^{2n}$ conduit à la relation
$\sum_{k=0}^n k^2 C_{2n}^{2k}=1/8(f''(1)+f'(1))=n(2n+1) 2 ^{2n-4}$

Gon · September 2019

Bonsoir @bd2017 peux-tu me m'expliquer l'idée qui t'a poussé à poser $p(x)$ ?

Merci d'avance pour ta réponse.

@Math Coss, j'avais fait ce changement,mais je crois que dans mes calculs je me suis mélangé les pédales. Je vais recommencer, et merci bien.

Rawlanovitch Silgaëv · September 2019

Désolé du long temps de réponse... il me fallait rédiger en $\LaTeX{}$.
Voilà à peu près ce que je disais :
soit $n \in \mathbb{N}$ fixé. Posons $$(H_p):\: \displaystyle \sum_{k=0}^p C_{n+k}^n = C_{n+p+1}^{n+1}.
$$

$(H_0):\: \displaystyle\sum_{k=0}^0 C_{n+k}^n = C_{n}^n = 1 = C_{n+1}^{n+1} = C_{n+0+1}^{n+1}.$ Par conséquent $(H_0)$ est vraie.
Supposons que $(H_0), (H_1), \cdots, (H_{p-1})$ sont vraies et montrons qu'alors $(H_p)$ est vraie.
\begin{eqnarray}\label{eq1}
(H_{p-1}) \quad \text{vraie} \quad &\Longleftrightarrow& \displaystyle \sum_{k=0}^{p-1} C_{n+k}^n = C_{n+p}^{n+1}\nonumber\\
&\Longrightarrow& C_{n+p}^n+\sum_{k=0}^{p-1} C_{n+k}^n = C_{n+p}^n+C_{n+p}^{n+1}\nonumber\\
&\Longrightarrow& \sum_{k=0}^p C_{n+k}^n = C_{n+p}^n+C_{n+p}^{n+1}.\qquad(1)
\end{eqnarray}
Or comme je le disais il faut remarquer que $C_N^K+C_N^{K+1}=C_{N+1}^{K+1} \quad (\ast).$
En appliquant enfin $(\ast)$ dans $(1)$ avec $N=n+p$ et $K=n$ on obtient
$\displaystyle \sum_{k=0}^p C_{n+k}^n = C_{n+p+1}^{n+1}$; ce qui n'est autre que la relation $(H_p)$.
Et comme la démonstration est vraie pour tout $n \in \mathbb{N}$ fixé, finalement $\forall \ n, p \in \mathbb{N},~(H_p)$ est vraie. CQFD.