This site is supported by donations to The OEIS Foundation.

# Recurrence relations with constant coefficients

(Redirected from Linear recurrence relations with constant coefficients)

A recurrence relation with constant coefficients of degree ${\displaystyle \scriptstyle d\,}$ is an equation of the form

${\displaystyle (...)\,}$

## Linear recurrence relations with constant coefficients

### Homogeneous linear recurrence relations with constant coefficients

An order ${\displaystyle \scriptstyle k\,}$ homogeneous linear recurrence relation with constant coefficients is an equation of the form

${\displaystyle \sum _{i=0}^{k}c_{i}\,a(n-i)=c_{0}\,a(n)+c_{1}\,a(n-1)+c_{2}\,a(n-2)+\cdots +c_{k}\,a(n-k)=0,\,}$

where the ${\displaystyle \scriptstyle k\,}$ coefficients ${\displaystyle \scriptstyle c_{i}\,(\forall i)\,}$ are constants.

### Nonhomogeneous linear recurrence relations with constant coefficients

An order ${\displaystyle \scriptstyle k\,}$ nonhomogeneous linear recurrence relation with constant coefficients is an equation of the form

${\displaystyle \left(\sum _{i=0}^{k}c_{i}\,a(n-i)\right)+f(n)={\Bigg (}c_{0}\,a(n)+c_{1}\,a(n-1)+c_{2}\,a(n-2)+\cdots +c_{k}\,a(n-k){\Bigg )}+f(n)=0,\,}$

where ${\displaystyle \scriptstyle f(n)\,\neq \,0\,}$ and the ${\displaystyle \scriptstyle k\,}$ coefficients ${\displaystyle \scriptstyle c_{i}\,(\forall i)\,}$ are constants.

## Quadratic recurrence relations with constant coefficients

(...)

(...)

### Bilinear recurrence relations with constant coefficients

#### Homogeneous bilinear recurrence relations with constant coefficients

A homogeneous bilinear recurrence relation with constant coefficients is an equation of the form

${\displaystyle \sum _{i=0}^{\lfloor k/2\rfloor }d_{i}\,a(n-i)\,a(n-k+i)=0,\,}$

where the ${\displaystyle \scriptstyle 1+{\lfloor k/2\rfloor }\,}$ coefficients ${\displaystyle \scriptstyle d_{i}\,(\forall i)\,}$ are constants. (Note that there are no squared ${\displaystyle \scriptstyle a(j)\,(\forall j)\,}$.)

#### Nonhomogeneous bilinear recurrence relations with constant coefficients

A nonhomogeneous bilinear recurrence relation with constant coefficients is an equation of the form

${\displaystyle \sum _{i=0}^{\lfloor k/2\rfloor }d_{i}\,a(n-i)\,a(n-k+i)+\left(\sum _{i=0}^{k}c_{i}\,a(n-i)\right)+f(n)=0,\,}$

where either ${\displaystyle \scriptstyle \sum _{i=0}^{k}|c_{i}|\,\neq \,0\,}$ or ${\displaystyle \scriptstyle f(n)\,\neq \,0\,}$ and the ${\displaystyle \scriptstyle 1+{\lfloor k/2\rfloor }\,}$ coefficients ${\displaystyle \scriptstyle d_{i}\,(\forall i)\,}$ and ${\displaystyle \scriptstyle c_{i}\,(\forall i)\,}$ and are constants. (Note that there are no squared ${\displaystyle \scriptstyle a(j)\,(\forall j)\,}$.)