8
$\begingroup$

According to my book, a linear homogeneous recurrence 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-homogeneous recurrence 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 that is supposed to mean. There is not much explanation. At first, I thought that linear homogeneous were equalities to $0$ while linear non-homogeneous 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?

  • 0
    ... Ah, you're right. So is that the case? Are homogeneous equations those that equal to 0?2012-11-28

1 Answers 1

12

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.