Mathématiques - une formule

une formule
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: aviateurpilot

je voulais montrer un exo et j'ai trouvé cette formule apres un petit calcule:

$6$\fbox{\2^{n-1}\bigsum_{j=i}^{n-1}\frac{C_{j}^{i}}{2^j}=\bigsum_{j=i}^{n-1}C_{n}^{j+1}}$

d'apres mon calcule je suis sure que ces vrai
il se peut que cette formule est dans le cour
sinon, c'est un jolie resultat

Posted by: nekros

Bonne chance pour la montrer

Thomas G

Posted by: Chimomo

Jolie formule en effet , peut tu nous donner ta démo (ou une idée si elle est trop compliquée).

Posted by: nekros

Salut Chimomo,

En fait, cette formule est apparue dans l'exo que j'ai proposé ici : http://maths-forum.com/showthread.php?t=16933

Juste si tu veux suivre le sujet

Thomas G

Posted by: Chimomo

Ok merci, je vais voir si j'ai le temps.

Posted by: aviateurpilot

j'ai pas encore demontré cette formule
mais voila ce que je vais utilisé
$5$\fbox{C_{n}^{j+1}=\bigsum_{t=0}^jC_{j}^{t}C_{n-j}^{j+1-t}}$ (*)
c'est un autre resultat que j'ai trouvé en utilisant le triangle de pascal
mais puisque je suis encore en terminal alors il se peut que j'ai fait une faut dans (*)
sinon c'est un autre jolie resultat

Posted by: aviateurpilot

on pose $3$\ U_i=2^{n-1}\bigsum_{j=i}^{n-1}\frac{C_{j}^{i}}{2^j}=\bigsum_{j=i}^{n-1}2^{n-1-j}C_{j}^{i}$ $(i\le n-1)$

$(m\le n-1)$
$3$\bigsum_{t=0}^mU_t=[\bigsum_{t=0}^m\bigsum_{j=t}^{n-1}2^{n-1-j}C_{j}^{t}]=[\bigsum_{j=m+1}^{n-1}2^{n-1-j}(\bigsum_{t=0}^mC_{j}^{t})]+[\bigsum_{j=0}^{m}2^{n-1-j}(\bigsum_{t=0}^jC_{j}^{t})]=[\bigsum_{j=m+1}^{n-1}2^{n-1-j}(2^j-\bigsum_{t=m+1}^jC_{j}^{t})]+(m+1)2^{n-1}$
donc
$3$\fbox{A_m=\bigsum_{t=0}^mU_t=n2^{n-1}-[\bigsum_{j=(m+1)}^{n-1}\bigsum_{t=(m+1)}^j2^{n-1-j}C_{j}^{t}]}$
pas encore terminer

je vais chercher ce probleme tt seul

mais c'est pas grave

Posted by: aviateurpilot

maintenant
on pose $\fbox{W_i=\bigsum_{j=i}^{n-1}C_{n}^{j+1}}$
$2$\fbox{\bigsum_{t=0}^mW_t=\bigsum_{t=0}^m\bigsum_ {j=t+1}^{n}C_{n}^{j}=(m+1)2^n-\bigsum_{t=0}^m\bigsum_{j=0}^{t}C_{n}^{j}}$

Posted by: aviateurpilot

je voi qu'il n y a personne qui veut m'aider
sinon qu'il n y a personne qui peut m'aider

Posted by: Yipee

la formule * (que je préfère ne pas écrire) est vraie et classique. C'est la formule de Vandermonde. Il y a une interprétation combinatoire très simple. On considère une urne avec n boules dont j noires (et n-j blanches) et on dénombre le nombre de manières d'en prendre j+1. Le nombre t désigne alors le nombre de boules noires du tirage.

On peut aussi le faire en développant les coefficients binomiaux.

Posted by: aviateurpilot

tu parle de la formule du poste 6
c'est tres simple je l'ai trouvé en utilisant le triangle de pascal dans 5min
mais moi je parle de la formule du poste 1

Posted by: Bouchra

Salut,
je crois avoir trouvé une démonstration pour la formule de ton 1er message.

On pose: pour $0 \leq i \leq n-1$
$4$ A(n,i) = \Bigsum_{j=i}^{n-1} 2^{n-1-j} C_{j}^{i}$ et
$4$ B(n,i) = \Bigsum_{j=i}^{n-1}C_{n}^{j+1}$

On remarque que les deux suites A(n,i) et B(n,i) vérifient la relation:
$4$ u(n,i) = u(n-1,i-1) + u(n-1,i) \ \ (*)$

Démonstration : facile en utilisant des changements d'indice et la relation : $C_{n}^{p} + C_{n}^{p+1} = C_{n+1}^{p+1}$

De plus:
A(n,n-1) = B(n,n-1) = 1 et
A(n,0) = B(n,0) = 2^n-1

