Recurrence relation (linear, second-order, constant coefficients)

Question

Q1. Find the general solution to the difference equation

$$ a_{n} - 4a_{n-1} + 3a_{n-2} = 6 $$

Q2. Solve the difference equation

$$ a_{n} - a_{n-1} - 2a_{n-2} = 0, a_0 = 2, a_1 = 4 $$

I am completely lost in solving recurrence relation questions. Can anyone guide me in steps to solve the following 2 questions?

Answer 1

The general approach to solving recurrence relations is the following: given a recurrence relation $$a_n+\alpha_1a_{n-1}+...+\alpha_ra_{n-r}=\beta(n) \; .$$

I) First you solve the homogeneous part $a_n^{(h)}+\alpha_1a_{n-1}^{(h)}+...+\alpha_ra_{n-r}^{(h)}=0$:
$\quad$ a) By solving the characteristic equation: $x^r+\alpha_1x^{r-1}+...+\alpha_r=0$ you get $x_1,...,x_r$ the roots of the equation.
$\quad$ b) If all $x_1,...,x_r$ are different then the $a_n^{(h)}=A_1x_1^n+...+A_rx_r^n$, where $A_1,...,A_r$ are the coefficients.
$\quad$ c) If you have a root $x_j$ is of multiplicity $k$ then you replace the term $A_jx_j^n$ with $(B_1n^{k-1}+...+B_k)x_j^n$

II) Now you find a particular solution to the equation $a_n^{(p)}+\alpha_1a_{n-1}^{(p)}+...+\alpha_ra_{n-r}^{(p)}=\beta(n)$. Each $\beta(n)$ needs a different approch to guess $a_n^{(p)}$. For example, if $\beta(n)=k^nf(n)$, where $k$ is a number and $f(n)$ is a polynomial in $n$, then $a_n^{(p)}=k^nn^sg(n)$ where $k$ is the same $k$, $s$ is the multiplicity of $k$ as a root of the characteristic equation in the homogeneous part and $g(n)$ is a polynomial of the same degree as $f(n)$.

Finally, $a_n=a_n^{(h)}+a_n^{(p)}$

Answer 2

The general second order homogeneous linear recurrence/difference equation with constant coefficients

$$x_{n}+c_{1}x_{n-1}+c_{2}x_{n-2}=0\qquad (1)$$

has two fundamental solutions $(\lambda _{1}^{n})_{n\geq 0}$ and $(\lambda _{2}^{n})_{n\geq 0}$, where $\lambda _{1},\lambda _{2}$ are the two zeroes of the characteristic polynomial

$$\lambda ^{2}+c_{1}\lambda +c_{2}\qquad (2)$$

Let's confirm.

$$\begin{eqnarray*} \lambda _{1}^{n}+c_{1}\lambda _{1}^{n-1}+c_{2}\lambda _{1}^{n-2} &=&\lambda _{1}^{n-2}\left( \lambda _{1}^{2}+c_{1}\lambda _{1}+c_{2}\right) \equiv 0 \\ && \\ \lambda _{2}^{n}+c_{1}\lambda _{2}^{n-1}+c_{2}\lambda _{2}^{n-2} &=&\lambda _{2}^{n-2}\left( \lambda _{2}^{2}+c_{2}\lambda _{2}+c_{2}\right) \equiv 0 \end{eqnarray*}$$

If $\lambda _{1}\neq \lambda _{2}$ the general solution of $(1)$ is a linear combination of $\lambda _{1}^{n}$ and $\lambda _{2}^{n}$

$$x_{n}=A\lambda _{1}^{n}+B\lambda _{2}^{n}\qquad (3)$$

as you can confirm substituting $(3)$ in $(1)$. Let's apply this result to your second difference equation $a_{n}-a_{n-1}-2a_{n-2}=0$. The characteristic polynomial $\lambda ^{2}-\lambda -2$ has the zeroes $\lambda _{1}=-1,\lambda _{2}=2$.

Thus $(3)$ becomes

$$a_{n}=A(-1)^{n}+B2^{n}$$

The constants $A$ and $B$ are determined by using the initial conditions $a_{0}=2$, $a_{1}=4$.

---

Added: Determination of $A$ and $B$:

$$a_{0}=A(-1)^{0}+B2^{0}=A+B=2\Leftrightarrow B=2-A$$

Hence

$$a_{n}=A(-1)^{n}+\left( 2-A\right) 2^{n}$$

and

$$a_{1}=A(-1)^{1}+\left( 2-A\right) 2^{1}=-A+4-2A=-3A+4=4\Leftrightarrow A=0.$$

Since $A=0$ and $B=2-A=2$ the solution is

$$a_{n}=2\cdot 2^{n}=2^{n+1}\qquad n\geq 2$$

---

As for your first equation it is not homogenous because the RHS is not zero. For solving it, please see the explanation by Dennis Gulko in his answer.

Answer 3

Consider the recurrence relation for $n\ge 1$ given by \begin{equation} \tag{1} \label{1} A_{n+1}=\alpha A_n+\beta A_{n-1}+f_n, \end{equation} where $\alpha$ and $\beta$ are constants (not dependent on $n$), and $f_n$ is a given function of $n$. Eqn.~\eqref{1} is to be solved either for specified $A_0$, $A_1$, or two constraints of the form \begin{align}\tag{2}\label{2} \sum_{n=1}^{\infty} c_nA_n&=h_n, \\ \sum_{n=1}^{\infty} d_nA_n&=g_n. \end{align}

We can write Eqn.~\eqref{1} as \begin{equation} \tag{3} \label{3} \begin{bmatrix} A_{n+1} \\ A_n \end{bmatrix}=T\begin{bmatrix} A_n \\ A_{n-1} \end{bmatrix}+\begin{bmatrix} f_n \\ 0 \end{bmatrix}, \end{equation} where \begin{equation*} T=\begin{bmatrix} \alpha & \beta \\ 1 & 0 \end{bmatrix}. \end{equation*}

First consider the case where the eigenvalues of $T$ are distinct, and given by \begin{align} \tag{4} \label{4} \lambda_1&=\frac{\alpha-\sqrt{\alpha^2+4\beta}}{2}, \\ \lambda_2&=\frac{\alpha+\sqrt{\alpha^2+4\beta}}{2}. \end{align} We deal with the case of repeated eigenvalues where $\beta=-\alpha^2/4$, and $\lambda_1=\lambda_2=\alpha/2$ later by taking appropriate limits. Since the eigenvalues are distinct, $T$ is diagonalizable, and can be written as \begin{equation} \tag{5} \label{5} T=\lambda_1 P_1+\lambda_2 P_2, \end{equation} where $P_1$ and $P_2$ are projections given by \begin{align*} P_1&=\frac{T-\lambda_2 I}{\lambda_1-\lambda_2}, \\ P_2&=\frac{T-\lambda_1 I}{\lambda_2-\lambda_1}. \end{align*} Thus, we have \begin{equation} \tag{6} \label{6} T^n=\lambda_1^n P_1+\lambda_2^n P_2. \end{equation}

We now have \begin{align} \tag{7} \label{7} \begin{bmatrix} A_{n+1} \\ A_n \end{bmatrix}&=T^n\begin{bmatrix} A_1 \\ A_0 \end{bmatrix}+\sum_{k=1}^{n-1}T^{n-k}\begin{bmatrix} f_k \\ 0 \end{bmatrix} +\begin{bmatrix} f_n \\ 0 \end{bmatrix} \notag \\ &=(\lambda_1^n P_1+\lambda_2^n P_2)\begin{bmatrix} A_1 \\ A_0 \end{bmatrix}+\sum_{k=1}^{n-1}(\lambda_1^{n-k} P_1+\lambda_2^{n-k} P_2) \begin{bmatrix} f_k \\ 0 \end{bmatrix}+\begin{bmatrix} f_n \\ 0 \end{bmatrix}, \end{align} which leads to the explicit formula \begin{equation} \tag{8} \label{8} A_n=\frac{1}{\lambda_2-\lambda_1}\left[(\lambda_2^n-\lambda_1^n)A_1-\lambda_1\lambda_2\left(\lambda_2^{n-1}-\lambda_1^{n-1}\right)A_0 +\sum_{k=1}^{n-1} \left(\lambda_2^{n-k}-\lambda_1^{n-k}\right)f_k\right]. \end{equation} If $f_n=f_0$ is a constant, Eqn.~\eqref{8} simplifies to \begin{equation} \tag{9} \label{9} A_n=\frac{1}{\lambda_2-\lambda_1}\left[(\lambda_2^n-\lambda_1^n)A_1-\lambda_1\lambda_2\left(\lambda_2^{n-1}-\lambda_1^{n-1}\right)A_0 +\left(\frac{\lambda_2(\lambda_2^{n-1}-1)}{\lambda_2-1}-\frac{\lambda_1(\lambda_1^{n-1}-1)}{\lambda_1-1}\right)f_0\right]. \end{equation} If $\lambda_1=1$, say, then by taking the limit in the above equation, we get \begin{equation} \tag{10} \label{10} A_n=\frac{1}{\lambda_2-1}\left[(\lambda_2^n-1)A_1-\lambda_2\left(\lambda_2^{n-1}-1\right)A_0 +\left(\frac{\lambda_2(\lambda_2^{n-1}-1)}{\lambda_2-1}-(n-1)\right)f_0\right]. \end{equation} In case the constraints in Eqn.~\eqref{2} are imposed in place of prescribed values for $A_0$ and $A_1$, then we determine $A_0$ and $A_1$ by substituting the solution given by Eqn.~\eqref{8} into Eqns.~\eqref{2}.

The solution for the case where the eigenvalues of $T$ are repeated is obtained by taking the limit $\lambda_2\rightarrow \lambda_1$ in Eqn.~\eqref{8}, and setting $\lambda_1=\alpha/2$ as \begin{equation} \tag{11} \label{11} A_n=\left(\frac{\alpha}{2}\right)^{n-1}\left[nA_1-\frac{\alpha(n-1)A_0}{2}\right]+\sum_{k=1}^{n-1}(n-k)f_k\left(\frac{\alpha}{2}\right)^{n-k-1}. \end{equation} If $f_n=f_0$ is a constant, Eqn.~\eqref{11} simplifies to \begin{align*} A_n&=\left(\frac{\alpha}{2}\right)^{n-1}\left[nA_1-\frac{\alpha(n-1)A_0}{2}\right]+\frac{4\left[2^n+(n-1)\alpha^n-2n\alpha^{n-1}\right]f_0}{(\alpha-2)^22^n}, && (\alpha\ne 2), \\ &=nA_1-(n-1)A_0+\frac{n(n-1)f_0}{2}, && (\alpha=2). \end{align*}

As examples, consider the following:

1. The Fibonacci sequence defined by $A_{n+1}=A_n+A_{n-1}$ with $A_0=0$, $A_1=1$, so that $\alpha=1$, $\beta=1$, $\lambda_1=(1-\sqrt{5})/2$, $\lambda_2=(1+\sqrt{5})/2$, $f_n=0$, and \begin{equation*} A_n=\frac{\lambda_2^n-\lambda_1^n}{\lambda_2-\lambda_1}. \end{equation*}
2. The recurrence \begin{equation*} A_{n+1}=4A_n-4A_{n-1}+4^{n-1}, \end{equation*} with $A_0=0$, $A_1=1$, so that $\alpha=4$, $\beta=-4$, $\lambda_1=\lambda_2=2$, $f_n=4^{n-1}$. From Eqn.~\eqref{11}, we get \begin{equation*} A_n=n2^{n-1}+2^{n-2}(2^n-n-1). \end{equation*}
3. The solution to your Q1 is given by Eqn.~\eqref{10} with $\lambda_2=3$ and $f_0=6$.

The above procedure can obviously be generalized to higher-order recurrences, by considering the eigenvalues of $T$ to be distinct, and then deriving various subcases for repeated eigenvalues by taking appropriate limits as in the development above.

Answer 4

Simple, general way of disposing such equations is using generating functions. Define: $$ A(z) = \sum_{n \ge 0} a_n z^n $$ Write the recurrence so it hasn't subtractions in indices: $$ a_{n + 2} - 4 a_{n + 1} + 3 a_n = 6 $$ Multiply by $z^n$, sum over $n \ge 0$ an recognize the resulting terms: $$ \frac{A(z) - a_0 - a_1 z}{z^2} - 4 \frac{A(z) - a_0}{z} + 3 A(z) = 6 \frac{1}{1 - z} $$

Substituting your initial values, and solving for $A(z)$, writing that as partial fractions: $$ A(z) = \frac{3}{(1 - z)^3} + \frac{5}{2 (1 - z)} + \frac{5}{2 (1 - 3 z)} $$ Using the generalized binomial theorem you can read off the coefficients: \begin{align} a_n &= 3 \binom{-3}{n} (-1)^n + \frac{5}{2} + \frac{5}{2} \cdot 3^n \\ &= 3 \binom{n + 3 - 1}{3 - 1} + \frac{5}{2} + \frac{5}{2} \cdot 3^n \\ &= \frac{3 (n + 2) (n + 1)}{2} + \frac{5}{2} + \frac{5}{2} \cdot 3^n \\ &= \frac{5 \cdot 3^n + 3 n^2 + 9 n + 11}{2} \end{align} The other one I leave as a exercise for the gentle reader.