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?
Best Answer
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.