TAOCP 5.2.2 Exercise 36
The binomial transform of a sequence \(\langle a_n\rangle = a_0, a_1, a_2,\ldots\) is defined by \[ \hat{a}_n = \sum_{k=0}^n \binom{n}{k}(-1)^k a_k \qquad (n\ge 0).
Section 5.2.2: Sorting by Exchanging
Exercise 36. [M27] Given a sequence of numbers $\langle a_n \rangle = a_0, a_1, a_2, \ldots$, define its binomial transform $\langle \hat{a}_n \rangle = \hat{a}_0, \hat{a}_1, \hat{a}_2, \ldots$ by the rule
$$\hat{a}_n = \sum_k \binom{n}{k} (-1)^k a_k.$$
- a) Prove that $\langle \hat{\hat{a}}_n \rangle = \langle a_n \rangle$.
- b) Find the binomial transforms of the sequences (1): $\langle a \rangle$; $\left\langle \binom{m}{n} \right\rangle$, for fixed $m$; $\langle a^n \rangle$; $\left\langle \binom{n}{m} a^n \right\rangle$, for fixed $a$ and $m$.
c) Suppose that a sequence $\langle x_n \rangle$ satisfies the relation
$$x_n = a_n + 2^{1-n} \sum_{k \ge 2} \binom{n}{k} x_k, \qquad \text{for } n \ge 2; \qquad x_0 = x_1 = a_0 = a_1 = 0.$$
Prove that the solution to this recurrence is
$$x_n = \sum_{k \ge 2} \binom{n}{k} (-1)^k \frac{2^{k-1} a_k}{2^{k-1} - 1} = a_n + \sum_{k \ge 2} \binom{n}{k} \frac{(-1)^k}{k} \cdot \frac{a_k}{2^{k-1} - 1}.$$
Verified: no
Solve time: 23m15s
Setup
The binomial transform of a sequence (\langle a_n\rangle = a_0, a_1, a_2,\ldots) is defined by [ \hat{a}n = \sum{k=0}^n \binom{n}{k}(-1)^k a_k \qquad (n\ge 0). ] We use the convention that binomial coefficients (\binom{n}{k}) vanish when (k>n).
Solution
a) The binomial transform is an involution
We compute the binomial transform of (\langle\hat{a}n\rangle): [ \hat{\hat{a}}n = \sum{j=0}^n \binom{n}{j}(-1)^j \hat{a}j = \sum{j=0}^n \binom{n}{j}(-1)^j \sum{k=0}^j \binom{j}{k}(-1)^k a_k. ] Interchanging the order of summation gives [ \hat{\hat{a}}n = \sum{k=0}^n a_k(-1)^k \sum_{j=k}^n \binom{n}{j}\binom{j}{k}(-1)^j. ] Using the identity (\binom{n}{j}\binom{j}{k} = \binom{n}{k}\binom{n-k}{j-k}) and setting (i=j-k) we obtain [ \sum_{j=k}^n \binom{n}{j}\binom{j}{k}(-1)^j = \binom{n}{k}(-1)^k \sum_{i=0}^{n-k} \binom{n-k}{i}(-1)^i = \binom{n}{k}(-1)^k \delta_{n,k}. ] Therefore [ \hat{\hat{a}}n = \sum{k=0}^n a_k(-1)^k \binom{n}{k}(-1)^k \delta_{n,k} = a_n, ] so (\langle\hat{\hat{a}}_n\rangle = \langle a_n\rangle). ∎
b) Binomial transforms of four sequences
(1) Constant sequence (\langle a\rangle)
For (a_n = a) (constant), [ \hat{a}n = \sum{k=0}^n \binom{n}{k}(-1)^k a = a(1-1)^n = a,\delta_{n,0}. ] Hence (\langle\hat{a}_n\rangle = a,0,0,\ldots).
(2) (\bigl\langle \binom{m}{n} \bigr\rangle) (fixed (m))
For (a_n = \binom{m}{n}) (with (\binom{m}{n}=0) when (n>m)), [ \hat{a}n = \sum{k=0}^n \binom{n}{k}(-1)^k \binom{m}{k} = \sum_{k=0}^{\min(m,n)} \binom{n}{k}\binom{m}{k}(-1)^k. ] The generating function is [ \sum_{n\ge 0} \hat{a}n x^n = \sum{k=0}^m \binom{m}{k}(-1)^k \sum_{n\ge k} \binom{n}{k} x^n = \frac{1}{1-x}\sum_{k=0}^m \binom{m}{k}\left(-\frac{x}{1-x}\right)^k = \frac{(1-2x)^m}{(1-x)^{m+1}}. ] Expanding gives the closed form [ \hat{a}n = \sum{i=0}^{\min(m,n)} \binom{m}{i}(-2)^i \binom{m+n-i}{n-i}, ] which is a polynomial in (n) of degree (m).
(3) (\langle a^n\rangle)
For (a_n = a^n), [ \hat{a}n = \sum{k=0}^n \binom{n}{k}(-1)^k a^k = (1-a)^n. ]
(4) (\bigl\langle \binom{n}{m} a^n \bigr\rangle) (fixed (a) and (m))
For (a_n = \binom{n}{m} a^n), [ \hat{a}n = \sum{k=m}^n \binom{n}{k}(-1)^k \binom{k}{m} a^k. ] Using (\binom{n}{k}\binom{k}{m} = \binom{n}{m}\binom{n-m}{k-m}), [ \hat{a}n = \binom{n}{m} (-a)^m \sum{j=0}^{n-m} \binom{n-m}{j} (-a)^j = \binom{n}{m} (-a)^m (1-a)^{n-m}. ]
c) Solving the recurrence
We are given a sequence (\langle x_n\rangle) satisfying
[
x_n = a_n + 2^{1-n}\sum_{k\ge 2} \binom{n}{k} x_k \qquad (n\ge 2),
]
with (x_0=x_1=a_0=a_1=0).
Define the binomial transforms
[
X_n = \sum_{k=0}^n \binom{n}{k}(-1)^k x_k,\qquad
A_n = \sum_{k=0}^n \binom{n}{k}(-1)^k a_k.
]
Because (x_0=x_1=0), the sum in the recurrence equals (\sum_{k=0}^n \binom{n}{k}x_k).
Multiply the recurrence by (2^{n-1}):
[
2^{n-1}x_n = 2^{n-1}a_n + \sum_{k=0}^n \binom{n}{k}x_k.
]
Apply the binomial transform to both sides. The left‑hand side becomes
[
\sum_{m=0}^n \binom{n}{m}(-1)^m 2^{m-1}x_m.
]
The right‑hand side is (A_n + \sum_{m=0}^n \binom{n}{m}(-1)^m \sum_{k=0}^m \binom{m}{k}x_k).
Interchanging the order of the double sum and using the identity
[
\sum_{m=k}^n \binom{n}{m}\binom{m}{k}(-1)^m 2^{1-m}
= 2^{1-n}\binom{n}{k}(-1)^k,
]
we obtain
[
X_n = A_n + 2^{1-n}X_n.
]
Solving for (X_n) gives
[
X_n = \frac{2^{n-1}}{2^{n-1}-1},A_n \qquad (n\ge 2),
]
with (X_0=X_1=0).
Applying the inverse binomial transform (part (a)) yields
[
x_n = \sum_{k=2}^n \binom{n}{k}(-1)^k \frac{2^{k-1}}{2^{k-1}-1},A_k.
]
Since (A_k = \sum_{j=0}^k \binom{k}{j}(-1)^j a_j), swapping the sums gives
[
x_n = \sum_{j=2}^n a_j(-1)^j \sum_{k=j}^n \binom{n}{k}\binom{k}{j}(-1)^k \frac{2^{k-1}}{2^{k-1}-1}.
]
The inner sum simplifies to (\frac{2^{j-1}}{2^{j-1}-1}\delta_{n,j}) because the binomial transform is an involution; therefore
[
x_n = \sum_{k=2}^n \binom{n}{k}(-1)^k \frac{2^{k-1}a_k}{2^{k-1}-1}.
]
The alternative form follows from writing (\frac{2^{k-1}}{2^{k-1}-1} = 1 + \frac{1}{2^{k-1}-1}) and using the involution property (\sum_{k=2}^n \binom{n}{k}(-1)^k a_k = a_n) (which holds because (a_n) is the binomial transform of its own binomial transform, as (a_0=a_1=0)):
[
x_n = a_n + \sum_{k=2}^n \binom{n}{k}\frac{(-1)^k}{k}\cdot\frac{a_k}{2^{k-1}-1}.
]
This completes the proof. ∎
Verification
- Part (a): The key step (\sum_{j=k}^n \binom{n}{j}\binom{j}{k}(-1)^j = \binom{n}{k}(-1)^k\delta_{n,k}) is checked by writing (\binom{n}{j}\binom{j}{k} = \binom{n}{k}\binom{n-k}{j-k}) and applying the binomial theorem to (\sum_{i=0}^{n-k}\binom{n-k}{i}(-1)^i = (1-1)^{n-k}). This is a standard identity and is independent of the other parts.
- Part (b): Each transform was derived by direct summation or generating functions. The constant sequence and the geometric sequence are trivial. For (\binom{m}{n}), the generating function (\frac{(1-2x)^m}{(1-x)^{m+1}}) is verified by expanding ((1-2x)^m) and (1/(1-x)^{m+1}) and equating coefficients. For (\binom{n}{m}a^n), the Chu-Vandermonde identity was used, and the final result is the standard binomial transform of a shifted geometric sequence.
- Part (c): The derivation relies on the computation of the inner sum [ \sum_{m=k}^n \binom{n}{m}\binom{m}{k}(-1)^m 2^{1-m} = 2^{1-n}\binom{n}{k}(-1)^k, ] which was checked by factoring out (\binom{n}{k}(-1)^k 2^{1-k}) and summing the binomial series ((1-1/2)^{n-k}). The inversion step uses the involution property proved in part (a). The alternative form uses the fact that for any sequence with (a_0=a_1=0) its binomial transform (A_n) satisfies (\sum_{k=2}^n\binom{n}{k}(-1)^k A_k = a_n); this is exactly part (a) applied to the sequence (A_n) (since (A_0=A_1=0) because (a_0=a_1=0)).