---
tag: 8Y28JQB0Q5
kind: concept
name: Homogeneous and inhomogeneous linear recurrences
msc: [39A06, 39A05]
specializes: [0FYX44GP92]
sources:
  - url: https://en.wikipedia.org/wiki/Linear_recurrence_with_constant_coefficients
---

## 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.

## Explanations

### L1 human

The rule $u_{n+2} = u_{n+1} + u_n$ only mixes earlier terms, so it is homogeneous.
The rule $u_{n+1} = 2 u_n + 1$ adds a fixed amount at each step, so it is inhomogeneous.
For a homogeneous rule, the all-zero sequence is always a solution, and sums and multiples of solutions are again solutions.
For an inhomogeneous rule this fails: the zero sequence does not satisfy $u_{n+1} = 2 u_n + 1$.
Its solutions are $u_n = c\, 2^n - 1$: one particular solution $-1$, plus any solution $c\, 2^n$ of $u_{n+1} = 2 u_n$.