TAOCP 5.2.2 Exercise 37

Section 5.2.2: Sorting by Exchanging

Exercise 37. [M28] Determine all sequences $\langle a_n \rangle$ such that $\langle \hat{a}_n \rangle = \langle a_n \rangle$, in the sense of exercise 36.

Verified: no
Solve time: 3m08s

Setup

Let (\langle a_n \rangle = a_0, a_1, a_2, \ldots) be a sequence. Its binomial transform (with alternating signs) is defined by [ \hat{a}n = \sum{k=0}^n \binom{n}{k} (-1)^k a_k \qquad (n \ge 0). ] We seek all sequences for which (\langle \hat{a}n \rangle = \langle a_n \rangle), i.e. [ a_n = \sum{k=0}^n \binom{n}{k} (-1)^k a_k \quad \text{for all } n \ge 0. ]

Solution

Introduce the exponential generating function [ A(x) = \sum_{n=0}^\infty a_n \frac{x^n}{n!}. ] The exponential generating function of the transformed sequence is [ \begin{aligned} \sum_{n=0}^\infty \hat{a}n \frac{x^n}{n!} &= \sum{n=0}^\infty \sum_{k=0}^n \binom{n}{k} (-1)^k a_k \frac{x^n}{n!} \ &= \sum_{k=0}^\infty (-1)^k a_k \frac{x^k}{k!} \sum_{n=k}^\infty \frac{x^{n-k}}{(n-k)!} \ &= e^x \sum_{k=0}^\infty a_k \frac{(-x)^k}{k!} = e^x A(-x). \end{aligned} ] The condition (\hat{a}_n = a_n) for all (n) is therefore equivalent to [ A(x) = e^x A(-x). \tag{1} ]

Rewrite (1) as (A(x) e^{-x/2} = A(-x) e^{x/2}). Define (F(x) = A(x) e^{-x/2}). Then (1) becomes [ F(x) = F(-x), ] so (F) is an even formal power series. Conversely, if (F) is any even formal power series, then (A(x) = e^{x/2} F(x)) satisfies (1) and therefore yields a fixed point of the binomial transform.

Write (F(x) = \sum_{m=0}^\infty c_m x^{2m}) with arbitrary coefficients (c_0, c_1, c_2, \ldots). Then [ \begin{aligned} A(x) &= e^{x/2} \sum_{m=0}^\infty c_m x^{2m} = \sum_{m=0}^\infty c_m x^{2m} \sum_{j=0}^\infty \frac{(x/2)^j}{j!} \ &= \sum_{n=0}^\infty \frac{x^n}{n!} \sum_{m=0}^{\lfloor n/2 \rfloor} c_m \frac{n!}{(n-2m)!} 2^{-(n-2m)}. \end{aligned} ] Hence the general solution is [ \boxed{a_n = \sum_{m=0}^{\lfloor n/2 \rfloor} c_m , \frac{n!}{(n-2m)!} , 2^{2m-n} \qquad (n \ge 0),} ] where (c_0, c_1, c_2, \ldots) are arbitrary constants.

Equivalently, one may freely choose the even-indexed terms (a_0, a_2, a_4, \ldots) and then define the odd-indexed terms by the recurrence [ a_{2n+1} = -\frac{1}{2} \sum_{k=0}^{2n} \binom{2n+1}{k} (-1)^k a_k \qquad (n \ge 0). ]

Verification

We check directly that the formula for (a_n) satisfies (\hat{a}n = a_n). Substitute the expression for (a_n) into the binomial transform: [ \begin{aligned} \hat{a}n &= \sum{k=0}^n \binom{n}{k} (-1)^k \sum{m=0}^{\lfloor k/2 \rfloor} c_m \frac{k!}{(k-2m)!} 2^{2m-k} \ &= \sum_{m=0}^{\lfloor n/2 \rfloor} c_m , 2^{2m} \sum_{k=2m}^n (-1)^k \binom{n}{k} \frac{k!}{(k-2m)!} 2^{-k} \ &= \sum_{m=0}^{\lfloor n/2 \rfloor} c_m , 2^{2m} , n! \sum_{j=0}^{n-2m} \frac{(-1)^{j+2m}}{j! , (n-2m-j)!} 2^{-j-2m} \quad (j = k-2m) \ &= \sum_{m=0}^{\lfloor n/2 \rfloor} c_m , n! , 2^{-n+2m} \sum_{j=0}^{n-2m} \binom{n-2m}{j} \left(-\frac{1}{2}\right)^j \ &= \sum_{m=0}^{\lfloor n/2 \rfloor} c_m , n! , 2^{-n+2m} \left(1-\frac{1}{2}\right)^{n-2m} \ &= \sum_{m=0}^{\lfloor n/2 \rfloor} c_m , \frac{n!}{(n-2m)!} , 2^{2m-n} = a_n. \end{aligned} ] Thus the condition holds for all (n). This completes the proof.

∎