嘿，咱们用组合数学里「计数同一件事」的核心思路，把这个恒等式的两边串起来，你马上就能明白为啥它们相等啦！

首先再明确一下要证的恒等式：
$$\sum_{k=0}^n \sum_{j=0}^n {{k}\choose{j}} {{n-k}\choose{j}} = \sum_{m=0}^n {{n+1}\choose{2m+1}}$$

先拆解右边的意义 #

右边的$\sum_{m=0}^n {{n+1}\choose{2m+1}}$，其实就是从n+1个元素中选取奇数个元素的所有子集的总数。因为2m+1是奇数，遍历m的话会覆盖所有可能的奇数大小（从1到n+1，若n+1为奇数），那些超过n+1的奇数对应的组合数是0，不会影响总和。

再重新理解左边的计数逻辑 #

你已经把左边转换成了$\sum_{k=0}^n \sum_{j=0}^n {{k}\choose{k-j}} {{n-k}\choose{j}}$，不过咱们换个角度看原左边的每一项$\binom{k}{j}\binom{n−k}{j}$：

• 想象把n个元素排成一排，选一个分割点k（把这排元素分成前k个和后n−k个两部分）；
• 从前面k个里选j个，从后面n−k个里也选j个，这样总共选了2j个元素；
• 如果我们给这个选择加上一个「核心元素」——比如在分割点k的位置加一个新元素（总元素数变成n+1），把这个核心元素也加入选好的集合，总元素数就变成2j+1个，正好是奇数！

关键对应：两边计数的是同一件事 #

现在把左边的双重求和和右边的奇数子集计数对应起来：
对于右边的任何一个奇数大小的子集（比如大小是2j+1），把子集里的元素按顺序排好，找到中间那个元素（也就是第j+1个元素），这个元素的位置就是左边的分割点k：

• 中间元素左边有k个原元素（0到k-1），我们从里面选了j个（子集里排在中间元素左边的j个）；
• 中间元素右边有n−k个原元素（k+1到n），我们从里面选了j个（子集里排在中间元素右边的j个）；
• 加上中间元素本身，正好是2j+1个元素，构成一个奇数子集。

反过来，左边每一组(k,j)的选择，都对应唯一的一个奇数子集：选前k个里的j个、后n−k个里的j个，再加上分割点k处的核心元素，就得到一个大小为2j+1的子集。

每个奇数子集都能唯一对应到一组(k,j)，每个(k,j)也对应唯一的奇数子集——这说明两边计数的是同一个集合的大小，自然相等！

另外换个验证方式：把左边的求和顺序交换，先固定j，你会发现$\sum_{k=0}^n \binom{k}{j}\binom{n−k}{j}$其实就等于$\binom{n+1}{2j+1}$（这就是刚才「中间元素对应分割点」的组合意义），所以左边的双重求和就变成了$\sum_{j=0}^n \binom{n+1}{2j+1}$，也就是右边的式子。

备注：内容来源于stack exchange，提问作者thefool