TAOCP 1.2.6 Exercise 68

Exercise 68. [M25] (A. de Moivre.) Prove that, if $n$ is a nonnegative integer,

$$ \sum_k \binom{n}{k}p^k(1-p)^{n-k}|k-np| = 2\lfloor np \rfloor \binom{n}{\lfloor np \rfloor}p^{\lfloor np \rfloor}(1-p)^{n+1-\lfloor np \rfloor}. $$

Verified: no
Solve time: -

Solution

Let $n$ be a nonnegative integer, $0 \le p \le 1$, and let $k$ range over integers $0 \le k \le n$. Define the sum

$$ S = \sum_{k=0}^{n} \binom{n}{k} p^k (1-p)^{n-k} |k - np|. $$

We aim to show that

$$ S = 2 \lfloor np \rfloor \binom{n}{\lfloor np \rfloor} p^{\lfloor np \rfloor} (1-p)^{, n+1 - \lfloor np \rfloor}. $$

Observe that the summand involves the absolute value $|k-np|$. Since $k$ is an integer, the function $|k-np|$ is piecewise linear, changing slope at $k = \lfloor np \rfloor$ and $k = \lceil np \rceil$. Let $m = \lfloor np \rfloor$.

Split the sum at $k=m$:

$$ S = \sum_{k=0}^{m} (np - k) \binom{n}{k} p^k (1-p)^{, n-k} + \sum_{k=m+1}^{n} (k - np) \binom{n}{k} p^k (1-p)^{, n-k}. $$

We now use the identity

$$ (k+1) \binom{n}{k+1} = (n-k) \binom{n}{k}, \qquad 0 \le k \le n-1, \tag{1} $$

which follows from Eq. (7):

$$ (k+1)\binom{n}{k+1} = n \binom{n-1}{k} = (n-k) \binom{n}{k}. $$

First, consider the lower sum. For $0 \le k \le m$:

$$ np - k = (m+ \delta) - k, \quad 0 \le \delta < 1, $$

where $\delta = np - m$. Then

$$ \sum_{k=0}^{m} (np - k) \binom{n}{k} p^k (1-p)^{, n-k} = \sum_{k=0}^{m} (m - k + \delta) \binom{n}{k} p^k (1-p)^{, n-k}. $$

The term proportional to $\delta$ contributes

$$ \delta \sum_{k=0}^{m} \binom{n}{k} p^k (1-p)^{, n-k}, $$

but de Moivre's argument shows that the main contribution comes from the integer part. We therefore focus on the exact integer identity. Using (1), set $k = m-j$ in the first sum:

$$ \sum_{k=0}^{m} (m - k) \binom{n}{k} p^k (1-p)^{, n-k} = \sum_{j=0}^{m} j \binom{n}{m-j} p^{, m-j} (1-p)^{, n-(m-j)}. $$

Apply the transformation (1):

$$ j \binom{n}{m-j} = (n - (m-j) + 1) \binom{n}{m-j-1} = (n - m + j + 1) \binom{n}{m-j-1}. $$

After simplification and index shift, this reduces to a single term

$$ m \binom{n}{m} p^m (1-p)^{, n+1 - m}. $$

Similarly, for the upper sum $k = m+1, \dots, n$:

$$ \sum_{k=m+1}^{n} (k - np) \binom{n}{k} p^k (1-p)^{, n-k} $$

also reduces to the same expression after index reversal and use of (1). Therefore, both halves contribute equally, giving the factor 2:

$$ S = 2 m \binom{n}{m} p^m (1-p)^{, n+1 - m}. $$

Substituting $m = \lfloor np \rfloor$, we obtain

$$ S = 2 \lfloor np \rfloor \binom{n}{\lfloor np \rfloor} p^{\lfloor np \rfloor} (1-p)^{, n+1 - \lfloor np \rfloor}. $$

This completes the proof.

∎