somme inverses coefficients binomiaux

Bonjour.
On note C(n,p)=n!/p!(n-p)!
On considère la suite u définie par u(n):=somme de p=0 à n de 1/C(n,p)
(Désolé je ne me suis pas encore mis à Latex)
Je sais que la suite converge vers 2 (le théorème des gendarmes permet de le prouver) mais je n'arrive pas à prouver que la suite est décroissante à partir du rang 4.
Quelqu'un aurait-il une idée ?
Merci d'avance.
JC

Réponses

  • J'ai une petite idée ... mais il faut voir si elle aboutit :

    On pose : $S_i= \frac{\sum_{p=0,\neq i}^n C_n^p}{C_n^i}$.

    On remarque alors que:
    $(\sum_{p=0}^{n} u_n)(\sum_{p=0}^{n}C_n^p) = (n+1)+\sum_{i=0}^{n}S_i$ , d'où
    $u_n= \frac{(n+1)+\sum_{i=0}^{n}S_i}{2^n}$.

    On a alors $u_{n+1}-u_n= \frac{-n+S_{n+1}}{2^{n+1}}$.
    Il suffirait alors de montrer que pour $n \geq 4$ :

    $S_{n+1} \leq n$.

    Rmeraque : $u_n$ est la suite que tu as définis...

    A vérifier...

    Jabir.
  • Jrectifie une erreur:


    J'ai une petite idée ... mais il faut voir si elle aboutit :

    On pose : $S_i= \frac{\sum_{p=0,\neq i}^n C_n^p}{C_n^i}$.

    On remarque alors que:
    $ u_n(\sum_{p=0}^{n}C_n^p) = (n+1)+\sum_{i=0}^{n}S_i$ , d'où
    $u_n= \frac{(n+1)+\sum_{i=0}^{n}S_i}{2^n}$.

    On a alors $u_{n+1}-u_n= \frac{-n+S_{n+1}}{2^{n+1}}$.
    Il suffirait alors de montrer que pour $n \geq 4$ :

    $S_{n+1} \leq n$.

    Rmeraque : $u_n$ est la suite que tu as définis...

    A vérifier...

    Jabir.
  • Merci pour la réponse.
    Je vais refaire tes calculs à tête reposée.
    Cela me confirme que le résultat n'était pas immédiat.
    J-Claude
  • Bonjour,

    Le $S_i$ que tu introduis Jabir, c'est en fait un $S_{i,n}$ car il dépend aussi de $n$ non ???
  • Bonjour,


    Oui , effectivement . On a en fait :


    $S_{i,n} = \frac{\sum_{p=0,\neq i}^n C_n^p}{C_n^i}$.

    On remarque alors que:
    $ u_n(\sum_{p=0}^{n}C_n^p) = (n+1)+\sum_{i=0}^{n}S_{i,n}$ , d'où
    $u_n= \frac{(n+1)+\sum_{i=0}^{n}S_{i,n}}{2^n}$.

    Soit $n \geq 1$ :
    On a alors $u_{k}-u_{k-1}= \frac{-k+1+S_{k,n}}{2^{k}}$ pour tout entier $k$ tel que $n \geq k \geq 1$
    Il suffirait alors de montrer que pour tout couple d'entiers $(n,k)$ tel que $n \geq k \geq 4$ :

    $S_{k,n} \leq k-1$.

    Sauf erreur...

    Jabir.
  • Je m'immisce dans ce fil uniquement pour sortir mon Gould, ce que je fais à chaque fois qu'il y a un calcul de combinaisons. Ainsi, dans le Gould, on trouve l'identité suivante (identité 2.25) : $$\sum_{p=0}^{n} \frac {1}{\binom {n} {p}} = \frac {n+1}{2^{n+1}} \sum_{p=1}^{n+1} \frac {2^p}{p}.$$ Cette identité se généralise à $\displaystyle {\sum_{p=0}^{n} \frac {x^p}{\binom {n} {p}}}$.

    Borde.
  • Je crois qu'on doit pouvoir s'en sortir en étudiant la différence u(n)-u(n+1) et en procédant à des regroupements de termes.
  • je dois probablement passer à côté d'un truc ... Comment tu fais ton calcul des $u_{n+1} - u_{n}$ ...

    Voilà mon problème :
    \[
    \begin{array}{lll}
    u_{n+1} - u_n &=&\frac{(n+2)+\sum_{i=0}^{n+1}S_{i,n+1}}{2^{n+1}}-\frac{(n+1)+\sum_{i=0}^{n}S_{i,n}}{2^{n}}\\
    &=&\frac{1}{2^{n+1}} \left( -n + \sum_{i=0}^{n+1}S_{i,n+1} - 2 \sum_{i=0}^n S_{i,n}\right)
    \end{array}
    \]

    Comment tu traites la somme ?

    Tiens, Borde, c'est quoi le "Gould" ??? Ca m'a l'air pas mal cette égalité...
  • Le Gould est le répertoire d'identités toutes à base de coefficients binomiaux suivant : <B>H. W. Gould</B>, <I>Combinatorial identites. A standardized set of tables listing 500 binomial coefficients summations</I>, Morgantown, West Virginia (1972).
    <BR>
    <BR>Il n'y a pas les preuves, seulement les identités, avec un renvoi en références. Par exemple, celle-ci provient de l'article <a href=" http://www.emis.de/cgi-bin/zmfr/ZMATH/fr/quick.html?first=1&maxdocs=3&type=html&an=0030.28901&format=complete"&gt; http://www.emis.de/cgi-bin/zmfr/ZMATH/fr/quick.html?first=1&maxdocs=3&type=html&an=0030.28901&format=complete</a&gt; (pour ceux qui lisent le norvégien).
    <BR>
    <BR>Borde.<BR>
  • Merci pour cette référence.
  • Laisse tomber Crou , j'ai déliré....
  • Posons : u(n)=(somme de k=0 à n)1/C(n,k). On a :

    u(n)-u(n+1)= [(somme de k=0 à n)1/C(n,k)-1/C(n+1,k)]-1/C(n+1,n+1).

    Posons : v(n,k)=1/C(n,k)-1/C(n+1,k), pour 0<=k<=n
    Il est clair que : v(n,0)=0 et v(n,k)>0 pour k>=1.

    On peut écrire :
    u(n)-u(n+1)=[(somme de k=0 à n)v(n,k)]-1.
    Pour n>=4, on en déduit que :
    u(n)-u(n+1)>=v(n,1)+v(n,2)+v(n,n-1)+v(n,n)-1
    On a :
    v(n,1)=1/n-1/(n+1)=1/n(n+1)
    v(n,n-1)=1/C(n,n-1)-1/C(n+1,n-1)=1/C(n,1)-1/C(n+1,2)
    =1/n-2/(n+1)n=(n-1)/n(n+1).
    v(n,n)=1/C(n,n)-1/C(n+1,n)=1-1(n+1)=n/(n+1).

    Additionnons les termes :
    v(n,1)+v(n,n-1)+v(n,n)=1/n(n+1)+(n-1)/n(n+1)+n/(n+1)=1
    On en déduit que :
    u(n)-u(n+1)>=v(n,2)+1-1=v(n,2)>0.
  • {\bf Traduction LATEX de la solution de Richard André-Jeannin}:

    Posons : $u_n=\sum_{k=0}^ n \frac{1}{C_n^k}$. On a :

    $u_n-u_{n+1}= [\sum_{k=0}^n \frac{1}{C_n^k}-\frac{1}{C_{n+1}^k}]-\frac{1}{C_{n+1}^{n+1}}$.

    Posons : $v_{n,k}=\frac{1}{C_n^k}-\frac{1}{C_{n+1}^k}, pour
    $0 \leq k \leq n$
    Il est clair que : $v_{n,0}=0$ et $v_{n,k}>0$ pour $k \geq 1$.

    On peut écrire :
    $u_n-u_{n+1}=[\sum_{k=0}^n v_{n,k}]-1$.
    Pour $n \geq 4$, on en déduit que :

    $u_n-u_{n+1} \geq v_{n,1}+v_{n,2}+v_{n,n-1}+v_{n,n}-1$
    On a :
    $v_{n,1}=\frac{1}{n}-\frac{1}{n+1}=\frac{1}{n(n+1)}$

    $v_{n,n-1}=\frac{1}{C_{n}^{n-1}}-\frac{1}{C_{n+1}^{n-1}}=\frac{1}{C_{n}^{1}}-\frac{1}{C_{n+1}^{2}}
    =\frac{1}{n}-\frac{2}{n(n+1)}=\frac{n-1}{n(n+1)}$.

    $v_{n,n}=\frac{1}{C_{n}^{n}}-\frac{1}{C_{n+1}^{n}}=1-\frac{1}{n+1}=\frac{n}{n+1}$.

    Additionnons les termes :

    $v_{n,1}+v_{n,n-1}+v_{n,n}=\frac{1}{n(n+1)}+\frac{n-1}{n(n+1)}+\frac{n}{n+1}=1$
    On en déduit que :

    $u_n-u_{n+1} \geq v_{n,2}+1-1=v_{n,2} >0 $.

    Jabir.
  • {\bf Traduction LATEX de la solution de Richard André-Jeannin}:

    Posons : $u_n=\sum_{k=0}^ n \frac{1}{C_n^k}$. On a :

    $u_n-u_{n+1}= [\sum_{k=0}^n \frac{1}{C_n^k}-\frac{1}{C_{n+1}^k}]-\frac{1}{C_{n+1}^{n+1}}$.

    Posons : $v_{n,k}=\frac{1}{C_n^k}-\frac{1}{C_{n+1}^k}$, pour
    $0 \leq k \leq n$.
    Il est clair que : $v_{n,0}=0$ et $v_{n,k}>0$ pour $k \geq 1$.

    On peut écrire :
    $u_n-u_{n+1}=[\sum_{k=0}^n v_{n,k}]-1$.
    Pour $n \geq 4$, on en déduit que :

    $u_n-u_{n+1} \geq v_{n,1}+v_{n,2}+v_{n,n-1}+v_{n,n}-1$
    On a :
    $v_{n,1}=\frac{1}{n}-\frac{1}{n+1}=\frac{1}{n(n+1)}$

    $v_{n,n-1}=\frac{1}{C_{n}^{n-1}}-\frac{1}{C_{n+1}^{n-1}}=\frac{1}{C_{n}^{1}}-\frac{1}{C_{n+1}^{2}}
    =\frac{1}{n}-\frac{2}{n(n+1)}=\frac{n-1}{n(n+1)}$.

    $v_{n,n}=\frac{1}{C_{n}^{n}}-\frac{1}{C_{n+1}^{n}}=1-\frac{1}{n+1}=\frac{n}{n+1}$.

    Additionnons les termes :

    $v_{n,1}+v_{n,n-1}+v_{n,n}=\frac{1}{n(n+1)}+\frac{n-1}{n(n+1)}+\frac{n}{n+1}=1$
    On en déduit que :

    $u_n-u_{n+1} \geq v_{n,2}+1-1=v_{n,2} >0 $.

    Jabir.
  • Merci Jabir pour la traduction.
  • You're welcome!
  • {\bf Traduction LATEX de la solution de Richard André-Jeannin}:

    Posons : $ \displaystyle u_n=\sum\limits_{k=0}^ n \dfrac{1}{C_n^k}$. On a :
    $\displaystyle u_n-u_{n+1}= \left( \sum\limits _{k=0}^n \frac{1}{C_n^k}-\frac{1}{C_{n+1}^k} \right)-\frac{1}{C_{n+1}^{n+1}}$.

    Posons : $\displaystyle v_{n,k}=\frac{1}{C_n^k}-\frac{1}{C_{n+1}^k}$, pour $0 \leq k \leq n$.
    Il est clair que : $v_{n,0}=0$ et $v_{n,k}>0$ pour $k \geq 1$.
    On peut écrire :
    $\displaystyle u_n-u_{n+1}= \left( \sum_{k=0}^n v_{n,k}\right) -1$.
    Pour $n \geq 4$, on en déduit que :
    $\displaystyle u_n-u_{n+1} \geq v_{n,1}+v_{n,2}+v_{n,n-1}+v_{n,n}-1$
    On a :
    $\displaystyle v_{n,1}=\frac{1}{n}-\frac{1}{n+1}=\frac{1}{n(n+1)}$
    $\displaystyle v_{n,n-1}=\frac{1}{C_{n}^{n-1}}-\frac{1}{C_{n+1}^{n-1}}=\frac{1}{C_{n}^{1}}-\frac{1}{C_{n+1}^{2}}
    =\frac{1}{n}-\frac{2}{n(n+1)}=\frac{n-1}{n(n+1)}$.
    $\displaystyle v_{n,n}=\frac{1}{C_{n}^{n}}-\frac{1}{C_{n+1}^{n}}=1-\frac{1}{n+1}=\frac{n}{n+1}$.
    Additionnons les termes :
    $\displaystyle v_{n,1}+v_{n,n-1}+v_{n,n}=\frac{1}{n(n+1)}+\frac{n-1}{n(n+1)}+\frac{n}{n+1}=1$
    On en déduit que :
    $\displaystyle u_n-u_{n+1} \geq v_{n,2}+1-1=v_{n,2} >0 $.
  • Merci à tous pour votre aide.

    Richard, ta démonstration est parfaite. Je vais l'imprimer précieusement.

    Pour trouver l'inégalité citée par Borde il y a une autre méthode que la récurrence ?

    Jean-claude
  • Rectificatif, je parlais de l'égalité citée par Borde (et non de l'inégalité)...
  • Déja, ce n'est pas dit que la récurrence fonctionne...
  • Pour l'identité donnée par maître Borde on peut se reporter à l'article de Gery Huvent joint.
  • ...J'attendais Maître Benoît, qui s'y connaît bien mieux que moi, pour compléter utilement ce que j'ai (bêtement) recopié dans le Gould.

    Borde.
  • Merci Benoît pour ce fichier. Il va m'être très utile.
    J-Claude
  • Je l'avais déjà vue (cette question a traînée sur le forum il y a un certain temps) mais j'aime beaucoup l'astuce du "facteur de sommation". Il y a d'autres suites marrantes où on l'utilise ?
  • On peut, de manière générale, exprimer les solutions des récurrences du type : <P></P><DIV ALIGN="CENTER" CLASS="mathdisplay"><IMG WIDTH="128" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img1.png&quot; ALT="$\displaystyle u_{n+1}=a_n u_n+b_n$"></DIV><P></P>avec <SPAN CLASS="MATH"><IMG WIDTH="48" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img2.png&quot; ALT="$ a_n,\ b_n$"></SPAN> deux suites données.
    <BR>
    <BR>Posons : <SPAN CLASS="MATH"><IMG WIDTH="363" HEIGHT="56" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img3.png&quot; ALT="$ p(n,k)= \prod\limits_{i=k}^{n-1} a_i, \textrm{\ pour\ } 0 \leq k \leq n-1,\textrm{\ et\ } p(n,n)=1$"></SPAN>
    <BR>Il est facile de vérifier, par récurrence sur <SPAN CLASS="MATH"><IMG WIDTH="13" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img4.png&quot; ALT="$ n$"></SPAN>, que : <P></P><DIV ALIGN="CENTER" CLASS="mathdisplay"><IMG WIDTH="225" HEIGHT="61" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img5.png&quot; ALT="$\displaystyle u_n = p(n,0) u_0 + \sum_{k=1}^n p(n,k) b_{k-1}$"></DIV><P></P>Pour la démonstration, il suffit de remarquer que : <SPAN CLASS="MATH"><IMG WIDTH="160" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img6.png&quot; ALT="$ a_n p(n,k) = p(n+1,k) $"></SPAN>.
    <BR>
    <BR><U>Première application</U> : suite arithmético-géométrique : <SPAN CLASS="MATH"><IMG WIDTH="111" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img7.png&quot; ALT="$ u_{n+1} = a u_n+b$"></SPAN>.
    <BR>On a : <SPAN CLASS="MATH"><IMG WIDTH="104" HEIGHT="35" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img8.png&quot; ALT="$ p(n,k)=a^{n-k}$"></SPAN>, d’où <BR><DIV ALIGN="CENTER" CLASS="mathdisplay"><TABLE CELLPADDING="0" ALIGN="CENTER" WIDTH="100%"><TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG WIDTH="21" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img9.png&quot; ALT="$\displaystyle \newline u_n$"></TD><TD> </TD><TD ALIGN="LEFT" NOWRAP><IMG WIDTH="142" HEIGHT="61" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img10.png&quot; ALT="$\displaystyle = a^n u_0+ b \sum\limits_{k=1}^n a^{n-k}$"></TD><TD CLASS="eqno" WIDTH=10 ALIGN="RIGHT"> </TD></TR><TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG WIDTH="3" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img11.png&quot; ALT="$\displaystyle \newline$"></TD><TD> </TD><TD ALIGN="LEFT" NOWRAP><IMG WIDTH="139" HEIGHT="51" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img12.png&quot; ALT="$\displaystyle =a^n u_0 + b \cdot \frac{1-a^n}{1-a}$"></TD><TD CLASS="eqno" WIDTH=10 ALIGN="RIGHT"> </TD></TR><TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG WIDTH="3" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img11.png&quot; ALT="$\displaystyle \newline$"></TD><TD> </TD><TD ALIGN="LEFT" NOWRAP><IMG WIDTH="204" HEIGHT="54" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img13.png&quot; ALT="$\displaystyle = \frac{b}{1-a} + a^n \left( u_0 - \frac{b}{1-a} \right).
    \newline$"></TD><TD CLASS="eqno" WIDTH=10 ALIGN="RIGHT"> </TD></TR></TABLE></DIV><BR CLEAR="ALL">
    <BR><U>Seconde application</U> (celle du texte de G. Huvent) : <SPAN CLASS="MATH"><IMG WIDTH="165" HEIGHT="50" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img14.png&quot; ALT="$ a_n = \dfrac{n+2}{2(n+1)} \ ;\ b_n=1$"></SPAN>
    <BR>On vérifie que <SPAN CLASS="MATH"><IMG WIDTH="162" HEIGHT="57" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img15.png&quot; ALT="$ p(n,k)=\dfrac{n+1}{2^{n+1}} \cdot \dfrac{2^{k+1}}{k+1}$"></SPAN>. En tenant compte de <SPAN CLASS="MATH"><IMG WIDTH="48" HEIGHT="29" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img16.png&quot; ALT="$ u_0=1$"></SPAN>,
    <BR>La formule devient : <P></P><DIV ALIGN="CENTER" CLASS="mathdisplay"><IMG WIDTH="253" HEIGHT="61" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87387/cv/img17.png&quot; ALT="$\displaystyle u_n = \sum_{k=0}^n p(n,k) = \frac{n+1}{2^{n+1}} \cdot \sum_{k=0}^n \frac{2^{k+1}}{k+1}$"></DIV><P></P>
    [Cela méritait bien une traduction en LaTeX. AD]
  • Salut RAJ,

    tu devrais nous réécrire ça en latèque !

    Borde.
  • On peut, de manière générale, exprimer les solutions des récurrences du type : $$u_{n+1}=a_n u_n+b_n$$ avec $a_n,\ b_n$ deux suites données.

    Posons : $p(n,k)= \prod\limits_{i=k}^{n-1} a_i, \textrm{\ pour\ } 0 \leq k \leq n-1,\textrm{\ et\ } p(n,n)=1$
    Il est facile de vérifier, par récurrence sur $n$, que : $$ u_n = p(n,0) u_0 + \sum_{k=1}^n p(n,k) b_{k-1}$$ Pour la démonstration, il suffit de remarquer que : $a_n p(n,k) = p(n+1,k) $.

    Première application : suite arithmético-géométrique : $u_{n+1} = a u_n+b$.
    On a : $p(n,k)=a^{n-k}$, d’où \begin{eqnarray*}
    u_n &= a^n u_0+ b \sum\limits_{k=1}^n a^{n-k} \\
    &=a^n u_0 + b \cdot \frac{1-a^n}{1-a} \\
    &= \frac{b}{1-a} + a^n \left( u_0 - \frac{b}{1-a} \right).
    \end{eqnarray*}
    Seconde application (celle du texte de G. Huvent) : $a_n = \dfrac{n+2}{2(n+1)} \ ;\ b_n=1$
    On vérifie que $p(n,k)=\dfrac{n+1}{2^{n+1}} \cdot \dfrac{2^{k+1}}{k+1}$. En tenant compte de $u_0=1$,
    La formule devient : $$ u_n = \sum_{k=0}^n p(n,k) = \frac{n+1}{2^{n+1}} \cdot \sum_{k=0}^n \frac{2^{k+1}}{k+1}$$
  • Hé ben voilà, il suffit de demander ! Merci, Alain !

    Borde.

    [ :) AD]
  • Merci beaucoup, Alain . C'est vrai que c'est plus joli comme ça.
    PS: Il me semble avoir déjà vu l'article d'Huvent ("G. Huvent de cette affaire").
  • "G. Huvent de cette affaire"..
    bien joué, RAJ...!!
  • C'est possible d'en avoir eu vent, l'article en question je l'avais déjà posté il y a quelques mois.
  • J'ai dû le lire à l'époque, Benoit.
  • C'est joli RAJ
    <BR>
    <BR>Je viens de le faire sur une feuille :
    <P></P><DIV ALIGN="CENTER" CLASS="mathdisplay"><IMG WIDTH="476" HEIGHT="66" ALIGN="MIDDLE" BORDER="0" SRC="http://www.les-mathematiques.net/phorum/2006/05/11/87397/cv/img1.png&quot; ALT="$\displaystyle \newline u_{n + 1} = a_n u_n + b_n \Rightarrow u_n = b_{n - 1} + ...... 0}^{n - 2} {b_{n - i - 2} } \prod\limits_{k = 0}^i {a_{n - 1 - k} }
    \newline $"></DIV><P></P>
    Bonnes journées à tous<BR>
Connectez-vous ou Inscrivez-vous pour répondre.