Somme de coefficients binomiaux

[NS]

Bonjour,

comment peut-on démontrer que

Sigma (-1)^k C(g,k) C(N-k,g) = 1

où k = 0..g?

On assume que g <= N et que les coefficient binomiaux qui ne sont pas définis sont égaux à 0.

Merci.

[HB]

Post by NS
Bonjour,
comment peut-on démontrer que
Sigma (-1)^k C(g,k) C(N-k,g) = 1
où k = 0..g?
On assume que g <= N et que les coefficient binomiaux qui ne sont pas définis sont égaux à 0.
Merci.

Cela ressemble furieusement à un exo de prépa ...

Quelques pistes, d'après mes premières constatations :

1°) on peut supposer g > 0 sinon ...

2°) le cas g = n peut être traité à part ...

3°) pour les cas restants, on peut séparer en 3 cas
a) g< n < 2g
b) n= 2g
c) c > 2g

Cordialement,

HB

[Olivier Miakinen]

Post by HB

Post by NS
comment peut-on démontrer que
Sigma (-1)^k C(g,k) C(N-k,g) = 1
où k = 0..g?
On assume que g <= N et que les coefficient binomiaux qui ne sont pas définis sont égaux à 0.

Cela ressemble furieusement à un exo de prépa ...

Tu veux dire que ç'aurait été plus en charte dans fr.education.entraide.maths ?

Post by HB
1°) on peut supposer g > 0 sinon ...

... sinon c'est trivialement vrai : (-1)^0 C(0,0) C(N,0) = 1

Post by HB
2°) le cas g = n peut être traité à part ...

Car c'est tout aussi trivialement vrai : (-1)^0 C(N,0) C(N,N) = 1.

Post by HB
3°) pour les cas restants, on peut séparer en 3 cas
a) g< n < 2g
b) n= 2g
c) c > 2g

En tout cas, sur quelques exemples que j'ai tentés, ça m'a toujours
semblé exact. Mais il doit bien y avoir une explication simple, non ?
Parce que les calculs peuvent nous prouver que c'est vrai, mais en
général on aime bien avoir une explication qui nous éclaire sur la
signification profonde du résultat.

[S***@me.com]

Post by HB
Cela ressemble furieusement à un exo de prépa ...

Bonjour, ca n’a rien à voir avec un exo de prepa :)

Je suis en train d’étudier un problème avec des polynômes et cette propriété apparaît après un changement de coordonnées.

Les deux premiers points de ton message sont faciles. Ce qui ne l’est pas est le cas g <= N/2 (ou g >= N/2).

J’ai essayé de le prouver par récurrence sur N mais je n’y arrive pas...

NS

[HB]

Post by S***@me.com
Je suis en train d’étudier un problème avec des polynômes
et cette propriété apparaît après un changement de coordonnées.

Bonjour,

1°) La séparation des cas (signe de n - 2g)
est imposée par maxima lorsque l'on demande
une simplification avec simplify_sum.
J'imagine que ce n'est pas sans raison.
C'est pour cela que j'ai parlé de
"premières constatations".

2°) En fait, ce type de pb se traite très souvent
en utilisant des polynômes puis en considérant
des valeurs particulières de X (réelles ou complexes)
ou en recherchant le coef d'un terme particulier.
De plus, une somme de produits peut souvent
se transformer en produit de sommes...
Ce type de ruse est fréquente dans les exos de prépas.
D'où ma remarque ...

