# Linear Homogeneous Recurrence Relations and Inhomogenous Recurrence Relations

I'm having some difficulty understanding 'Linear Homogeneous Recurrence Relations' and 'Inhomogeneous Recurrence Relations', the notes that we've been given in our discrete mathematics class seem to be very sparse in terms of listing each step taken to achieve the answer and this makes it incredibly hard for people like myself who are not of a maths background to understand (I'm a computer science student, not a maths student) and I guess my main problem is that I don't understand the notes, as they some to jump steps due to assumed maths knowledge and this is troubling for me coming from a purely computer science background.

I was wondering if somebody could write out the steps in order to achieve the answers for these types of questions?

I've searched around on youtube and google on guides of how to do them, but they all differ slightly from the one's that we are supposed to learn, and I don't want to learn the wrong thing. I'm not sure if maybe my lecturer has called it something slightly different, but if somebody could help me out, that'd be great.

An example question in the notes for Linear Homogeneous Recurrence Relations is:

1. Find the solution of: with

And an example of Inhomogeneous Recurrence Relations would be:

2. Find a particular solution of:

Here is a second example for a more complicated linear homogeneous recurrence relation:

3. Find the solution: $a_{n} = a_{n-1} + a_{n-2}$ with $a_{0} = 0 \ and \ a_{1} = 1$

The lecturer came up with the general solution of $a_{n} = c\left ( \frac{1+\sqrt{5}}{2} \right )^{n} + d\left ( \frac{1+\sqrt{5}}{2} \right )^{n}$

And I just can't see how he got here, is there some way that he has worked this out, or is it pure deduction?

-

Are you familiar with differential equations? Solving linear recurrences is the same as solving linear differential equations, essentially. Linear recurrences (ie., difference equations) are discrete differential equations.

So for $a_{n} = 4a_{n-1} - 3a_{n-2}$, we start by setting up our characteristic polynomial: $\lambda^{2} - 4\lambda + 3 = 0$. You then solve for $\lambda$, getting solutions $\lambda = 1, 3$. And so your general form equation $a_{n} = c_{1}(\lambda_{1})^{n} + c_{2}(\lambda_{2})^{n}$.

To set up the characteristic polynomial, you look at the difference of the indices. So for $a_{n}$, we see indices $n, n-1, n-2$. Clearly there is a difference of two between the largest and smallest index. So we have a quadratic. The largest indexed term has the largest power. So $a_{n} \to \lambda^{2}$, $4a_{n-1} \to 4\lambda$, and $-3a_{n-2} \to -3$. Do you see how I got that?

So $a_{n} = c_{1} + c_{2}3^{n}$. Then plug in your constraints and solve for $c_{1}$ and $c_{2}$.

Now for your example with Fibonacci, we have $a_{n} = a_{n-1} + a_{n-2}$, we have another quadratic. Do you see why? So $a_{n} \to \lambda^{2}$, $a_{n-1} \to \lambda$, $a_{n-2} \to 1$. And so our characteristic polynomial is $\lambda^{2} - \lambda - 1 = 0$. Solve for $\lambda$, which gives you two distinct roots $\lambda_{1}, \lambda_{2}$, then plug in: $a_{n} = c_{1} \lambda_{1}^{n} + c_{2}\lambda_{2}^{n}$ and solve the system of equations from your initial conditions.

Now for a first order non-homogenous recurrence of the form $a_{n} = ra_{n-1} + c$, we get a solution of the form $a_{n} = kr^{n} + c \frac{r^{n}-1}{r -1 }$ for $r \neq 1$. If $r = 1$, we get $a_{n} = k + cn$.

The constant $k$ is what we solve for based on the initial conditions.

-
I will edit my post to add more about the homogenous solution. – ml0105 Mar 31 '14 at 21:49
I've updated my post. Please let me know if you need further clarification. Hope this helps some! – ml0105 Mar 31 '14 at 21:55
The solutions are actually $\frac{1 \pm \sqrt{5}}{2}$. The second term with the coefficient of $d$ should be $\frac{1 - \sqrt{5}}{2}$. He got them by solving the characteristic equation: $\lambda^{2} - \lambda - 1 = 0$, which I showed you how to set up in my edit above. – ml0105 Mar 31 '14 at 22:21
Are you familiar with solving a quadratic equation? To derive the roots, you go back to high school algebra. There is nothing fancy going on. :-) – ml0105 Mar 31 '14 at 22:23
I think you should brush up on your high school algebra, yes. Note you will be dealing with a quadratic only on a second-order linear recurrence. On a third-order linear recurrence, it would be a cubic. On a fourth-order linear recurrence, you'd have a quintic. And so on. If you know that you need to set the characteristic equation to $0$ and solve for $\lambda$, you could throw it at a graphing calculator or Wolfram Alpha. A basic understanding of the algebra is probably a good thing, though. Glad I've been able to help some! :-) – ml0105 Mar 31 '14 at 22:34

A linear recurrence equation for $a_r$ is one of the form: $$f_n(r) a_{r + n} + f_{n - 1}(r) a_{r + n - 1} + \cdots + f_0(r) a_r = g(r)$$ Here the $f_i(r)$ and $g(r)$ are arbitrary functions of $r$. If $f_n \ne 0$ and $f_0 \ne 0$, it is called of $n$-th order. If $g = 0$, it is called homogeneous.

If the $f_i$ are constants, it is a linear recurrence with constant coefficients, which are specially nice to handle.

Only general linear recurrences of the first order can be solved exactly, higher orders with non-constant coefficients can get quite hairy.

-