Question

مجموع زیر را بیابید: $$ \sum_{i=0}^{n-1} \sum_{j=i+1}^{n+1} \binom{n+1}{j} \binom{n}{i} $$

Answer 1

$$u_n=\sum_{i=0}^{n-1}\sum_{j=i+1}^{n+1} {n+1\choose j}{n\choose i}=\sum_{i=0}^{n-1}{n\choose i}\sum_{j=i+1}^{n+1} {n+1\choose j}$$

$$u_{n+1}=\sum_{i=0}^{n}\left[{n\choose i}+{n\choose i-1}\right]\sum_{j=i+1}^{n+2} \left[{n+1\choose j}+{n+1\choose j-1}\right]$$ $u_{n+1}=a_n+b_n+c_n+d_n$

$$a_n=\sum_{i=0}^{n}{n\choose i}\sum_{j=i+1}^{n+2} {n+1\choose j}=1+\sum_{i=0}^{n-1}{n\choose i}\sum_{j=i+1}^{n+1} {n+1\choose j}=1+u_n$$

$$b_n=\sum_{i=0}^{n}{n\choose i}\sum_{j=i+1}^{n+2} {n+1\choose j-1}=\sum_{i=0}^{n}{n\choose i}\sum_{j=i}^{n+1} {n+1\choose j}\\=\sum_{i=0}^{n}{n\choose i}{n+1\choose i}+\sum_{i=0}^{n}{n\choose i}\sum_{j=i+1}^{n+1} {n+1\choose j}\\=\sum_{i=0}^{n}{n\choose i}{n+1\choose i}+u_n+1$$ $$c_n=\sum_{i=0}^{n}{n\choose i-1}\sum_{j=i+1}^{n+2} {n+1\choose j}=\sum_{i=0}^{n-1}{n\choose i}\sum_{j=i+2}^{n+1} {n+1\choose j}\\=u_n-\sum_{i=0}^{n-1}{n\choose i}{n+1\choose i+1}$$ $$d_n=\sum_{i=0}^{n}{n\choose i-1}\sum_{j=i+1}^{n+2} {n+1\choose j-1}=\sum_{i=0}^{n-1}{n\choose i}\sum_{j=i+2}^{n+2} {n+1\choose j-1}\\=\sum_{i=0}^{n-1}{n\choose i}\sum_{j=i+1}^{n+1} {n+1\choose j}=u_n$$

,

$$u_{n+1}=4u_n+2+\sum_{i=0}^{n}{n\choose i}{n+1\choose i}-\sum_{i=0}^{n-1}{n\choose i}{n+1\choose i+1}\\=4u_n+3+\sum_{i=0}^{n}{n\choose i}{n+1\choose i}-\sum_{i=0}^{n}{n\choose i}{n+1\choose i+1}$$

Vandermonde's identity:

$$\sum_{i=0}^{n}{n\choose i}{n+1\choose i}=\sum_{i=0}^{n}{n\choose i}{n+1\choose i+1}={2n+1\choose n+1}$$

---

$u_{n+1}=4u_n+3$, $u_1=3$ ($u_0=0$ ). $u_n=4^n-1$.

Comments

آفرین! البته من یک راه حل دیگری داشتم اما این راه حل هم خیلی زیباست.

Answer 2

برای $i=0$

داریم$${n+1\choose1}+\dots+{n+1\choose n+1}=2^{n+1}-1$$

برای $n$ (فرد) $$2^{n+1}-1+2^{n+1}\frac{2^n-2}{2}=4^n-1$$ $n$ (زوج) $i$ $${n\choose n/2}\left({n+1\choose n/2+1}+\dots+{n+1\choose n+1}\right)=\frac{1}{2}{n\choose n/2}2^{n+1}$$

$$2^{n+1}-1+2^{n+1}\frac{2^n-2}{2}=4^n-1$$