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]

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]

Le 26/04/2020 00:50, HB a écrit :
>>
>> 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 ?

> Quelques pistes, d'après mes premières constatations :
>
> 1°) on peut supposer g > 0 sinon ...

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

> 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.

> 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.

--
Olivier Miakinen

[Sottoc...@me.com]

On Sunday, 26 April 2020 02:50:14 UTC+4, HB wrote:
>
> 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]

Le 26/04/2020 à 08:20, Sottoc...@me.com a écrit :

> 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]

Le 26/04/2020 08:20, Sottoc...@me.com a écrit :
>
> 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...


--
Olivier Miakinen

[Olivier Miakinen]

Le 26/04/2020 13:53, HB a écrit :
>
> [...]

> 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.

> [...]

>
> 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.

> [...]

>
> 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.

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


--
Olivier Miakinen

[Sottoc...@me.com]

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

> 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

[Michel Talon]

Le 25/04/2020 à 13:51, NS a écrit :

et donc C(N-k,g)=0 pour N-k<0 donc en fait N-g <= k <= g ce qui suppose
g <= N <= 2g
>
> 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.


--
Michel Talon

[Olivier Miakinen]

Le 26/04/2020 15:07, Michel Talon a écrit :
>>
>> 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

> donc en fait N-g <= k <= g

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

> [...]

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).

--
Olivier Miakinen

[David Hilbert]

Bonjour,

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

NS

[HB]

Le 26/04/2020 à 15:07, Michel Talon a écrit :

>>
> 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.
>

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]

Le 25/04/2020 à 13:51, NS a écrit :

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]

Le 26/04/2020 à 15:33, Olivier Miakinen a écrit :
> Le 26/04/2020 15:07, Michel Talon a écrit :
>>>
>>> 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
>
>> 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.


--
Michel Talon

[Michel Talon]

Le 26/04/2020 à 17:40, serge bouc a écrit :
>
>    Sauf erreur ou omission, on peut procéder comme suit :

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


--
Michel Talon

[Sottoc...@me.com]

Oui ça marche !

Merci NS