Plus rarement, des considérations ensemblistes
liées aux dénombrements s'avèrent fécondes.
Dans ce cas, cette piste me semble moins évidente !
(c'est peut-être lié à mon goût personnel)

Le pb avec ces méthodes,
c'est que celui qui n'a pas eu
la "bonne inspiration", l'intuition adaptée,
considèrera plus la preuve comme un tour de magie
que comme une "explication"...

Pour une preuve par récurrence :
Ici, il y a 2 paramètres : n et g ...
Il y a donc plusieurs méthodes envisageables.

Donc :
Pourrait-on savoir de quels polynômes il s'agit ?

On peut peut-être y puiser une "source d'inspiration"
voire une piste pour étudier le pb initial
sous un autre l'angle.


Bien cordialement,

HB

[Olivier Miakinen]

Post by HB
[...]
De plus, une somme de produits peut souvent
se transformer en produit de sommes...

Oui, et ce changement de point de vue peut être très fécond.

Post by HB
[...]
Le pb avec ces méthodes,
c'est que celui qui n'a pas eu
la "bonne inspiration", l'intuition adaptée,
considèrera plus la preuve comme un tour de magie
que comme une "explication"...

En effet.

Post by HB
[...]
Pourrait-on savoir de quels polynômes il s'agit ?
On peut peut-être y puiser une "source d'inspiration"
voire une piste pour étudier le pb initial
sous un autre l'angle.

Ah, nous sommes bien d'accord. ;-)

[S***@me.com]

On Sunday, 26 April 2020 15:53:45 UTC+4, HB wrote>

Post by HB
Pourrait-on savoir de quels polynômes il s'agit ?

Voici mon problème :

On considère cette famille de polynômes homogènes de dégrée n (n > 2):

p_n(x,y) = Sigma 2^(n-2k) C(n-k,k) x^(2k) y^(n-2k)

où k varie entre 0 et [n/2].

On introduit les coordonnées X et Y:

x = sqrt(-XY)
y = (X+Y)/2

Démontrer que le polynôme p, dans les nouvelle coordonnées, s'écrit

P(X,Y) = ( X^(n+1) - Y^(n+1) ) / (X-Y).

NS

[Olivier Miakinen]

Post by S***@me.com
Je suis en train d’étudier un problème avec des polynômes et cette propriété apparaît après un changement de coordonnées.

Du coup, connaître le problème d'origine pourrait peut-être nous aider à
trouver une explication simple et non pas tirée du chapeau...

[Michel Talon]

Post by NS
Bonjour,
comment peut-on démontrer que
Sigma (-1)^k C(g,k) C(N-k,g) = 1
où k = 0..g?
On assume que g <= N et que les coefficient binomiaux qui ne sont pas définis sont égaux à 0.

et donc C(N-k,g)=0 pour N-k<0 donc en fait N-g <= k <= g ce qui suppose
g <= N <= 2g

Post by NS
Merci.

La propriété semble fausse. Par exemple avec N=5 et g=4 maxima nous donne:
(%i11) makelist((-1)^k*binomial(g,k)*binomial(g,N-k),k,N-g,g);
(%o11) [- 4, 24, - 24, 4]
ce que j'ai vérifié et la somme vaut donc 0. J'ai fait d'autres essais
qui ne donnent jamais 1.

[Olivier Miakinen]

Post by Michel Talon

Post by NS
comment peut-on démontrer que
Sigma (-1)^k C(g,k) C(N-k,g) = 1
où k = 0..g?
On assume que g <= N et que les coefficient binomiaux qui ne sont pas définis sont égaux à 0.

et donc C(N-k,g)=0 pour N-k<0

Plutôt pour N-k < g

Post by Michel Talon
donc en fait N-g <= k <= g

Plutôt 0 <= k <= min(g, N-g)

Post by Michel Talon
[...]

Je n'ai pas vérifié le reste, mais si tu fais varier k de N-g à g c'est normal
que tu ne trouves pas le même résultat qu'entre 0 et min(g, N-g).

[Michel Talon]

Post by Olivier Miakinen

Post by Michel Talon

Post by NS
comment peut-on démontrer que
Sigma (-1)^k C(g,k) C(N-k,g) = 1
où k = 0..g?
On assume que g <= N et que les coefficient binomiaux qui ne sont pas définis sont égaux à 0.

et donc C(N-k,g)=0 pour N-k<0

Plutôt pour N-k < g

Post by Michel Talon
donc en fait N-g <= k <= g

Plutôt 0 <= k <= min(g, N-g)

Je vois, pour moi, C(N-k,g) signifiait C^(N-k)_g alors que c'était le
contraire. D'ailleurs C(g,k) est bien C_g^k, donc l'erreur était
impossible. Evidemment le reste souffre de la même erreur.

[David Hilbert]

Bonjour,

nous avons 5 - 4 = 1 (apres les deux premieres terms tous les autres
sont nuls).

NS

[HB]

Post by Michel Talon
(%i11) makelist((-1)^k*binomial(g,k)*binomial(g,N-k),k,N-g,g);
(%o11)                        [- 4, 24, - 24, 4]
ce que j'ai vérifié et la somme vaut donc 0. J'ai fait d'autres essais
qui ne donnent jamais 1.

Cette liste ne me semble pas correspondre à la somme
qui était donnée :

"Sigma (-1)^k C(g,k) C(N-k,g)"

===============================================================
J'avais remplacé g par p ... question de traditions ;o)
Avec maxima (aussi) j'ai obtenu :

==============================================
(%i8)
load(functs);load(simplify_sum);declare(n,integer);declare(p,integer);declare(k,integer);assume(k<n);assume(n>p);assume(p>0);
(%o1) "C:/maxima-5.43.2/share/maxima/5.43.2/share/simplification/functs.mac"

(%o2)
"C:/maxima-5.43.2/share/maxima/5.43.2/share/solve_rec/simplify_sum.mac"

(%o3) done

(%o4) done

(%o5) done

(%o6) [n>k]

(%o7) [n>p]

(%o8) [p>0]

(%i9) R:sum((-1)^k*combination(p,k)*combination(n-k,p),k,0,p);
(R) sum((\-1)^k*binomial(n\-k,p)*binomial(p,k),k,0,p)
(%i10) simplify_sum(R);
"Is "2*p\-n" positive, negative or zero?"p;
(%o10) 1

(%i11) simplify_sum(R);
"Is "2*p\-n" positive, negative or zero?"n;
(%o11) 1

(%i13) S:subst(2*p,n,R);simplify_sum(S);
(S) sum((\-1)^k*binomial(p,k)*binomial(2*p\-k,p),k,0,p)
(%o13) 1
===============================================================

Donc

avec 0<= k < n et 0 < p < n

R est défini par
sum((-1)^k*combination(p,k)*combination(n-k,p),k,0,p)

Quand je demande la simplification avec simplify_sum,
Maxima demande le signe de 2p - n pour continuer...

mais, finalement, cela donne toujours R = 1

Cordialement,

HB

[serge bouc]

Post by NS
Bonjour,
comment peut-on démontrer que
Sigma (-1)^k C(g,k) C(N-k,g) = 1
où k = 0..g?
On assume que g <= N et que les coefficient binomiaux qui ne sont pas définis sont égaux à 0.
Merci.

Bonjour,

Sauf erreur ou omission, on peut procéder comme suit :

Soit S(n,g) = Sigma_k (-1)^k C(g,k) C(n-k,g) la somme demandée,
où l'on a changé N en n pour des raisons esthétiques... ;-)

En utilisant le fait que C(n+1-k,g) = C(n-k,g) + C(n-k,g-1), on voit que
S(n+1,g) = S(n,g) + Sigma_k (-1)^k C(g,k) C(n-k,g-1)

On utilise alors le fait que C(g,k) = C(g-1,k) + C(g-1,k-1), et l'on
trouve
S(n+1,g) = S(n,g) + S(n,g-1) + Sigma_k(-1)^kC(g-1,k-1) C(n-k,g-1)

En changeant k en k-1 dans cette dernière somme, on a
S(n+1,g) = S(n,g) + S(n,g-1) - S(n-1,g-1)

et on gagne par récurrence, puisque 1 + 1 - 1 = 1

[Michel Talon]

Bravo. Avec les C(n,p) dans le bon sens :( maxima est assez savant
lui aussi:

(%i16) sum((-1)^k*binomial(g,k)*binomial(N-k,g),k,0,min(g,N-g));
min(g, N - g)
====
\ k
(%o16) > binomial(g, k) binomial(N - k, g) (- 1)
/
====
k = 0
(%i17) simplify_sum(%);

Is 2 g - N positive, negative or zero?

n;
Is g - N positive, negative or zero?

n;
(%o17) 1

[S***@me.com]

Oui ça marche !

Merci NS

Post by NS
Bonjour,
Soit S(n,g) = Sigma_k (-1)^k C(g,k) C(n-k,g) la somme demandée,
où l'on a changé N en n pour des raisons esthétiques... ;-)
En utilisant le fait que C(n+1-k,g) = C(n-k,g) + C(n-k,g-1), on voit que
S(n+1,g) = S(n,g) + Sigma_k (-1)^k C(g,k) C(n-k,g-1)
On utilise alors le fait que C(g,k) = C(g-1,k) + C(g-1,k-1), et l'on
trouve
S(n+1,g) = S(n,g) + S(n,g-1) + Sigma_k(-1)^kC(g-1,k-1) C(n-k,g-1)
En changeant k en k-1 dans cette dernière somme, on a
S(n+1,g) = S(n,g) + S(n,g-1) - S(n-1,g-1)
et on gagne par récurrence, puisque 1 + 1 - 1 = 1