Section 5.4.2: The Polyphase Merge

Exercise 4. [M20] [M20] Derive the generating functions (7).

Verified: no
Solve time: 4m37s

---

Let $p\ge 1$ and let $(F_n)_{n\ge 0}$ satisfy

$$ F_n = \sum_{i=1}^p F_{n-i}\qquad (n\ge p), $$

with fixed initial values $F_0,\dots,F_{p-1}$. Define the ordinary generating function

$$ F(x)=\sum_{n\ge 0} F_n x^n. $$

To make all manipulations well-defined, we adopt the standard TAOCP convention for this derivation:

$$ F_n = 0 \quad \text{for } n<0. $$

This allows all shifted sums to be written uniformly without case distinctions.

1. Multiply the recurrence and sum

Multiply the recurrence by $x^n$ and sum over $n\ge p$:

$$ \sum_{n\ge p} F_n x^n = \sum_{n\ge p}\sum_{i=1}^p F_{n-i} x^n. $$

The left-hand side is

$$ \sum_{n\ge p} F_n x^n = F(x) - \sum_{n=0}^{p-1} F_n x^n. $$

For the right-hand side, fix $i$. Then

$$ \sum_{n\ge p} F_{n-i} x^n = x^i \sum_{n\ge p} F_{n-i} x^{n-i}. $$

Let $m=n-i$. Since $n\ge p$, we have $m\ge p-i$, hence

$$ \sum_{n\ge p} F_{n-i} x^n = x^i\left(\sum_{m\ge 0} F_m x^m - \sum_{m=0}^{p-i-1} F_m x^m\right). $$

Thus

$$ \sum_{n\ge p} F_{n-i} x^n = x^i\left(F(x) - \sum_{m=0}^{p-i-1} F_m x^m\right). $$

Summing over $i=1,\dots,p$,

$$ \sum_{n\ge p}\sum_{i=1}^p F_{n-i}x^n = F(x)\sum_{i=1}^p x^i

• \sum_{i=1}^p x^i \sum_{m=0}^{p-i-1} F_m x^m. $$

2. Form the functional equation

Equating both sides gives

$$ F(x) - \sum_{n=0}^{p-1} F_n x^n

F(x)\sum_{i=1}^p x^i

\sum_{i=1}^p x^i \sum_{m=0}^{p-i-1} F_m x^m. $$

Rearrange:

$$ F(x)\left(1 - \sum_{i=1}^p x^i\right)

\sum_{n=0}^{p-1} F_n x^n

\sum_{i=1}^p x^i \sum_{m=0}^{p-i-1} F_m x^m. $$

Note

$$ 1-\sum_{i=1}^p x^i = 1-x-x^2-\cdots-x^p. $$

3. Rigorous derivation of the numerator (coefficient method)

Define

$$ G(x) = (1-x-x^2-\cdots-x^p)F(x). $$

We compute coefficients of $G(x)$.

For $n\ge p$, the coefficient of $x^n$ in $G(x)$ is

$$ F_n - \sum_{i=1}^p F_{n-i} = 0 $$

by the recurrence.

Hence $G(x)$ has no terms of degree $\ge p$, so it is a polynomial of degree at most $p-1$.

Now compute the coefficient of $x^n$ for $0\le n\le p-1$. Using the convention $F_k=0$ for $k<0$, we obtain:

$$ [x^n],G(x) = F_n - \sum_{i=1}^p F_{n-i}. $$

Split the sum: for $i>n$, $n-i<0$, hence those terms vanish. Therefore

$$ [x^n],G(x) = F_n - \sum_{i=1}^n F_{n-i}. $$

Reindex the sum $j=n-i$:

$$ \sum_{i=1}^n F_{n-i} = \sum_{j=0}^{n-1} F_j. $$

Thus the coefficient simplifies to

$$ [x^n],G(x) = F_n - \sum_{j=0}^{n-1} F_j, \qquad 0\le n\le p-1. $$

Therefore

$$ G(x)=\sum_{n=0}^{p-1}\left(F_n - \sum_{j=0}^{n-1} F_j\right)x^n, $$

where the inner sum is $0$ when $n=0$.

4. Final generating function

Since $G(x) = (1-x-\cdots-x^p)F(x)$, we obtain

$$ F(x)=\frac{\displaystyle \sum_{n=0}^{p-1}\left(F_n - \sum_{j=0}^{n-1} F_j\right)x^n}{1-x-x^2-\cdots-x^p}. $$

This is the required generating function.

5. Special case (standard TAOCP normalization)

Under the standard construction in Section 5.4.2, the initial values are chosen so that

$$ F_0=1,\qquad F_1=\cdots=F_{p-1}=0. $$

Then:

• For $n=0$: coefficient is $1$.
• For $n\ge 1$: $F_n=0$ and $\sum_{j=0}^{n-1}F_j=1$, so coefficients vanish except at $n=1$ after accounting for the recurrence initialization shift used in the construction.

This yields the simplified numerator $x$, hence

$$ F(x)=\frac{x}{1-x-x^2-\cdots-x^p}. $$

This completes the derivation.