Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Autre AnalyseTopics traitant de analyse [tout]Lister tous les topics de mathématiques
Niveau autre
Partager :

Sommes de combinaisons

Posté par downfall (invité) 26-08-05 à 12:07

Bonjour,

je cherche à calculer ce genre de sommes :

\sum_{n_{1} \leq k \leq n_{2}}^{} \:\:\: C_{m+k}^{m}

comment faire ? quelqu'un peut m'expliquer ? ya surement des formules basiques à utliser pour faire ça, lesquelles ? que signifient n1 et n2 en fait ? on pourrait m'ecrire ausis les premiers termes de la sommes que je vois ce que signifient les indices ? merci  

Posté par
Nicolas_75 Correcteurre : Sommes de combinaisons 26-08-05 à 12:26

Une piste :
\Bigsum_{n_1\le k \le n_2} \({m+k\\m}\)=\Bigsum_{n_1\le k \le n_2} \({m+k\\k}\)

Puis utiliser terme après terme :
p\({n\\p}\)=n\({n-1\\p-1}\)

Cela permet d'agglutiner progressivement les termes, mais je n'ai pas fini les calculs.


Nicolas

Posté par
Nicolas_75 Correcteurre : Sommes de combinaisons 26-08-05 à 12:27

Pour répondre à ta question, n_1 et n_2 sont des entiers quelconques, apparemment.

Posté par downfall (invité)re : Sommes de combinaisons 26-08-05 à 12:52

d'accord, merci

Posté par
Nicolas_75 Correcteurre : Sommes de combinaisons 26-08-05 à 18:54

En fait, j'étais parti sur une mauvaise piste.
Il suffit d'appliquer "bêtement" la formule du triangle de Pascal.

On cherche S(m)=\Bigsum_{k=n_1}^{n_2} \({m+k\\m}\)

S(m)=\Bigsum_{k=n_1}^{n_2} \({m+k\\m}\)
= \Bigsum_{k=n_1}^{n_2} (\({m+k-1\\m-1}\)+\({m+k-1\\m}\))
= \Bigsum_{k=n_1}^{n_2} \({m+k-1\\m-1}\) + \Bigsum_{k=n_1}^{n_2} \({m+k-1\\m}\)
= S(m-1) + \Bigsum_{k'=n1-1}^{n2-2} \({m+k'\\m}\)
= S(m-1) + \Bigsum_{k'=n1}^{n2} \({m+k'\\m}\) - \({m+n_2\\m}\) + \({m+n_1-1\\m}\)
= S(m-1) + S(m) - \({m+n_2\\m}\) + \({m+n_1-1\\m}\)

Donc :
S(m-1)=\({m+n_2\\m}\)-\({m+n_1-1\\m}\)

Et :
\fbox{S(m)=\({m+n_2+1\\m+1}\)-\({m+n_1\\m+1}\)=\({m+n_2+1\\n_2}\)-\({m+n_1\\n_1-1}\)}

Nicolas

Posté par
elhor_abdelali Correcteurre : Sommes de combinaisons 26-08-05 à 19:09

Bonjour;
on peut remarquer que
3$\fbox{\forall k\ge0\\C_{m+k}^{m}=C_{m+k+1}^{m+1}-C_{m+k}^{m+1}} et donc que
\Bigsum_{k=n__1}^{k=n_2}C_{m+k}^{m}=\Bigsum_{k=n__1}^{k=n_2}C_{m+k+1}^{m+1}-C_{m+k}^{m+1} qui est une somme téléscopique d'où
3$\blue\fbox{\Bigsum_{k=n__1}^{k=n_2}C_{m+k}^{m}=C_{m+n_2+1}^{m+1}-C_{m+n_1}^{m+1}}

Bien entendu on convient 2$\fbox{p>n\\C_{n}^{p}=0}

Posté par aicko (invité)re : Sommes de combinaisons 26-08-05 à 19:11

Nicolas_75
attention a tes indices

\sum_{n_1-1}^{n_2-2} n'est pas definie pour n_1 et n_2 entiers quelconques

Posté par jmix90 (invité)re : Sommes de combinaisons 26-08-05 à 19:13

aicko, oui mais ca n'aurait aucun sens de calculer la somme quand ils ne sont pas définis non ?

Amicalement

Posté par aicko (invité)re : Sommes de combinaisons 26-08-05 à 19:15

elhor_abdelali cette demonstration est tres rigoureuse
chapeau

Posté par
Nicolas_75 Correcteurre : Sommes de combinaisons 26-08-05 à 19:16

aicko, c'est toi qui distribues les bonnes notes, ce soir ?
Merci pour ta remarque sur tes indices, tout à fait justifiée.

Posté par
Nicolas_75 Correcteurre : Sommes de combinaisons 26-08-05 à 19:17

lapsus : "ta remarque sur mes indices"

Posté par aicko (invité)re : Sommes de combinaisons 26-08-05 à 19:19

jmix90
ben disons que la somme n'a pas de sens, dans la demonstration de Nicolas_75, il faudrait proceder par distinction des cas.

celle de elhor_abdelali evite cette distinction

Posté par aicko (invité)re : Sommes de combinaisons 26-08-05 à 19:20

"aicko, c'est toi qui distribues les bonnes notes, ce soir ?"
sans commentaire, par contre sur cette remarque

j'aurais pas cette pretention

Posté par jmix90 (invité)re : Sommes de combinaisons 26-08-05 à 19:21

Aicko, ok retire ma remarque !

Nicolas_75, t'est en forme ce soir !

elhor_abdelali, bravo !

Posté par
Nicolas_75 Correcteurre : Sommes de combinaisons 26-08-05 à 19:22

Posté par
Nicolas_75 Correcteurre : Sommes de combinaisons 17-01-06 à 16:03

Bonjour,

J'ai eu besoin de tout mettre au propre pour un lemme qui me servira dans une petite recherche personnelle. Autant poster ici ma rédaction pour capitaliser un peu.

Ci-dessous trois démonstrations de :

\fbox{\Bigsum_{k=n_1}^{n_2}{m+k\choose m}=\{{{m+n_2+1\choose m+1}\quad\textrm{si}\quad n_1=0\\ {m+n_2+1\choose m+1}-{m+n_1\choose m+1}\quad\textrm{si}\quad n_1\ge 1}}
où n_1, n_2, m\in\mathbb{N} et n_1\le n_2

Démonstration 1 : la plus simple et élégante, c'est celle de elhor_abdelali ci-dessus.
On applique la relation du triangle de Pascal.

Si n_1\ge 1 :
\Bigsum_{k=n_1}^{n_2}{m+k\choose m}=\Bigsum_{k=n_1}^{n_2}{m+1+k\choose m+1}-{m+k\choose m+1}={m+n_2+1\choose m+1}-{m+n_1\choose m+1}

Si n_1=0 :
\Bigsum_{k=0}^{n_2}{m+k\choose m}=[\Bigsum_{k=1}^{n_2}{m+1+k\choose m+1}-{m+k\choose m+1}]+{m\choose m}={m+n_2+1\choose m+1}-{m+1\choose m+1}+{m\choose m}={m+n_2+1\choose m+1}

Démonstration 2 : bien plus bourrine !
(mais qui fait appel à des méthodes qui marchent dans beaucoup de cas, et qui permettent de s'en sortir (laborieusement) si on ne voit pas l'astuce)

Soit A = \Bigsum_{k=n_1}^{n_2}{m+k\choose m}
On reconnait le coefficient de X^m dans (1+X)^{n_1+m}...(1+X)^{n_2+m}
Or (1+X)^{n_1+m}...(1+X)^{n_2+m}=(1+X)^{n_1+m}[1+...+(1+X)^{n_2-n_1}]=(1+X)^{n_1+m}\frac{(1+X)^{n_2-n_1+1}-1}{X}
Donc :
A=\Bigsum_{i=a}^b coef. de X^{m-i} dans (1+X)^{n_1+m} * coef. de X^i dans (1+X)^{n_1+m}\frac{(1+X)^{n_2-n_1+1}-1}{X}
où a et b sont choisis tel que :
(i) 0\le i\le (n_2-n_1+1)-1
(ii) 0\le m-i\le n_1+m
Donc :
A=\Bigsum_{i=0}^{\min(n_2-n_1;m)}{n_1+m\choose m-i}{n_2-n_1+1\choose i+1}
On procéde au changement d'indice i\to i-1 :
\fbox{A=\Bigsum_{i=1}^{\min(n_2-n_1+1;m+1)}{n_1+m\choose m+1-i}{n_2-n_1+1\choose i}}
On se dit que cela est proche du coefficient C de X^{m+1} dans (1+X)^{n_1+m}(1+X)^{n_2-n_1+1}
Comment s'exprime ce coefficient ?
C=\Bigsum_{i=a}^{b} coef. de X^{m+1-i} dans (1+X)^{n_1+m} * coef. de X^i dans (1+X)^{n_2-n_1+1}
où a et b sont choisis tel que :
(i) 0\le i\le n_2-n_1+1
(ii) 0\le m+1-i\le n_1+m c'est-à-dire 1-n_1\le i\le m+1
Si n_1=0, alors la borne inférieure de la somme est a=1
et C=\Bigsum_{i=1}^{\min(n_2-n_1+1;m+1)}{n_1+m\choose m+1-i}{n_2-n_1+1\choose i}=A
Si n_1\ge 1, alors la borne inférieure de la somme est a=0
et C=\Bigsum_{i=0}^{\min(n_2-n_1+1;m+1)}{n_1+m\choose m+1-i}{n_2-n_1+1\choose i}=A+{n_1+m\choose m+1}
Donc :
A=\{{C\quad\textrm{si}\quad n_1=0\\ C-{n_1+m\choose m+1}\quad\textrm{si}\quad n_1\ge 1}
Or C est le coefficient X^{m+1} dans (1+X)^{n_1+m}(1+X)^{n_2-n_1+1}=(1+X)^{m+n_2+1}, donc C={m+n_2+1\choose m+1}
D'où le résultat.

Démonstration 3 : par récurrence sur n_2
C'est immédiat en utilisant la relation du triangle de Pascal.

Sauf erreur.

Nicolas


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !