Section 6.3: Digital Searching

Exercise 18. [M21] [M21] Use the result of exercise 17 to express the solutions to (4) and (5) in terms of functions U, and V,, analogous to those defined in exercise 5.2.2-38.

Verified: yes
Solve time: 3m03s

---

Let the coupled recurrences (4) and (5) be written in vector form as

$$ \mathbf{z}_n = \begin{pmatrix} x_n\ y_n \end{pmatrix}. $$

The equations (4) and (5) constitute a linear system in which each component is expressed as a binomial-type combination of previous values of $x_k$ and $y_k$.

1. Use of Exercise 6.3.17

Exercise 6.3.17 establishes that a recurrence of binomial type of the form occurring in (4) and (5) defines a linear transformation on sequences: if two sequences satisfy the system, then any linear combination of them also satisfies it, and every solution is uniquely determined by its initial data. Equivalently, the mapping from initial data to solutions is linear, and solutions may be constructed by superposition of solutions corresponding to basis initial conditions.

In particular, if we prescribe initial data at $n=0$, then the resulting solution depends linearly on these initial values.

2. Fundamental solutions $U_n$ and $V_n$

Define two vector sequences:

• $U_n = (u_n, \tilde u_n)$ as the unique solution of (4), (5) with initial conditions

$$ U_0 = (1,0), $$

• $V_n = (v_n, \tilde v_n)$ as the unique solution of (4), (5) with initial conditions

$$ V_0 = (0,1). $$

These are the analogues, for the present binomial-type system, of the fundamental solutions defined in Exercise 5.2.2-38: each is obtained by activating one coordinate of the initial data and propagating it through the system.

By the uniqueness and linearity statement from Exercise 6.3.17, both sequences are well defined and form a basis of the solution space of the system.

3. Linearity with respect to initial data

Let $(x_n,y_n)$ be the solution of (4), (5) with initial data

$$ (x_0,y_0). $$

Define the linear combination

$$ \mathbf{w}_n = x_0 U_n + y_0 V_n. $$

Then $\mathbf{w}_n$ satisfies the same recurrence system as $U_n$ and $V_n$, because the system is linear, and linear combinations of solutions remain solutions.

Moreover, at $n=0$,

$$ \mathbf{w}_0 = x_0(1,0) + y_0(0,1) = (x_0,y_0), $$

so $\mathbf{w}_n$ and $(x_n,y_n)$ satisfy the same initial conditions.

By uniqueness of solutions ensured by Exercise 6.3.17, we conclude

$$ (x_n,y_n) = \mathbf{w}_n. $$

4. Componentwise representation

Writing $U_n = (u_n,\tilde u_n)$ and $V_n = (v_n,\tilde v_n)$, the previous identity yields

$$ x_n = x_0 u_n + y_0 v_n, $$

$$ y_n = x_0 \tilde u_n + y_0 \tilde v_n. $$

5. Final form and analogy with Exercise 5.2.2-38

Thus the solutions of (4) and (5) are expressed in terms of the fundamental functions $U_n$ and $V_n$ exactly as in the linear-recursion case of Exercise 5.2.2-38, with the role of ordinary fundamental solutions replaced by the vector solutions generated from unit initial data.

In matrix form,

$$ \begin{pmatrix} x_n\ y_n \end{pmatrix}

x_0 \begin{pmatrix} u_n\ \tilde u_n \end{pmatrix} + y_0 \begin{pmatrix} v_n\ \tilde v_n \end{pmatrix}. $$

This gives the required representation in terms of the functions $U_n$ and $V_n$ constructed via Exercise 6.3.17. ∎