一个组合恒等式
老年数数选手复健一下。
例题.
证
\sum_{k=0}^n(-1)^k{2n-k\choose k}2^{2n-2k}=2n+1 证明.
考虑所有
2n 步的，先\rightarrow 再\uparrow 的格路；显然恰好2n+1 条。然后考虑用容斥对其计数，具体来说令
k 为\uparrow\rightarrow 的数目，整个格路由k 个\uparrow\rightarrow 和2n-2k 个? 组成。它们的相对位置是{2n-k\choose k} 的，而? 的定向是2^{2n-2k} 的。
后记.
戚大师说这是胶带组合数学课的作业，可惜本专业不开 qaq