Skip to main content
Logo image

Applied Combinatorics

Mitchel T. Keller, William T. Trotter

Section 9.5 Formalizing our approach to recurrence equations

So far, our approach to solving recurrence equations has been based on intuition, and we’ve not given a lot of explanation for why the solutions we’ve given have been the general solution. In this section, we endeavor to remedy this. Some familiarity with the language of linear algebra will be useful for the remainder of this section, but it is not essential.
Our techniques for solving recurrence equations have their roots in a fundamentally important concept in mathematics, the notion of a vector space. Recall that a vector space
 1 
To be more complete, we should say that we are talking about a vector space over the field of real numbers, but in our course, these are the only kind of vector spaces we will consider. For this reason, we just use the short phrase “vector space”.
consists of a set \(V\) of elements called vectors; in addition, there is a binary operation called addition with the sum of vectors \(x\) and \(y\) denoted by \(x+y\text{;}\) furthermore, there is an operation called scalar multiplication which combines a scalar (real number) \(\alpha\) and a vector \(x\) to form a product denoted \(\alpha x\text{.}\) These operations satisfy the following properties:
  1. \(x+y=y+x\) for every \(x,y,\in V\text{.}\)
  2. \(x+(y+z) = (x+y)+z\text{,}\) for every \(x,y,z\in V\text{.}\)
  3. There is a vector called zero and denoted \(0\) so that \(x+0=x\) for every \(x\in V\text{.}\) Note: We are again overloading an operator and using the symbol \(0\) for something other than a number.
  4. For every element \(x\in V\text{,}\) there is an element \(y\in V\text{,}\) called the additive inverse of \(x\) and denoted \(-x\) so that \(x+(-x)=0\text{.}\) This property enables us to define subtraction, i.e., \(x-y= x+(-y)\text{.}\)
  5. \(1x=x\) for every \(x\in X\text{.}\)
  6. \(\alpha(\beta x) = (\alpha\beta)x\text{,}\) for every \(\alpha,\beta\in\reals\) and every \(x\in V\text{.}\)
  7. \(\alpha(x+y)=\alpha x + \alpha y\) for every \(\alpha\in\reals\) and every \(x,y\in V\text{.}\)
  8. \((\alpha +\beta) x = \alpha x + \beta x\text{,}\) for every \(\alpha,\beta\in\reals\) and every \(x\in V\text{.}\)
When \(V\) is a vector space, a function \(\phi\colon V\rightarrow V\) is called an linear operator, or just operator for short, when \(\phi(x+y)=\phi(x)+\phi(y)\) and \(\phi(\alpha x)=\alpha\phi(x)\text{.}\) When \(\phi\colon V\rightarrow V\) is an operator, it is customary to write \(\phi x\) rather than \(\phi(x)\text{,}\) saving a set of parentheses. The set of all operators over a vector space \(V\) is itself a vector space with addition defined by \((\phi+\rho)x = \phi x +\rho x\) and scalar multiplication by \((\alpha\phi)x=\alpha(\phi x)\text{.}\)
In this chapter, we focus on the real vector space \(V\) consisting of all functions of the form \(f\colon\ints\rightarrow\reals\text{.}\) Addition is defined by \((f+g)(n)= f(n)+g(n)\) and scalar multiplication is defined by \((\alpha f)(n)=\alpha(f(n))\text{.}\)

Subsection 9.5.1 The Principal Theorem

Here is the basic theorem about solving recurrence equations (stated in terms of advancement operator equations)—and while we won’t prove the full result, we will provide enough of an outline where it shouldn’t be too difficult to fill in the missing details.
The conclusion that the set \(W\) of all solutions is a subspace of \(V\) is immediate, since
\begin{equation*} p(A)(f+g)=p(A)f+p(A)g\quad\text{ and } \quad p(a)(\alpha f)=\alpha p(A)(f). \end{equation*}
What takes a bit of work is to show that \(W\) is a \(k\)-dimensional subspace. But once this is done, then to solve the advancement operator equation given in the form of Theorem 9.18, it suffices to find a basis for the vector space \(W\text{.}\) Every solution is just a linear combination of basis vectors. In the next several subsections, we outline how this goal can be achieved.

Subsection 9.5.2 The Starting Case

The development proceeds by induction (surprise!) with the case \(k=1\) being the base case. In this case, we study a simple equation of the form \((c_0A+c_1)f=0\text{.}\) Dividing by \(c_0\) and rewriting using subtraction rather than addition, it is clear that we are just talking about an equation of the form \((A-r)f=0\) where \(r\neq0\text{.}\)

Proof.

