Homogeneous and inhomogeneous linear recurrences

Summary

A linear recurrence expresses a term of a sequence as a linear combination of earlier terms. It may also add an extra term that depends only on the index. It is homogeneous when this extra term is zero, and inhomogeneous otherwise. The solutions of a homogeneous recurrence form a vector space. The solutions of an inhomogeneous one form a translate of that space. So solving an inhomogeneous recurrence reduces to finding one particular solution and the solutions of the homogeneous one.