اتحادهای ترکیبیاتی

$$\binom{n-1}{r-1} + \binom{n-1}{r} = \frac{(n-1)!}{(r-1)! (n-r)!} + \frac{(n-1)!}{r! (n-r-1)!} = \\ \frac{r (n-1)!}{r! (n-r)!} + \frac{(n-r) (n-1)!}{r! (n-r)!} = \frac{(n-r+r) (n-1)!}{r! (n-r)!} = \\ \frac{n!}{r! (n-r)!} = \binom{n}{r} $$

از اتحاد پاسکال داریم: $$\binom{n-1}{r-1} + \binom{n-1}{r} = \binom{n}{r}$$

بنابراین: $$\binom{n-1}{r-1} = \binom{n}{r} - \binom{n-1}{r} \Longrightarrow \binom{r}{k} = \binom{r+1}{k+1} - \binom{r}{k+1} \Longrightarrow \\ \sum \limits_{r=k}^{n} \binom{r}{k} = \sum \limits_{r=k}^{n} \binom{r+1}{k+1} - \binom{r}{k+1} = \\ -\binom{k}{k+1} + \binom{k+1}{k+1} - \binom{k+1}{k+1} + \binom{k+2}{k+1} - \binom{k+2}{k+1} + \binom{k+3}{k+1} - \ ... \\ - \binom{n}{k+1} + \binom{n+1}{k+1} = \binom{n+1}{k+1} - \binom{k}{k+1} = \binom{n+1}{k+1} - 0 = \binom{n+1}{k+1}$$

طبق اتحاد چوشی - چی: $$\sum \limits_{r=0}^{n} \binom{k+r}{k} = \sum \limits_{r=0}^{n} \binom{k+r}{r} = \sum \limits_{r=k}^{n+k} \binom{r}{k} = \binom{n+k+1}{k+1} = \binom{n+k+1}{n}$$

اثبات با دوگانه شماری:

مساله: مدرسه‌ای دو کلاس دارد. کلاس اول $m$ و کلاس دوم $n$ دانش‌آموز دارد. به چند طریق می‌توانیم از بین دانش‌آموزان این دو کلاس $k$ نفر را برای گروه سرود انتخاب کنیم؟

راه حل اول: اگر $i$ نفر از کلاس اول انتخاب شوند: به $\binom{m}{i}$ طریق این $i$ دانش‌آموز و به $\binom{n}{k-i}$ طریق $k-i$ نفر دیگر را از کلاس دوم انتخاب می‌کنیم. پس طبق اصل جمع،‌ جواب مساله برابراست با: $$\sum \limits_{i=0}^{k} \binom{m}{i} \binom{n}{k-i}$$

راه حل دوم: می‌خواهیم $k$ نفر از بین $n+m$ نفر انتخاب کنیم. تعداد راه‌های انجام این کار برابراست با:‌ $\binom{n+m}{k}$

پس: $$\sum \limits_{i=0}^{k} \binom{m}{i} \binom{n}{k-i} = \binom{n+m}{k}$$

در اتحاد واندرموند اگر قرار دهیم $n = m = k$: $$\sum \limits_{i=0}^{k} \binom{m}{i} \binom{n}{k-i} = \binom{n+m}{k} \Longrightarrow \sum \limits_{i=0}^{k} \binom{n}{i} \binom{n}{i} = \binom{2n}{n}$$