We first show that \(f(n)=cr^n\) for every \(n\ge0\text{,}\) by induction on \(n\text{.}\) The base case is trivial since \(c=f(0) = cr^0\text{.}\) Now suppose that \(f(k)=cr^k\) for some non-negative integer \(k\text{.}\) Then \((A-r)f=0\) implies that \(f(k+1)-rf(k)=0\text{,}\) i.e.,
\begin{equation*} f(k+1)=rf(k)= rcr^k=cr^{k+1}. \end{equation*}
A very similar argument shows that \(f(-n) = cr^{-n}\) for every \(n\le0\text{.}\)

Proof.

Let \(f\) be a solution of (9.5.2), and let \(f_1=f-f_0\text{.}\) Then
\begin{equation*} p(A)f_1 = p(A)(f-f_0)=p(A)f-p(A)f_0=g-g=0. \end{equation*}
This implies that \(f_1\in W\) and that \(f=f_0+f_1\) so that all solutions to (9.5.2) do in fact have the desired form.
Using the preceding two results, we can now provide an outline of the inductive step in the proof of Theorem 9.18, at least in the case where the polynomial in the advancement operator has distinct roots.

Proof.

The case \(k=1\) is Lemma 9.19. Now suppose we have established the theorem for some positive integer \(m\) and consider the case \(k=m+1\text{.}\) Rewrite (9.5.4) as
\begin{equation*} (A-r_1)(A-r_2)\dots(A-r_m)[(A-r_{m+1})f]=0. \end{equation*}
By the inductive hypothesis, it follows that if \(f\) is a solution to (9.5.4), then \(f\) is also a solution to the nonhomogeneous equation
\begin{equation} (A-r_{m+1})f=d_1r_1^n+d_2r_2^n+\dots+d_mr_m^n.\tag{9.5.5} \end{equation}
To find a particular solution \(f_0\) to (9.5.5), we look for a solution having the form
\begin{equation} f_0(n)= c_1 r_1^n+c_2 r_2^n+\dots+c_m r_m^n.\tag{9.5.6} \end{equation}
On the other hand, a simple calculation shows that for each \(i=1,2,\dots,m\text{,}\) we have
\begin{equation*} (A-r_{m+1})c_i r_i^n=c_i r_i^{n+1}-r_{m+1}c_i r_i^n=c_i (r_i-r_{m+1})r_i^n, \end{equation*}
so it suffices to choose \(c_i\) so that \(c_i(r_i-r_{m+1})=d_i\text{,}\) for each \(i=1,2,\dots,m\text{.}\) This can be done since \(r_{m+1}\) is distinct from \(r_i\) for \(i=1,2,\dots m\text{.}\)
Now we have a particular solution \(f_0(n)=\sum_{i=1}^{m} c_i r_i^n\text{.}\) Next we consider the corresponding homogeneous equation \((A-r_{m+1})f=0\text{.}\) The general solution to this equation has the form \(f_1(n)=c_{m+1}r_{m+1}^n\text{.}\) It follows that every solution to the original equation has the form
\begin{equation*} f(n)=f_0(n)+f_1(n) = c_1r_1^n+c_2r_2^n+\dots+c_m r_m^n+cr_{m+1}^n, \end{equation*}
which is exactly what we want!

Subsection 9.5.3 Repeated Roots

It is straightforward to modify the proof given in the preceding section to obtain the following result. We leave the details as an exercise.

Subsection 9.5.4 The General Case

Combining the results in the preceding sections, we can quickly write the general solution of any homogeneous equation of the form \(p(A)f=0\) provided we can factor the polynomial \(p(A)\text{.}\) Note that in general, this solution takes us into the field of complex numbers, since the roots of a polynomial with real coefficients are sometimes complex numbers—with non-zero imaginary parts.
We close this section with one more example to illustrate how quickly we can read off the general solution of a homogeneous advancement operator equation \(p(A)f=0\text{,}\) provided that \(p(A)\) is factored.

Example 9.23.

Consider the advancement operator equation
\begin{equation*} (A-1)^5(A+1)^3(A-3)^2(A+8)(A-9)^4f=0. \end{equation*}
Then every solution has the following form
\begin{align*} f(n)=\amp c_1+c_2n+c_3n^2+c_4n^3+c_5n^4\\ \amp +c_6(-1)^n+c_7n(-1)^n+c_8n^2(-1)^n\\ \amp +c_93^n+c_{10}n3^n\\ \amp +c_{11}(-8)^n\\ \amp +c_{12}9^n +c_{13}n 9^n+c_{14}n^2 9^n +c_{15}n^39^n. \end{align*}
You have attempted of activities on this page.
PrevTopNext