# What are linear homogeneous and non-homoegenous recurrence relations?

According to my book, linear homogeneous of order k is expressed this way: $$A_0a_n+A_1a_{n-1}+A_2a_{n-2}+\cdots+A_ka_{n-k}=0$$ While a linear non-homoegeous of order k is this way: $$A_0a_n+A_1a_{n-1}+A_2a_{n-2}+\cdots+A_ka_{n-k}=f(n)$$

I hardly understand what is that supposed to mean. There is not much explanation. At first, I though that linear homogeneous were equalities to $0$ while linear non-homogenous were equalities to something else.

Well, I was wrong because later the book says that the succession defined by $c_n=c_{n-1}+4c_{n-3}$ is linear homogeneous of order 3.

Can you give me a better explanation?

-
Well, you can see the equality as $c_n-c_{n-1}-4c_{n-3}=0$. –  ՃՃՃ Nov 28 '12 at 4:27
the example you gave, when all terms are brought on one side, they are equal to 0 and hence homogeneous –  Bhargav Nov 28 '12 at 4:28
... Ah, you're right. So is that the case? Are homogeneous equations those that equal to 0? –  Zol Tun Kul Nov 28 '12 at 4:30

## 1 Answer

You’re correct in thinking that the difference between homogeneous and non-homogeneous recurrences is the difference between equality to $0$ and equality to something else, but you have to put the recurrence into standard form first. For a linear recurrence, standard form has on one side all of the terms that are constant multiples of terms of the sequence being defined, and it has everything else on the other side.

If you rearrange the recurrence $c_n=c_{n-1}+4c_{n-3}$ into standard form, as used in the definitions, you get

$$c_n-c_{n-1}-4c_{n-3}=0\;,$$

which indeed has $0$ on the righthand side. If the recurrence had been $c_n=c_{n-1}+4c_{n-3}+2n$, say, then the rearranged recurrence would have been

$$c_n-c_{n-1}-4c_{n-3}=2n\;,$$

with a non-zero term on the righthand side, and would therefore have been non-homogeneous.

-