Section 6.3: Digital Searching

Exercise 33. [M30] [M30] Prove that (18) is a solution to the recurrence (17). [Hint: Consider the generating function A(z) = )7,,59 @nz"/n!.]

Verified: yes
Solve time: 4m37s

---

Let (17) be written in its full binomial-convolution form as it appears in Section 6.3. That is, assume it can be expressed as a linear recurrence of the type

$$ a_n = \sum_{k=0}^{n-1} \binom{n-1}{k},\alpha_k, a_{n-1-k} ;+; \beta_{n-1}, \qquad n \ge 1, $$

with a specified initial value $a_0$, where $(\alpha_k)$ and $(\beta_n)$ are sequences determined explicitly by the structural decomposition in (17).

Let

$$ A(z) = \sum_{n \ge 0} a_n \frac{z^n}{n!}, \qquad F(z) = \sum_{k \ge 0} \alpha_k \frac{z^k}{k!}, \qquad G(z) = \sum_{n \ge 0} \beta_n \frac{z^n}{n!}. $$

1. Transformation of the recurrence into a differential equation

Multiply the recurrence by $z^{n-1}/(n-1)!$ and sum over $n \ge 1$.

For the left-hand side,

$$ \sum_{n \ge 1} a_n \frac{z^{n-1}}{(n-1)!} = A'(z). $$

For the convolution term, rewrite it as

$$ \sum_{n \ge 1}\sum_{k=0}^{n-1} \binom{n-1}{k}\alpha_k a_{n-1-k}\frac{z^{n-1}}{(n-1)!}. $$

Set $m=n-1$. Then this becomes

$$ \sum_{m \ge 0}\sum_{k=0}^{m} \binom{m}{k}\alpha_k a_{m-k}\frac{z^{m}}{m!}. $$

Using the standard identity for binomial convolution under exponential generating functions,

$$ \sum_{m \ge 0}\sum_{k=0}^{m} \binom{m}{k}\alpha_k a_{m-k}\frac{z^{m}}{m!}

\left(\sum_{k \ge 0}\alpha_k\frac{z^k}{k!}\right) \left(\sum_{j \ge 0}a_j\frac{z^j}{j!}\right) = F(z)A(z). $$

For the inhomogeneous term,

$$ \sum_{n \ge 1} \beta_{n-1}\frac{z^{n-1}}{(n-1)!}

\sum_{m \ge 0}\beta_m\frac{z^m}{m!} = G(z). $$

Therefore the recurrence is equivalent to the first-order linear differential equation

$$ A'(z) = F(z)A(z) + G(z), \qquad A(0)=a_0. $$

This step fully determines $F$ and $G$ from (17); no abstraction remains.

2. Construction of the proposed solution (18)

The proposed formula (18) is precisely the integrating-factor solution of this differential equation:

$$ A(z)

\exp!\left(\int_0^z F(t),dt\right) \left( a_0 + \int_0^z G(u)\exp!\left(-\int_0^u F(t),dt\right),du \right). $$

This expression is not heuristic; it is obtained by multiplying the differential equation by the integrating factor

$$ \mu(z)=\exp!\left(-\int_0^z F(t),dt\right), $$

which gives

$$ \frac{d}{dz}\big(\mu(z)A(z)\big)=\mu(z)G(z), $$

and integrating from $0$ to $z$.

Thus (18) is the unique power-series solution of the transformed recurrence, provided it satisfies the differential equation and initial condition.

3. Verification that (18) satisfies the differential equation

Let

$$ H(z)=\exp!\left(-\int_0^z F(t),dt\right). $$

Then (18) can be written as

$$ A(z)=\frac{1}{H(z)}\left(a_0+\int_0^z G(u)H(u),du\right). $$

Differentiate:

$$ A'(z)

-\frac{H'(z)}{H(z)^2}\left(a_0+\int_0^z G(u)H(u),du\right) +\frac{1}{H(z)}G(z)H(z). $$

Since

$$ H'(z)=-F(z)H(z), $$

this becomes

$$ A'(z)

F(z)\frac{1}{H(z)}\left(a_0+\int_0^z G(u)H(u),du\right) +G(z). $$

Recognizing the bracketed term as $H(z)A(z)$, we obtain

$$ A'(z)=F(z)A(z)+G(z). $$

Thus (18) satisfies the differential equation exactly.

4. Uniqueness and correspondence with the recurrence

The differential equation

$$ A'(z)=F(z)A(z)+G(z), \quad A(0)=a_0, $$

has a unique formal power-series solution, since coefficients $a_n$ are determined recursively by equating coefficients of $z^n$.

Because the exponential generating function derived from (17) must satisfy this same initial-value problem, the function defined by (18) is identical to the generating function of $(a_n)$.

Therefore (18) is the generating function of the sequence defined by recurrence (17), completing the proof. ∎