Somma dei prodotti dei coefficienti binomiali divisa per l'indice

Question

Ho problemi a trovare una forma più compatta per le serie seguenti.

$$\sum_{i=j}^{n}\left(\begin{array}{c}n \\ i\end{array}\right)\left(\begin{array}{c}i \\ j\end{array}\right) \frac{(-1)^{i+j}}{i}, \quad n\ge 1, j\le n-1.$$

$j$può essere considerato come una costante. Penso di aver visto qualcosa di simile prima, ma non sono sicuro se sia possibile semplificare ulteriormente la somma. Tutti i suggerimenti notevolmente sono apprezzati.

Answer 1

Nota che

$$j\sum_{i=j}^n\binom{n}i\binom{i}j\frac{(-1)^{i+j}}i=\sum_{i=j}^n(-1)^{i-j}\binom{n}i\binom{i-1}{j-1}\,,$$

quindi è sufficiente dimostrarlo

$$\sum_{i=j}^n(-1)^{i-j}\binom{n}i\binom{i-1}{j-1}=1\,.\tag{1}$$

Per $j\le i\le n$ ci sono $\binom{n}i\binom{i-1}{j-1}$ coppie $\langle S,T\rangle$ di sottoinsiemi di $[n]$ tale che $T\subseteq S$, $|S|=i$, $|T|=j$, e $\max T=\max S$. Quante volte nette fa un dato$T$ vengono contati sul lato sinistro di $(1)$?

Permettere $T$ essere un $j$-sottoinsieme di $[n]$ con $\max T=m\ge j$. Per$i=j,\ldots,m$ ci sono $\binom{m-j}{i-j}$ $i$-sottoinsiemi $S$ di $[n]$ tale che $m=\max S$, così $T$ viene contato

$$\sum_{i=j}^m(-1)^{i-j}\binom{m-j}{i-j}=\sum_{\ell=0}^{m-j}(-1)^\ell\binom{m-j}\ell=\begin{cases} 0,&\text{if }m>j\\ 1,&\text{if }m=j \end{cases}$$

volte e $(1)$ segue immediatamente.

Answer 2

Vogliamo dimostrarlo $$\sum_{i=j}^n\binom{n}{i}\binom{i}{j} \frac{(-1)^{i+j}}{i} = \frac{1}{j},$$ equivalentemente, $$\sum_{i=j}^n\binom{n}{i}\binom{i-1}{j-1} (-1)^{i+j} = 1. \tag1$$ Applicare olio di serpente: \begin{align} &\sum_{j=1}^n \sum_{i=j}^n\binom{n}{i}\binom{i-1}{j-1} (-1)^{i+j} z^j \\ &= \sum_{i=1}^n \binom{n}{i}(-1)^i \sum_{j=1}^i\binom{i-1}{j-1} (-z)^j \\ &= \sum_{i=1}^n \binom{n}{i}(-1)^i (-z)(1-z)^{i-1} &&\text{(binomial theorem)}\\ &= \frac{z}{1-z}\sum_{i=1}^n \binom{n}{i} (1-z)^i &&\\ &= \frac{z}{1-z} (z^n-1) &&\text{(binomial theorem)}\\ &= \sum_{j=1}^n z^j&&\text{(finite geometric series)} \end{align} che immediatamente implica $(1)$ estraendo il coefficiente di $z^j$.

Answer 3

Supponiamo che ci interessi

$$S_{n, q} = \sum_{p=q}^n {n\choose p} {p\choose q} \frac{(-1)^{p+q}}{p}$$

lo osserviamo

$${n\choose p} {p\choose q} = \frac{n!}{(n-p)! \times q! \times (p-q)!} = {n\choose q} {n-q\choose n-p}$$

così otteniamo

$${n\choose q} \sum_{p=q}^n {n-q\choose n-p} \frac{(-1)^{p+q}}{p} = {n\choose q} \sum_{p=0}^{n-q} {n-q\choose n-q-p} \frac{(-1)^{p}}{p+q} \\ = {n\choose q} \sum_{p=0}^{n-q} {n-q\choose p} \frac{(-1)^{n-q-p}}{n-p}.$$

Cerchiamo di valutare la somma intermedia

$$T_{n,q} = \sum_{p=0}^{n-q} {n-q\choose p} \frac{(-1)^{p}}{n-p}.$$

Con questo in mente vi presentiamo

$$f(z) = \frac{(n-q)! \times (-1)^{n-q}}{n-z} \prod_{r=0}^{n-q} \frac{1}{z-r}.$$

Questo ha la proprietà che per $0\le p\le n-q$ noi abbiamo

$$\mathrm{Res}_{z=p} f(z) = \frac{(n-q)! \times (-1)^{n-q}}{n-p} \prod_{r=0}^{p-1} \frac{1}{p-r} \prod_{r=p+1}^{n-q} \frac{1}{p-r} \\ = \frac{(n-q)! \times (-1)^{n-q}}{n-p} \frac{1}{p!} \frac{(-1)^{n-q-p}}{(n-q-p)!} = {n-q\choose p} \frac{(-1)^p}{n-p}$$

così che

$$T_{n,q} = \sum_{p=0}^{n-q} \mathrm{Res}_{z=p} f(z).$$

Ora i residui si sommano a zero e il residuo all'infinito è zero per ispezione quindi

$$T_{n,q} = - \mathrm{Res}_{z=n} f(z) = (n-q)! (-1)^{n-q} \prod_{r=0}^{n-q} \frac{1}{n-r} \\ = (n-q)! (-1)^{n-q} \frac{(q-1)!}{n!} = (-1)^{n-q} \frac{1}{q} {n\choose q}^{-1}.$$

Otteniamo così

$$S_{n,q} = {n\choose q} (-1)^{n-q} (-1)^{n-q} {n\choose q}^{-1} \frac{1}{q}.$$

Questo semplifica a

$$\bbox[5px,border:2px solid #00A000]{ S_{n,q} = \frac{1}{q}.}$$

Answer 4

Pubblicherò solo un altro metodo fattibile per dimostrare questa identità.

È semplice dimostrarlo $$ {{i+j}\choose{j}}{{n}\choose{i+j}}= {{n}\choose{j}}{{n-j}\choose{i}}. \tag1 $$ Dalla definizione della funzione ipergeometrica, abbiamo $$ _2F_1(j-n,j;j+1;z) =\sum_{i=0}^{n-j}(-1)^i {{n-j}\choose{i}} \frac{j}{j+i}z^i\quad \tag2$$ da $j<n$.

Combinando (1) e (2), è immediato quello $$ \sum_{i=j}^n (-z)^i {{i}\choose{j}}{{n}\choose{i}}\frac{1}{i} = \frac{(-z)^j}{j}{{n}\choose{j}}{}_2F_1(j-n,j;j+1;z).$$

Permettere $z=1$, quindi dal teorema di Gauss, si può semplificare la funzione ipergeometrica e ottenere lo stesso risultato mostrato in altre soluzioni.