Somme de coefficients binomiaux
Réponses
-
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] -
$k^2=k(k-1)+k$ et $k\binom{n}{k}=n\binom{n-1}{k-1}$ (me semble-t-il).
-
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.Personne n'a raison contre un enfant qui pleure. -
Oui, je l'ai fait, n'existe-t-il pas d'autre méthodes calculatoires pour le faire.
-
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}$. -
Félicitations – pour la méthode du polynôme, pour l'autre, et pour ta volonté de faire la deuxième quand même.
-
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 -
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. -
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 ?
-
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? -
Ce n'est pas très génial mais une simple récurrence sur p résout rapidement le problème.
-
Bonsoir, svp Je peux avoir une indication pour ma dernière somme que j'ai postée.
-
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$ ! -
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 ! -
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}$ -
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.
-
J'ai déjà résolu cet exercice.
-
ok merci, ça me fait une méthode de plus.
-
Je vous en prie, c'est avec plaisir ! C'est toujours bien autant que cela se peut, d'avoir plus d'une méthode.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 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
- 63 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
- 313 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
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres