Un prodotto di somme alterne con binomiali
Stavo provando averificare questa identità:
$$\sum_{j=1}^{r+1} (-1)^{r+1-j} \binom{d-j+1}{d-r} \sum_{l=1}^{d-k} (-1)^{l+1} \binom{d-k}{l} \binom{d-l+1}{j-1} = 1
$$
dove $r\leq k-1$ e $k \leq \lfloor d/2 \rfloor$
Ho iniziato riordinando i termini in questo modo:
$$(-1)^{r+1}\sum_{l=1}^{d-k} (-1)^{l+1} \binom{d-k}{l} \sum_{j=0}^{r+1} (-1)^{j} \binom{d-j+1}{d-r} \binom{d-l+1}{j-1}$$
quindi mi sono concentrato sulla sommatoria più interna $$\sum_{j=0}^{r+1} (-1)^{j} \binom{d-j+1}{d-r} \binom{d-l+1}{j-1}$$
poi ho provato a usare questa identità:
$$\sum_{j \leq a} (-1)^j \binom{a-j}{m} \binom{s}{j-n} = (-1)^{a+m} \binom{s-m-1}{a-m-n}
$$
dove $a=d+1$, $m=d-r$, $s=d-l+1$,$n=1$. Ho notato che posso ignorare i termini da $r+2$ to $d+2$ per via del primo binomiale che si annulla.
Quindi usando questa identità ottengo $$\binom{r-l}{r}$$ .
Il problema è che $l$ va da $1$ a $d-k$ quindi questo binomiale si annullerebbe per ogni valore di $l$.
Credo che il problema sia che non posso applicare questa identità, ma non capisco il perchè. Se qualcuno avesso un consiglio su come procedere sarebbe molto gradito. Grazie a chi risponderà.
$$\sum_{j=1}^{r+1} (-1)^{r+1-j} \binom{d-j+1}{d-r} \sum_{l=1}^{d-k} (-1)^{l+1} \binom{d-k}{l} \binom{d-l+1}{j-1} = 1
$$
dove $r\leq k-1$ e $k \leq \lfloor d/2 \rfloor$
Ho iniziato riordinando i termini in questo modo:
$$(-1)^{r+1}\sum_{l=1}^{d-k} (-1)^{l+1} \binom{d-k}{l} \sum_{j=0}^{r+1} (-1)^{j} \binom{d-j+1}{d-r} \binom{d-l+1}{j-1}$$
quindi mi sono concentrato sulla sommatoria più interna $$\sum_{j=0}^{r+1} (-1)^{j} \binom{d-j+1}{d-r} \binom{d-l+1}{j-1}$$
poi ho provato a usare questa identità:
$$\sum_{j \leq a} (-1)^j \binom{a-j}{m} \binom{s}{j-n} = (-1)^{a+m} \binom{s-m-1}{a-m-n}
$$
dove $a=d+1$, $m=d-r$, $s=d-l+1$,$n=1$. Ho notato che posso ignorare i termini da $r+2$ to $d+2$ per via del primo binomiale che si annulla.
Quindi usando questa identità ottengo $$\binom{r-l}{r}$$ .
Il problema è che $l$ va da $1$ a $d-k$ quindi questo binomiale si annullerebbe per ogni valore di $l$.
Credo che il problema sia che non posso applicare questa identità, ma non capisco il perchè. Se qualcuno avesso un consiglio su come procedere sarebbe molto gradito. Grazie a chi risponderà.
Risposte
Intanto... siamo sicuri al 100% che la formula dia sempre 1 come risultato ?
I parametri dei vari coeff. binomiali sono sempre corretti ? Vanno in negativo ?
I parametri dei vari coeff. binomiali sono sempre corretti ? Vanno in negativo ?
Da una semplice prova con Octave risulta questo, poi forse sbaglio qualcosa io...
d=3 k=2 r=1: 0
d=4 k=2 r=1: 1
d=4 k=3 r=1: 0
d=4 k=3 r=2: 0
d=5 k=2 r=1: 1
d=5 k=3 r=1: 1
d=5 k=3 r=2: 0
d=5 k=4 r=1: 0
d=5 k=4 r=2: 0
d=5 k=4 r=3: 0
d=6 k=2 r=1: 1
d=6 k=3 r=1: 1
d=6 k=3 r=2: 1
d=6 k=4 r=1: 1
d=6 k=4 r=2: 0
d=6 k=4 r=3: 0
d=6 k=5 r=1: 0
d=6 k=5 r=2: 0
d=6 k=5 r=3: 0
d=6 k=5 r=4: 0
d=7 k=2 r=1: 1
d=7 k=3 r=1: 1
d=7 k=3 r=2: 1
d=7 k=4 r=1: 1
d=7 k=4 r=2: 1
d=7 k=4 r=3: 0
d=7 k=5 r=1: 1
d=7 k=5 r=2: 0
d=7 k=5 r=3: 0
d=7 k=5 r=4: 0
d=7 k=6 r=1: 0
d=7 k=6 r=2: 0
d=7 k=6 r=3: 0
d=7 k=6 r=4: 0
d=7 k=6 r=5: 0
clear all
close all
for d = 1:7
for k = 1:(d-1)
for r = 1:(k-1)
assert(r <= k-1)
nr = r+1;
nc = d-k;
l = ones(nr, 1) * (1:nc);
j = (1:nr)' * ones(1, nc);
M = (-1).^(r+1-j) .* ...
bincoeff(d-j+1 , d-r) .* ...
(-1).^(l+1) .* ...
bincoeff(d-k, l) .* ...
bincoeff(d-l+1, j-1);
sum(M);
res = sum(sum(M));
printf("d=%d k=%d r=%d: %d\n", d, k, r, res);
endfor
endfor
endfor
"Quinzio":
Intanto... siamo sicuri al 100% che la formula dia sempre 1 come risultato ?
I parametri dei vari coeff. binomiali sono sempre corretti ? Vanno in negativo ?
In questo caso oltre a $0 \leq r \leq k-1$ so che $k \leq \lfloor d/2 \rfloor$ (grazie per avermelo ricordato, ora correggo anche la domanda). Per quanto riguarda l'identità che ho usato mi pare sia tutto ben definito dato che $a-j=d+1-j$ che è sempre strettamente positivo perchè alla peggio (cioè per $j=r+1$) fa $d-r$ che è positivo perchè appunto $r \leq k-1 \leq \lfloor d/2 \rfloor-1$; mentre $s=d-l+1$ che nel peggiore dei casi (cioè $l=d-k$) fa $k+1$. Ho il dubbio che ci sia da richiedere che $s \geq a$ ma nel libro "Concrete Mathematics" da cui ho preso tale identità non è specificato.
"Quinzio":
Da una semplice prova con Octave risulta questo, poi forse sbaglio qualcosa io...
d=3 k=2 r=1: 0 d=4 k=2 r=1: 1 d=4 k=3 r=1: 0 d=4 k=3 r=2: 0 d=5 k=2 r=1: 1 d=5 k=3 r=1: 1 d=5 k=3 r=2: 0 d=5 k=4 r=1: 0 d=5 k=4 r=2: 0 d=5 k=4 r=3: 0 d=6 k=2 r=1: 1 d=6 k=3 r=1: 1 d=6 k=3 r=2: 1 d=6 k=4 r=1: 1 d=6 k=4 r=2: 0 d=6 k=4 r=3: 0 d=6 k=5 r=1: 0 d=6 k=5 r=2: 0 d=6 k=5 r=3: 0 d=6 k=5 r=4: 0 d=7 k=2 r=1: 1 d=7 k=3 r=1: 1 d=7 k=3 r=2: 1 d=7 k=4 r=1: 1 d=7 k=4 r=2: 1 d=7 k=4 r=3: 0 d=7 k=5 r=1: 1 d=7 k=5 r=2: 0 d=7 k=5 r=3: 0 d=7 k=5 r=4: 0 d=7 k=6 r=1: 0 d=7 k=6 r=2: 0 d=7 k=6 r=3: 0 d=7 k=6 r=4: 0 d=7 k=6 r=5: 0 clear all close all for d = 1:7 for k = 1:(d-1) for r = 1:(k-1) assert(r <= k-1) nr = r+1; nc = d-k; l = ones(nr, 1) * (1:nc); j = (1:nr)' * ones(1, nc); M = (-1).^(r+1-j) .* ... bincoeff(d-j+1 , d-r) .* ... (-1).^(l+1) .* ... bincoeff(d-k, l) .* ... bincoeff(d-l+1, j-1); sum(M); res = sum(sum(M)); printf("d=%d k=%d r=%d: %d\n", d, k, r, res); endfor endfor endfor
Grazie per questa verifica, come ho scritto sopra non avevo specificato la condizione $k \leq \lfloor d/2 \rfloor$.
Mi scuso per essermi dimenticato. Effettivamente con la correzione $k \leq \lfloor d/2 \rfloor$ sembrerebbe fare sempre 1...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo