Last modified: September 01, 2023

This article is written in: 🇺🇸

Difference Equation

A difference equation (also known as a recurrence relation) defines each term of a sequence based on previous terms. In some cases, the general term of a sequence is given explicitly (e.g., $a_n=3n+2$, resulting in the sequence $5,8,11,\dots$). However, more commonly, a difference equation provides a relationship between terms.

For example:

$$a_n=4a_{n-1}-5a_{n-2}$$

is a second-order difference equation because it relates $a_n$ to the two previous terms $a_{n-1}$ and $a_{n-2}$.

Solving Difference Equations

To solve a difference equation, we often look for a solution of the form:

$$a_n={\lambda }^n$$

This assumes a solution structure where each term is proportional to the previous term by some factor $\lambda$.

Example:

For the difference equation:

$$a_n=4a_{n-1}-5a_{n-2}$$

Substitute $a_n={\lambda }^n$ into the equation:

$${\lambda }^n=4{\lambda }^{n-1}-5{\lambda }^{n-2}$$

Dividing both sides by ${\lambda }^{n-2}$, we get the characteristic equation:

$${\lambda }^2-4\lambda +5=0$$

This is a quadratic equation. Solving for $\lambda$, we get the roots:

$$\lambda =2,\lambda =3$$

Thus, the general solution to the difference equation is:

$$a_n=c_1{2}^n+c_2{3}^n$$

where $c_1$ and $c_2$ are constants determined by the initial conditions.

Example: Solving with Initial Conditions

Given the initial conditions $a_0=4$ and $a_1=10$, we can solve for $c_1$ and $c_2$.

At $n=0$:

$$a_0=c_1{2}^0+c_2{3}^0=c_1+c_2=4$$

At $n=1$:

$$a_1=c_1{2}^1+c_2{3}^1=2c_1+3c_2=10$$

Solving this system of equations:

$$\begin{array}{cc}{c}_1+c_2& =4\\ 2c_1+3c_2& =10\end{array}$$

We find:

$$c_1=2,c_2=2$$

Thus, the solution to the difference equation is:

$$a_n=2\cdot 2^n+2\cdot 3^n$$

Higher-Order Difference Equations

A $k$-th order difference equation has the form:

$$a_n={\beta }_1{a}_{n-1}+{\beta }_2{a}_{n-2}+\cdots +{\beta }_k{a}_{n-k}$$

The characteristic equation for such a difference equation is:

$${\lambda }^k-{\beta }_1{\lambda }^{k-1}-\cdots -{\beta }_k=0$$

Once we find the $k$ roots ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_k$, the general solution is:

$$a_n=c_1{\lambda }_1^n+c_2{\lambda }_2^n+\cdots +c_k{\lambda }_k^n$$

The constants $c_1,c_2,\dots ,c_k$ are determined by the initial conditions.

Example: Fibonacci Sequence

The Fibonacci sequence is a classic example of a difference equation:

$$a_n=a_{n-1}+a_{n-2}$$

with initial conditions $a_0=2$ and $a_1=3$.

The characteristic equation is:

$${\lambda }^2-\lambda -1=0$$

Solving this quadratic equation:

$${\lambda }_1=\frac{1-\sqrt{5}}{2},{\lambda }_2=\frac{1+\sqrt{5}}{2}$$

Thus, the general solution is:

$$a_n=c_1{\left(\frac{1-\sqrt{5}}{2}\right)}^n+c_2{\left(\frac{1+\sqrt{5}}{2}\right)}^n$$

Using the initial conditions:

$$c_1+c_2=2$$

$$c_1\left(\frac{1-\sqrt{5}}{2}\right)+c_2\left(\frac{1+\sqrt{5}}{2}\right)=3$$

Solving for $c_1$ and $c_2$, we find:

$$c_1=\frac{3-\sqrt{5}}{2},c_2=\frac{3+\sqrt{5}}{2}$$

Thus, the general term of the Fibonacci sequence is:

$$a_n=\frac{1}{\sqrt{5}}({\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n)$$

Relation to Differential Equations

A $k$-th order linear ordinary differential equation has a similar form to the $k$-th order difference equation:

$$y^{\left(k\right)}={\beta }_1{y}^{(k-1)}+\cdots +{\beta }_{k}y$$

The solution for the differential equation is found using the same characteristic equation:

$${\lambda }^k-{\beta }_1{\lambda }^{k-1}-\cdots -{\beta }_k=0$$

Once the roots are found, the general solution is expressed as a sum of exponentials, analogous to the powers of $\lambda$ in the difference equation solution.