每日一题[2270]组合恒等式

已知如下数列：

第 $1$ 个数列：$1,1,1,1,1,1,1,1,1,1,1,1,1,\cdots$

第 $2$ 个数列：$1,2,3,4,5,6,7,8,9,10,11,\cdots$

第 $3$ 个数列：$1,2,4,7,11,16,22,29,37,\cdots$

第 $4$ 个数列：$1,2,4,8,15,26,42,64,\cdots$ $\cdots$

其中第 $m$ 个数列的每一项与前一项的差恰好是第 $m-1$ 个数列，则第 $m$ 个数列的通项是_______，前 $n$ 项和是_______．

答案    $\displaystyle\sum_{k=0}^{m-1}\dbinom{n-1}k$；$\displaystyle\sum_{k=1}^m\dbinom nk$．

解析    设第 $m$ 个数列的第 $n$ 项为 $a(m,n)$，则当 $n\geqslant 2$ 时，有 $$a(m,n)-a(m,n-1)=a(m-1,n-1),$$ 且 $a(1,n)=1$，$a(m,1)=1$．联想组合恒等式，有 $$a(m,n)=\sum_{k=0}^{m-1}\dbinom{n-1}k,$$ 其中定义当 $k>n-1$ 时，$\dbinom{n-1}k=0$，且当 $k=0$ 时，$\dbinom{n-1}k=1$．进而根据常用组合恒等式，有 $$\sum_{j=1}^na_(m,n)=\sum_{j=1}^n\sum_{k=0}^{m-1}\dbinom{n-1}k=\sum_{k=0}^{m-1}\sum_{j=0}^{n-1}\dbinom{j}{k}=\sum_{k=0}^{n-1}\dbinom n{k+1}=\sum_{k=1}^m\dbinom nk,$$ 设第 $m$ 个数列的第 $n$ 项为 $a(m,n)$，则当 $n\geqslant 2$ 时，有 $$a(m,n)-a(m,n-1)=a(m-1,n-1),$$ 且 $a(1,n)=1$，$a(m,1)=1$．联想组合恒等式，有 $$a(m,n)=\sum_{k=0}^{m-1}\dbinom{n-1}k,$$ 其中定义当 $k>n-1$ 时，$\dbinom{n-1}k=0$，且当 $k=0$ 时，$\dbinom{n-1}k=1$．进而根据常用组合恒等式，有 $$\sum_{j=1}^na_(m,n)=\sum_{j=1}^n\sum_{k=0}^{m-1}\dbinom{n-1}k=\sum_{k=0}^{m-1}\sum_{j=0}^{n-1}\dbinom{j}{k}=\sum_{k=0}^{n-1}\dbinom n{k+1}=\sum_{k=1}^m\dbinom nk.$$

备注    最后的换序求和可以利用杨辉三角帮助理解．