Homogeneous Recurrence Relation

This is section 7.4 in the book. We want to solve for homogeneous recurrence relation.

Definition Homogeneous recurrence relation is a recurrence of the form: $$ h_n = a_1 h_{n-1} + a_2h_{n-2} + \ldots + a_kh_{n-k} $$ Where $k$ and $a_i$'s are constants.

Definition The characteristic polynomial of the homogeneous linear recurrence: $$ \begin{align*} \frac{P(x)}{x^{n-k}} &= \frac{x^n - (a_1 x^{n-1} + a_2 x^{n-2} + \ldots + a_k x^{n-k})}{x^{n-k}}\ r(x) &= x^k - (a_1x^{k-1} + a_2x^{k-2} + \ldots + a_kx) \end{align*} $$ $r(x)$ is the characteristic polynomial of the homogeneous linear recurrence.

Actually, characteristic polynomial is very useful when we solve these recurrences. The root of characteristic equations gives us a hint of the solution. We will see this later.

There are some basic HRR we usually see:

The Fibonacci sequence: $f_n = f_{n-1} + f_{n-2}$
The factorial sequence: $f_n = nf_{n-1}$
The geometric sequence: $f_n = q h_{n-1}$

Theorem

Let $(h_i)_{i\ge0}$ be a sequence of numbers defined by the homogeneous recurrence relation

$$ h_n + a_1h_{n-1}+\cdots+a_kh_{n-k}=0, , (n \ge k) $$

of order $k$ and with initial values for $h_0, h_1,\ldots,h_{k-1}$.

Let $r(x) = x^k +a_1 x^{k-1}+a_2x^{k-2}+\cdots+a_k$ be the characteristic polynomial of this recurrence relation.

Then, the generating function of $(h_i)_{i\ge0}$ is given by $g(x) = p(x)/q(x)$, where $q(x) = x^k r(1/x)$ and

$$ p(x) = h_0 + (h_1+a_1h_0)x+(h_2+a_1h_1+a_2h_0)x^2+\cdots+(h_{k-1}+a_1h_{k-2}+\cdots+a_{k-1}h_0)x^{k-1} $$

$p(x)$ in another form:

$$ p(x) = \sum_{i = 0}^{k - 1}\left( \sum_{j = 0}^{i} a_jh_{i-j}\right)x^i $$

where we define $a_0 = 1$.

Note that this is slightly different from the previous definition, but this is still a homogeneous recurrence relations.

Proof is not given... I think just understanding this theorem's statement what matters.

Exercise

Find the general solution of the recurrence relation: $$ h_n = 2h_{n-1} + 2h_{n-2}, \quad(n \geq 2) $$ where $h_0 = 1$ and $h_1 = 3$.

Solution

We try: $h_n = q^n$ for some constant $q$. $$ \begin{align*} h_n = q^n &= 2q^{n-1} + 2q^{n-2}\ q^2 &= 2q + 2 && \text{this is the characteristic equation}\ q^2 &- 2q - 2 = 0 \ \implies \ & \begin{cases} q_1 = 1 + \sqrt 3\ q_2 = 1 - \sqrt 3 \end{cases}\ \end{align*} $$ This gives us a hint of how the general solution (closed form) of $h_n$ looks like: $$ h_n = c_1 (1 + \sqrt 3)^n + c_2 (1 - \sqrt3)^n $$ Then we find $c_1$ and $c_2$ by using our initial condition. I skip the calculation. The answer is: $$ h_n = (\frac{1}{2} + \frac{1}{3} \sqrt3)^n + (\frac{1}{2} - \frac{1}{3} \sqrt3)^n $$

Example

Find the general solution of the recurrence relation: $$ h_n = 4h_{n-1} - 4h_{n-2} $$ where $h_0 = 1, h_1 = 3$. Show that $h_c = c2^n$ is not a general solution of the given recurrence relation.

Solution

Just like the previous one, we first try: $h_n = q^n$. $$ \begin{align*} q^n &= 4q^{n-1} - 4q^{n-2}\ &q^2 - 4q + 4 = 0\ &(q-2)^2 = 0 \implies q = 2 \end{align*} $$ We can actually simplify this by just calculate the root of the characteristic equation.

Putting $q=2$ back to recurrence, we guess $h_n = 2^n$. Also, multiplying a constant $c$ everywhere gives us that it is possible to have $h_n = c \cdot 2^n$. But this gives us a contradiction it we try to satisfy $h_0 = 1, h_1 = 3$. Thus this trial fails.

Then, try: $h_n = n \cdot 2^n$. Goal: show that $h_n$ satisfies the recurrence relation.

In this case, we want to know if the following equivalence holds: $$ n \cdot 2^n \overset{?}{=} 4(n-1)2^{n-1} - 4 (n-2)2^{n-2} $$

We can try from the right side: $$ \begin{align*} &4(n-1)2^{n-1} - 4 (n-2)2^{n-2}\ &= 2^{n-2}\cdot \left( 8(n-1) - 4(n-2) \right)\ &= 2^{n-2}(8n-8-4n+8)\ &= 2^{n-2}(4n) = n \cdot 2^n = \text{left side} \end{align*} $$ Yes, our guess is valid! How about the first two terms? If we let $h_n = n2^n$, this implies $h_0 = 0, h_1 = 2$, then both failed. Then, observe that $h_n = c_1\cdot 2^n + c_2 \cdot n \cdot 2^n$ is also a solution of the recurrence relation $\forall c_1, c_2 \in \mathbb{R}$.

