Which is a linear and homogeneous recurrence?

Question

Which of the following choices is a linear and homogenous recurrence?

$1)$ $A_n = A_{n-1} + 4A_{n-2} + 3n$

$2)$ $A_n = n + 1$

$3)$ $A_n = (A_{n-1})^2$

$4)$ $A_n = 5A_{n-1} + A_{n-2} + 3A_{n-3}$

Answer 1

What is a linear homogeneous recurrence relation?

It is an equation of the form: $A_0a_n + A_1a_{n-1} + A_2a_{n-2} + ... + A_ka_{n-k} = 0$

Indeed, the equation above is of order k.

For it to be linear, there should be no powers greater than $1$ lying around the recurrence relation terms. It is easy to verify this for your equations.

Now, important to note is the right-hand side of the equation. Homogeneous recurrence relations simply are equations which have all terms which define the recurrence relation on one side and on the other side there is only $0$, ergo, the recurrence relation equates to $0$. Non-homogeneous recurrence relations equate to a function $f(n)$ and not to $0$. Try shift the terms of the equations around and see what you get.

What does this tell you about the homogeneity of the equations you have been given?