计算机程序设计艺术

当\(n \in \mathbb{N}\)时，证明下列等式成立

$$
\require{AMSmath}
\sum_{k} \binom{n}{k} p^k (1-p)^{n-k} \left| k-np \right| =
2 \lceil np \rceil \binom{n}{\lceil np \rceil} p^{\lceil np \rceil}(1-p)^{n+1-\lceil np \rceil}
$$

基本思路：因为等式左侧涉及的难处理符号为绝对值符号，等式右侧涉及到的难处理符号为取整符号，为将两者进行关联，关键在于去掉绝对值符号并确定非整数np的上下整数限。

显然，根据题意，变量p的取值范围为\(p \in \left[ 0,1 \right]\)，如此对于一般的情况，我们可以设定变量np的取值范围为\(np \in \left( M,N \right)\)，那么我们便可以化解左侧的绝对值符号以及右侧的取整符号如下：

$$
\begin{cases}
\lceil np \rceil &= N = M+1 \\
\left| k-np \right | &=
\begin{cases}
np -k, & k \le M \\
k -np, & k \ge N
\end{cases} \\
\end{cases}
$$

在此基础上，我们开始对等式左侧进行解构：

$$
\begin{align}
\sum_{k=0}^{n} \binom{n}{k} p^k (1-p)^{n-k} \left| k-np \right|
& = \sum_{k=0}^{M} \binom{n}{k} p^k (1-p)^{n-k} (np-k) + \sum_{k=N}^{n} \binom{n}{k} p^k (1-p)^{n-k} (k-np) \\
&= \sum_{k=0}^{n} \binom{n}{k} p^k (1-p)^{n-k} \left( k-np \right) + 2 \sum_{k=0}^{M} \binom{n}{k} p^k (1-p)^{n-k} (np-k) \\
&= 2 \sum_{k=0}^{M} \binom{n}{k} p^k (1-p)^{n-k} (np-k) \tag{1} \\
\end{align}
$$

因此，现在问题的核心转移至计算上述求和公式1，计算过程如下：

$$
\begin{align}
2 \sum_{k=0}^{M} \binom{n}{k} p^k (1-p)^{n-k} (np-k)
&= 2np\sum_{k=0}^{M} \binom{n}{k}p^{k}(1-p)^{n-k} – 2np\sum_{k=0}^{M} \binom{n-1}{k-1} p^{k-1} (1-p)^{n-k} \\
&= 2np\sum_{k=0}^{M} \{ \binom{n-1}{k} + \binom{n-1}{k-1} \} p^{k}(1-p)^{n-k} – 2np \sum_{k=0}^{M} \binom{n-1}{k-1} p^{k-1} (1-p)^{n-k} \\
&= 2np \sum_{k=0}^{M} \binom{n-1}{k}p^{k}(1-p)^{n-k}-2np \sum_{k=0}^{M}\binom{n-1}{k-1}p^{k-1}(1-p)^{n-(k+1)} \\
&= 2np \sum_{k=0}^{M} \binom{n-1}{k}p^{k}(1-p)^{n-k}-2np \sum_{k=0}^{M-1}\binom{n-1}{k}p^{k}(1-p)^{n-k} \\
&= 2np \binom{n-1}{M} p^M (1-p)^{n-M} \\
&= 2(M+1)\binom{n}{M+1}p^{M+1}(1-p)^{n+1-(M+1)} \\
\end{align}
$$

至此，整个证明工作已完结！