4
$\begingroup$

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?

  • 1
    For linear recurrence relations, one can get some insight but making the ansatz $a_n = \lambda^n$ and then figuring out which $\lambda$s fulfill the equation (then one can take an arbitrary linear combination of these solutions in order to get the initial conditions right).2011-05-05

3 Answers 3

7

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)}$

  • 0
    @liangteh: In addition to what user9325 said, you can check that the set of all sequences $a_n$ that obey to a homogeneous recurrence relation form a vector space over $\mathbb{C}$. Hence, the set of all solutions of a non-homogeneous recurrence relation forms an affine vector space.2011-05-05
3

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.

  • 0
    @liangteh: Do you still have doubts concerning Q1? The homogeneous equation has the solution $A3^n+B$.2011-05-06
1

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.