范德蒙德卷積 學習筆記
直接放結論，反正我也不會證。
\[\sum_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i}=\dbinom{n+m}{k}
\]
\]
下面有幾個推論，可以稍微不那麼嚴謹的證明一下。
首先你要知道的是這個東西：
\[\dbinom{m}{i}=\dbinom{m}{m-i}
\]
\]
感性理解一下就是楊輝三角的對稱性，其實直接拆式子也不是什麼難事。
下面來看幾個推論：
推論一
\[\sum_{i=1}^{n}\dbinom{n}{i}\dbinom{n}{i-1}=\dbinom{2n}{n+1}
\]
\]
關於證明，我們可以把 \(\binom{n}{i-1}\) 轉化成為 \(\binom{n}{n-i+1}\) 。
然後原式變成
\[\sum_{i=1}^{n}\dbinom{n}{i}\dbinom{n}{n-i+1}
\]
\]
直接套用公式就可以了。
推論二
\[\sum_{i=0}^n\dbinom{n}{i}^2=\dbinom{2n}{n}
\]
\]
證明的話先把式子的平方拆開，變成這樣
\[\sum_{i=0}^n\dbinom{n}{i}\times\dbinom{n}{i}
\]
\]
然後考慮這樣的一個轉換：
\[\dbinom{n}{i}=\dbinom{n}{n-i}
\]
\]
帶入原式可以發現，又變成了范德蒙德卷積的形式
\[\sum_{i=0}^n\dbinom{n}{i}\dbinom{n}{n-i}
\]
\]
推論三
\[\sum_{i=0}^m\dbinom{n}{i}\dbinom{m}{i}=\dbinom{n+m}{m}
\]
\]
證明也很簡單，考慮這樣的一個轉換
\[\dbinom{m}{i}=\dbinom{m}{m-i}
\]
\]
帶入以後成為范德蒙德卷積的形式：
\[\sum_{i=0}^m\dbinom{n}{i}\dbinom{m}{m-i}
\]
\]
