# Solving linear homogenuous recurrence relation

I am learning about recurrence relations from a discrete math text book by Grimaldi. An introductory example(A second degree homogeneous recurrence relation), proceeds as follows

After determining the two possible solutions to the recurrence relation, $a_n = 2^n$ and $a_n = (-3)^n$ I don't understand why the author goes on to say that $a_n = c_1 2^n + c_2(-3)^n$ is the general solution. Why does he add the individual solutions obtained to form the general solution. Aren't $c_1 2^n$ and $c_2(-3)^n$ themselves the general solutions?

Does this have to do with the "linearly independent solutions" he talks about in the previous line? Could someone throw more light on this?

-

This is clearest when viewed from the point of view of linear algebra.

Let $V=\Bbb C^{\Bbb N}$, the vector space of infinite sequences of complex numbers with componentwise addition and scalar multiplication. Consider the $r$-th order homogeneous recurrence

$$x_n=a_1x_{n-1}+a_2x_{n-2}+\ldots+a_rx_{n-r}\tag{1}$$

with constant coefficients. A sequence $\alpha=\langle\alpha_n:n\in\Bbb N\rangle\in V$ satisfies $(1)$ if and only if

$$\alpha_n=a_1\alpha_{n-1}+a_2\alpha_{n-2}+\ldots+a_r\alpha_{n-r}$$

for all $n\ge r$. If $\alpha\in V$ satisfies $(1)$, we call $\alpha$ a solution to $(1)$. The set of solutions to $(1)$ is a subspace of $V$.

Proposition. Let $H=\{\alpha\in V:\alpha\text{ satisfies }(1)\}$; then $H$ is a subspace of $V$.

Proof. The proof is entirely straightforward. If $\alpha,\beta\in H$ and $b,c\in\Bbb C$, let $\gamma=b\alpha+c\beta$. Then for each $n\ge r$ we have

\begin{align*} \gamma_n&=b\alpha_n+c\beta_n\\ &=b(a_1\alpha_{n-1}+\ldots+a_r\alpha_{n-r})+c(a_1\beta_{n-1}+\ldots+a_r\beta_{n-r})\\ &=a_1(b\alpha_{n-1}+c\beta_{n-1})+\ldots+a_r(b\alpha_{n-r}+c\beta_{n-r})\\ &=a_1\gamma_{n-1}+\ldots+a_r\gamma_{n-r}\;, \end{align*}

and hence $\gamma\in H$. $\dashv$

It turns out that $\dim H=r$. (This isn’t very hard to show, but doing so would take me further afield than is really necessary.) $H$ therefore has a basis $B=\{\beta^1,\dots,\beta^r\}$ (where the superscripts are just indices, not exponents). Thus, each $\alpha\in H$ can be written uniquely in the form

$$\alpha=b_1\beta^1+b_2\beta^2+\ldots+b_r\beta^r$$

for some $b_1,b_2,\dots,b_r\in\Bbb C$. The technique that you’re learning with the characteristic equation is a way to find such a basis.

In your particular problem $r=2$, and you’ve found that the sequences $\alpha$ and $\beta$ given by $\alpha_n=2^n$ and $\beta_n=(-3)^n$ are in $H$. It’s also clear that they are linearly independent: neither is a scalar multiple of the other. Since in this case $\dim H=2$, $\{\alpha,\beta\}$ must be a basis for $H$, and therefore every solution $\gamma$ to your recurrence must have the form $\gamma=a\alpha+b\beta$, i.e.,

$$\gamma_n=a\alpha_n+b\beta_n=a2^n+b(-3)^n\quad\text{ for all }n\in\Bbb N\;,\tag{2}$$

for some constants $a$ and $b$. The initial conditions are then used to pin down the specific values of $a$ and $b$. Since every linear combination of $\alpha$ and $\beta$ is a solution of the recurrence, not just the simple multiples $a\alpha$ and $b\beta$ of the solutions $\alpha$ and $\beta$, there’s no guarantee that your initial conditions will be satisfied by one of those simple multiples.

A simple analogy: every vector in $\Bbb R^2$ is a linear combination of the basis vectors $\langle 1,0\rangle$ and $\langle 1,1\rangle$, but if you need one whose first component is $0$, you can’t get it as a scalar multiple of $\langle 1,0\rangle$ or of $\langle 1,1\rangle$: you have to use a linear combination of both basis vectors.

-

The two sequences you've identified represent a class of functions that will satisfy the recurrence relation, so this is a general solution to the relation. Selecting particular values for the coefficients ($c_1$ and $c_2$) will give you a particular solution to the recurrence relation. Any particular solution depends on initial values. You need to determine as many initial values as you have coefficients in your general solution to establish a particular solution.

Imagine you are running an experiment on a system that conforms to the recurrence relationship. When you start the experiment, you will initialize some parameters and let the experiment run. The value of the initialized parameters will determine precisely what the system will do. If you want to analyze the situation and calculate what the system will do, first you have to solve the recurrence relation for the general solution, then you apply the initial conditions of the experiment to calculate a particular solution. This calculation will determine the values of $c_1$ and $c_2$. Once $c_1$ and $c_2$ are identified, you can calculate exactly the results of the experiment.

In your case, assume in the experiment, $a[0] = 2$, and $a[1] =-1$. What values of $c_1$ and $c_2$ satisfy this? The answer provides one particular solution to the relation.

-
I meant to ask why does the author add the two individual solutions($c_12^n$ and $c_2(-3)^n$). Aren't they solutions to the recurrence relations by themselves? –  Abhijith Jan 4 '13 at 14:25
Each sequence is a solution to the recursion relation by itself; however by selecting one sequence you are forcing one of the coefficients (c1,c2) to 0 which eliminates a whole class of possible particular solutions. The general solution must include all possible particular solutions. Since this is a linear relationship, the general solution is the sum of all linearly independent sequences that satisfy the relation. You will find that the order of the recursion relationship determines how many linearly independent sequences make up a the solution set. –  Bruce Zenone Jan 4 '13 at 15:31