Why taking linear combination still holds?

We need: $$ \begin{cases} h_0 = 1 = c_1\ h_1 = 3 = c_1 \cdot 2 + c_2 \cdot 1 \cdot 2 \end{cases} \implies c_2 = \frac{1}{2} $$ Conclusion:

$h_n = 2^n + \frac{1}{2}n2^n$ is a solution to this recurrence relation. $\blacksquare$

About how do we deal with a double root:

In Brualdi's book page 237, it writes;

If, as in the preceding example, some characteristic root is repeated, we would like to find another solution associated with that root. The situation is similar to that which occurs in differential equations.

Well, I don't know how to solve for differential equations. I don't know how to solve for a differential equation, so I will try to clarify this using just the example we have seen. There are some confusing words that Brualdi used in the book. Here is my understanding:

For any equation, it can have multiple "solutions". But there is only one "general solution". The "general solution" can be the linear combination of linearly independent "solutions". Now, what are the "solutions"? I think solutions are all possible relations that satisfies our recurrence. In our case, we discovered that there are two possible solutions to the recurrence relation, but they all failed on the first two terms. But we can actually take the linear combination of them. Here is why: say we have two "solutions" at this point: $$ \begin{align*} &\begin{cases} a_n = q^n\ b_n = n \cdot q^n \end{cases} \quad \text{where $q$ is the root of the characteristic polynomial}\ &\implies\ &\begin{cases} a_n - q^n = 0\ bn - n \cdot q^n = 0 \end{cases} \implies \begin{cases} k_1(a_n - q^n) = 0\ k_2(bn - n \cdot q^n) = 0 \end{cases} \overset{\text{combine}}{\implies} k_1(a_n - q^n) + k_2(bn - n \cdot q^n) = 0 \end{align*} $$

In the last equation, we see why taking the linear combination won't affect the result. THIS IS HOMOGENEOUS, meaning the "right side" must be zero. Multiply by any constant won't change the recurrent relation, but it will only help us shif the expression to fit in the initial conditions.

Now, there is a more general theorem for what I have just discussed here.

Theorem

Let $H$ be the characteristic polynomial of a homogeneous linear recurrence. If $r$ is a root of $H(x)=0$ with multiplicity $k$, then

$$ r^n, nr^n, n^2r^n,\ldots,n^{k-1}r^n $$

are all solutions to the recurrence.

Proof

We first need some tools:

First tool: decomposition $$ P(x)=\left(x-q_1\right)^{i_1} \cdot\left(x-q_2\right)^{i_2} \cdots\left(x-q_d\right)^{i_d} $$ where $i_1+\cdots+i_d=k$, $i$'s are multiplicities. This decomposition is always possible.

Second Tool: Let $Q$ be a polynomial. Suppose that $(x-q)^i \mid Q(x)$, for some $i \geqslant 1$. Then, $(x-q)^{i-1} \mid Q^{\prime}(x)$ proof: $Q(x)=(x-q)^i \cdot P(x)$ for some polynomial $P(x)$. By product rule in calculus, we have: $$ \begin{aligned} Q^{\prime}(x) & =i(x-q)^{i-1} \cdot P(x)+(x-q)^i P^{\prime}(x) \ & =(x-q)^{i-1} \cdot \underbrace{\left( i P(x)+(x-q) P^{\prime}(x)\right)}_{\text {also a poly }} \ & \Rightarrow(x-q)^{i-1} \mid Q^{\prime}(x) \end{aligned} $$ Moreover, by applying these rules multiple times, we also have: $$ (x-q)^{i-j} \mid Q^{(j)}(x) \quad \forall j \leqslant i-1 $$

Corollary Let $Q$ be a polynomial. Then, if $r$ is a root of $Q$ with multiplicity $i$, then $Q^{(j)}(r)=0 \quad \forall j \leq i-1$

proof: by the second tool, we have: $$ Q^{(j)}(x)=(x-r)^{i-j} \cdot P_j(x) $$ for some polynomial $P_j$. Plug $x=r$, this gives us 0.

⚠️NOW, back to the proof of the theorem.

Consider $$ h_n=a_1 h_{n-1}+a_2 h_{n-2}+\cdots+a_k h_{n-k} $$

Which has characteristic polynomial: $$ Q(x) = x^n - a_1x^{n-1} - a_2x^{n-2} - \cdots - a_kx^{n-k} $$ We know that $Q$ has multiplicity $k$, then by the corollary, $Q^{(j)}(r)=0 \quad \forall j \leq i-1$.

If we expand $Q^{(j)}(r)$, we get: $$ Q^{(j)}(r) = c_1 nr^{n-1} + c_2 (n-1)r^{n-2} + \cdots + c_k(n-k)r^{n-k-1} $$ This implies:

$h_n = n \cdot r^{n-1}$ is a solution of the recurrent relation???????