Or d'après la relation (*) que vérifient les deux suites, on en déduit que: A(n,i) = B(n,i),
car tout A(n,i) peut s'écrire comme somme de A(k,k-1) et de A(m,0) .

Une illustration :
$4$\begin{array}{ccccc} u(1,0) & u(2,0) & u(3,0)& u(4,0)& \ldots\\ & u(2,1) & u(3,1)& u(4,1) & \ldots \\ & & u(3,2)&u(4,2) & \ldots\\ & & & \ddots \\ \end{array}$

par exemple :
A(5,2) = A(4,1) + A(4,2)
= A(3,0) + A(3,1) + A(3,1) + A(3,2)
= A(3,0) +2( A(2,0) + A(2,1)) + A(3,2)
= ...
= B(5,2).

Voilà, j'éspère ne pas avoir dit de bêtises.

Posted by: aviateurpilot

$B(n-1,i)+B(n-1,i-1)=C_{i-1}^{i-1}\bigsum_{j=i}^{n-2}C_{j+1}^{i}+C_{j+1}^{i-1}=1+\bigsum{j=i}^{n-2}C_{j+2}^{i}=1+\bigsum_{j=i+1}^{n-1}C_{j+1}^{n-1}=1+B(n,i)-C_{i}^{i}=B(n,i)$
donc $(*)$ est vrai pour $B(n,i)$
sans verifie pour $A(n,i)$ je suis sure que c'est vraie car je suis sure que ma formule $4$\fbox{A(n,i)=B(n,i)}$ est vraie
par la meme façon que j'ai fait pour trouvé $4$\fbox{C_{n}^{j+1}=\bigsum_{t=0}^jC_{j}^{t}C_{n-j}^{j+1-t}}$ en utilisant le triangle de pascal car C(n,j+1) verifie $(*)$
si on place les $U(n,i)$ commes les $C_{n}^{i}$ sous forme d'un triangle comme celui de pascale et ce ce que tu as fait bouchra dans ton Une illustration
on trouve que $4$\fbox{U(n,i)=\bigsum_{t=0}^{i-1}C_{i-1}^{t}U(n-i+1,i-t)$
et c'est ce que tu va trouvé a la fait de

Citation:

Posté par Bouchra

par exemple :
A(5,2) = A(4,1) + A(4,2)
= A(3,0) + A(3,1) + A(3,1) + A(3,2)
= A(3,0) +2( A(2,0) + A(2,1)) + A(3,2)
= ...
=...........

mais pas forcement $B(5,2)$
sauf si tu fait les calcule d'une autre façon.

Posted by: Yipee

Je n'ai pas eu le temps - ni le courage - de lire tous vos calculs. Voici la méthode que je propose. L'idée est de faire varier i dans la formule. On commence par montrer que c'est vrai pour i = n-1 ce qui est évident. Ensuite on "descend" en montrant, à l'aide du triangle de Pascal que si c'est vrai pour un i donné, c'est encore vrai pour i-1. Les calculs sont assez directs (mais long à taper)

Posted by: aviateurpilot

impossible de faire ça !!

Posted by: aviateurpilot

http://www.maths-forum.com/showthread.php?t=16933

Posted by: Bouchra

Citation:

mais pas forcement $B(5,2)$

Si si, car:
B(n,i) vérifie la relation (*), donc:
B(5,2) = B(4,1) + B(4,2)
= B(3,0) + B(3,1) + B(3,1) + B(3,2)
= B(3,0) +2( B(2,0) + B(2,1)) + B(3,2)

Et on a monté que B(n,0) = A(n,0) et B(n,n-1) = A(n,n-1), d'où le résultat.

L'idée en gros, pour calculer A(n,i) c'est de se rammener à la somme de A(k,k-1) et de A(m,0) (on peut toujours d'après la formule (*) et on le voit facilement à partir de l'illustration) qui est égale à la somme des B(k,k-1) et de B(m,0), qui est égale à B(n,i) (toujours à partir de la formule (*)) .

Posted by: Yipee

Citation:

Posté par aviateurpilot

impossible de faire ça !!

Je ne comprends pas

Posted by: aviateurpilot

impossible pour moi
car j'ai essayé
mais pour toi peut etre que tu arrive
assaye alors

Posted by: nekros

On finira bien par trouver car :

En essayant continuellement, on finit par réussir. Donc plus ça rate, plus on a de chances que ça marche.

Thomas G

Posted by: aviateurpilot

je vais faire tes calcule bouchra pour verifie "ok"
voila ce que tu as fait
$4$\fbox{A(n,i)=\bigsum_{t=0}^{j}C_{j}^{t}A(n-j,i-t)$ quelque soit $0\le j\le i$
pour j=i
$2$\fbox{A(n,i)=\bigsum_{t=0}^{i}C_{i}^{t}A(n-i,i-t)=A(n-i,0)+\bigsum_{t=0}^{i-1}C_{i}^{t}A(n-i,i-t)$
et on fait la meme chose avec les $A(n-i,i-t)$ pour trouve quelque chose de la forme A(m,0)+une autre somme, ........etc
jusqu'à ce qu'on trouve $A(n,i)$ en fonction des $A(m,0)$
or on a les $A(m,0)$ = les $B(m,0)$
et avec ces $B(m,0)$ on costruit $B(n,i)$
je voulais faire ça en calcule mais c'est tres long
mais si quelqu'un autre peut et veut le faire ( bienvenu )
moi je n'ai que les instrument du terminal et je ne peus pas faire grand chose là

Posted by: Yipee

Je vais essayer de trouver un peu de temps cet après-midi pour vérifier et taper ma solution.

Posted by: Yipee

Nous voulons donc montrer que, pour tout entier n non nul et tout entier i compris entre 0 et n-1 on a
$2^{n-1} \sum_{j=i}^{n-1} \frac{1}{2^j}C_j^i = \sum_{j=i}^{n-1} C_n^{j+1}$

Soit n un entier fixé (non nul), on remarque que pour i=n-1 l'égalité devient :
$2^{n-1} \frac{1}{2^{n-1}}C_{n-1}^{n-1} = C_n^{n} = 1$

C'est donc vrai.

Nous allons alors procéder à une "récurrence en descendant" (pour les puristes il suffit de considérer le plus grand entier i tel que l'égalité soit fausse). Nous allons donc supposer que l'égalité est vraie pour un entier i fixé et nous allons le démontrer pour i-1.

On a d'après le triangle de Pascal que
$C_j^{i-1} = C_{j+1}^i - C_j^i$
D'où :
$2^{n-1} \sum_{j=i-1}^{n-1} \frac{1}{2^j}C_j^{i-1} = 2^{n-1}\left( \sum_{j=i-1}^{n-1} \frac{1}{2^j}C_{j+1}^{i} - \sum_{j=i-1}^{n-1} \frac{1}{2^j}C_{j}^{i} \right) = 2^{n-1}\left( \sum_{j=i}^{n} \frac{1}{2^{j-1}}C_{j}^{i} - \sum_{j=i}^{n-1} \frac{1}{2^j}C_{j}^{i} \right)$

Le dernier terme est égal en utilisant la relation de "récurrence" à

$2\sum_{j=i}^{n-1} C_n^{j+1} + 2^{n-1}\times\frac{1}{2^{n-1}}C_n^i - \sum_{j=i}^{n-1} C_n^{j+1}\right = \sum_{j=i}^{n-1} C_n^{j+1} + C_n^i = \sum_{j=i-1}^{n-1} C_n^{j+1}$

Posted by: Bouchra

Salut Yipee, j'ai des petits doutes sur cette réccurence mais peut-être je me trompe.

Comment tu fais le passage par exemple de A(n,n-1) à A(n,n-2) (puisque c'est une récurrence décendante)? Tu utilises en fait le fait que A(n,n-2) = A(n+1,n-1) - A(n,n-1) (ton avant dernière égalité avec mes notations) et tu dis que A(n,n-1) =B(n,n-1) (d'accord) et que A(n+1,n-1) = B(n+1,n-1) (alors qu'on n'en sait rien) , c'est ce qu'on veut montrer. Ca me semble bizarre .

EDIT :
En plus avec ta méthode, on peut montrer que $A(n,i) =\Bigsum_{j=i}^{n-1} C_{n}^{j+1} = C_{n}^{i+1}$ :
C'est vrai pour i=n-1, puis si c'est vrai pour i $A(n,i-1) = A(n+1,i) - A(n,i) = C_{n+1}^{i+1} - C_{n}^{i+1} = C_{n}^{i}.$ donc c'est vrai pour i-1 .

Et on sait bien que ce résultat est faux, i=2 et n=4 par ex.

Posted by: Yipee

Non, non, non. Relis la démonstration et tu verras que j'utilise la relation à n fixé (j'enlève le terme pour j=n dans la première somme pour le traiter à part).

Posted by: Bouchra

Ah oui, désolée j'avais mal lu la fin .

Je ferai plus attention la prochaine fois .

Posted by: mathématicien arabe

bonsoir. JE crois que tous ces formules que vous venez de discuter peuvent étre facilement étre interprétées de facon probabilistique ( pour eviter les calculs pénibles) . j ai ben voulu vou expliker comment mais dommage que je ne sais pas comment écrire ces trucs de signe par clavier. Si Vous permettez essayer de me guider car sui encore faible dans ces trucs la.

MERCI

Posted by: nekros

Salut,

Pour les signes mathématiques, tu peux aller voir ici

N'oublie pas les balises [TEX] autour de tes formules.

Thomas G

Posted by: aviateurpilot

montrer nous ce que tu veus dire alors mathématicien arabe