TAOCP 1.2.9 Exercise 15

Define G_n(z)=\sum_{k=0}^{n}\binom{n-k}{k}z^k.

taocpmathematicsalgorithmsvolume-1math-hard

Section 1.2.9: Generating Functions

Exercise 15. [M28] By considering $H(w)=\sum_{n \ge 0} G_n(z)w^n$, find a closed form for the generating function

$$ G_n(z) = \sum_{k=0}^{n} \binom{n-k}{k} z^k = \sum_{k=0}^{n} \binom{2k-n-1}{k} (-z)^k. $$

Verified: yes
Solve time: 1m26s

Setup

Define

$$ G_n(z)=\sum_{k=0}^{n}\binom{n-k}{k}z^k. $$

Define the ordinary generating function in $n$

$$ H(w)=\sum_{n\ge 0} G_n(z)w^n. $$

The task is to determine a closed form for $H(w)$.

Solution

Write

$$ G_n(z)=\sum_{k\ge 0}\binom{n-k}{k}z^k $$

with the convention $\binom{n-k}{k}=0$ when $k>\frac{n}{2}$ or $n-k<k$.

Split $G_n$ using Pascal’s identity

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

Sum over $k$:

$$ G_n(z)=\sum_{k\ge 0}\binom{n-1-k}{k}z^k+\sum_{k\ge 0}\binom{n-1-k}{k-1}z^k. $$

For the second sum, substitute $k\mapsto k+1$:

$$ \sum_{k\ge 1}\binom{n-2-k}{k}z^{k+1} = z\sum_{k\ge 0}\binom{n-2-k}{k}z^k. $$

Thus

$$ G_n(z)=G_{n-1}(z)+zG_{n-2}(z) \qquad (n\ge 2). $$

Initial values follow directly from the definition:

$$ G_0(z)=\binom{0}{0}=1,\qquad G_1(z)=\binom{1}{0}=1. $$

Multiply the recurrence by $w^n$ and sum for $n\ge 2$:

$$ \sum_{n\ge 2}G_n w^n =\sum_{n\ge 2}G_{n-1}w^n+z\sum_{n\ge 2}G_{n-2}w^n. $$

Rewrite each term using shifts:

$$ \sum_{n\ge 2}G_n w^n = H(w)-G_0-G_1w, $$

$$ \sum_{n\ge 2}G_{n-1}w^n = w\sum_{n\ge 1}G_n w^n = w(H(w)-G_0), $$

$$ \sum_{n\ge 2}G_{n-2}w^n = w^2H(w). $$

Substitute $G_0=1$:

$$ H(w)-1-w = w(H(w)-1)+zw^2H(w). $$

Rearrange:

$$ H(w)-wH(w)-zw^2H(w)=1. $$

Factor:

$$ H(w)(1-w-zw^2)=1. $$

Hence

$$ H(w)=\frac{1}{1-w-zw^2}. $$

Verification

The denominator expansion implies

$$ (1-w-zw^2)H(w)=1 $$

so the coefficient of $w^0$ is $G_0=1$.

For $n\ge 1$, equating coefficients of $w^n$ yields

$$ G_n=G_{n-1}+zG_{n-2}, $$

with the convention $G_{-1}=0$ induced by the power-series identity.

The explicit formula for $G_1$ extracted from $H(w)$ is $1$, matching the definition.

Notes

The recurrence $G_n=G_{n-1}+zG_{n-2}$ identifies $G_n(z)$ as the Fibonacci polynomials in the variable $z$, and the generating function

$$ \frac{1}{1-w-zw^2} $$

encodes this second-order linear recurrence directly. This matches the general structure described for linear recurrences in Section 1.2.9. ∎