A question about the definition of linear recurrence relation

Question

I am reading the book "Discrete Mathematics and Its Applications". It showed me the definition of linear recurrence relation.

Why can "the right-hand side is a sum of previous terms of the sequence each multiplied by a function of $n$" conclude "it is linear"? And what is the function of $n$?

Answer 1

Linear in the context of recurrence relations just means that the nth term can be written as a linear/first degree polynomial in some of the previous terms.

I think your source missed out the word linear before "function of n".

Think of each term, like $a_{n-1}$, as x. So since its linear, like $ax+b$, we're going to have constant coefficients, $c_i$, for the $a_{n-i}$.

I was thinking you might have another constant at the end (not a coefficient) but then it can still be written in the form from your textbook; see Marcus Andrew's answer to this question.

Answer 2

The reason why this kind of equation is called linear is for the same reason that differential equations of the form $a_0(x) y(x) + a_1(x) y'(x) + \ldots + a_n(x) y^{(n)}(x) = b(x)$ are called linear differential equations - because they are linear in all of the $y$ terms, meaning that if you ignore the $x$ part you just have the various derivatives of $y$ being multiplied by things that don't depend on $y$, then added together. This is important because the derivative operator is itself linear in the sense that $\frac{d}{dx}(ay + bz) = a \frac{dy}{dx} + b \frac{dz}{dx}$, assuming that $a$ and $b$ are constants.

In a recurrence relation, instead of derivatives you have differences of terms - you could write a linear recurrence as $c_0'(n) a_n + c_1'(n) \Delta a_n + \ldots + c_k'(n) \Delta^{n-k} a_n = b(n)$, where $\Delta a_n = a_n - a_{n - 1}$. Then if $c_i'(n) = c'_i$ are constants, and $b(n) = 0$, you'll get the equation given in your definition once you relate the $c_i$ and $c'_i$ appropriately.