$$
\sum_{i=0}^n A^i\binom{n-i}{k}=\sum_{i=0}^n(A-1)^i\binom{n+1}{i+k+1}
$$
其中 $A,n,k$ 均为正整数,特别地,当 $A=1$ 时,等式右端 $(A-1)^0$ 应视作 $1$ .
证明
有 $n$ 个球,先确定一个 $i$ ,将前 $i$ 个球拿出,这 $i$ 个球每个球可以放入 $A$ 个盒子中的任意一个,再从剩下的 $n-i$ 个球中选出 $k$ 个球,这 $k$ 个球每个球只能放入一个盒子中,求方案数.
显然左式是上面这个问题的答案,接下来我们用另外一个办法来选球,以证明右式也是这个问题的答案.
记前 $i$ 个球为第一类球,选出的 $k$ 个球为第二类球.
枚举共有 $j$ 个第一类球放入了前 $A-1$ 个盒子,并讨论最后一个第一类球是否放入了前 $A-1$ 个盒子.
若最后一个第一类球放入了前 $A-1$ 个盒子,那么我们选出 $i+k$ 个球,其中前 $i$ 个球表示放入前 $A-1$ 个盒子的球,后 $k$ 个球表示第二类球,贡献为 $\sum(A-1)^i \binom{n}{i+k}$.
若最后一个第一类球放入了最后一个盒子,那么我们选出 $i+1+k$ 个球,其中前 $i$ 个球表示放入前 $A-1$ 个盒子的球,第 $i+1$ 个球表示最后一个第一类球,后 $k$ 个球表示第二类球,贡献为 $\sum(A-1)^i \binom{n}{i+1+k}$ .
第一类球需要形成一个前缀,此时前缀中空出的位置一定是放入最后一个盒子的第一类球.
将两类贡献求和即可得到右式 $\sum_{i=0}^n(A-1)^i\binom{n+1}{i+k+1}$ ,从而证明了右式也是问题的答案,得出左式和右式相等.
运用
当 $n$ 很大, $k$ 较小时,直接用左式计算,时间复杂度是 $O(n-k)$ 的.
而右式可以通过简单处理变成二项式定理的形式,可以用总和减掉另外 $k$ 项的贡献求得答案,时间复杂度 $O(k)$ .