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?

$\endgroup$
  • $\begingroup$ Re Q2, you could try to compute the first terms, to see if a pattern emerges. $\endgroup$ – Did May 5 '11 at 10:08
  • $\begingroup$ Don't you have a guide for that in your textbooks? Those are pretty standard. $\endgroup$ – Raskolnikov May 5 '11 at 10:10
  • $\begingroup$ @Raskolnikov I dont understand the examples on the textbook. $\endgroup$ – ilovetolearn May 5 '11 at 10:13
  • 1
    $\begingroup$ 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). $\endgroup$ – Fabian May 5 '11 at 10:13
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ can you explain the purpose of finding general solution and particular solutions for linear difference equation? $\endgroup$ – ilovetolearn May 5 '11 at 11:01
  • $\begingroup$ @liang The purpose is that you find a general solution for a simpler equation and a particular solution for the complicated equation to arrive at the general solution for the complicated equation. $\endgroup$ – Phira May 5 '11 at 11:17
  • $\begingroup$ @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. $\endgroup$ – Dennis Gulko May 5 '11 at 11:32
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Américo Tavares: why one gets a cubic characteristic polynomial for the first equation? $\endgroup$ – Fabian May 5 '11 at 11:56
  • $\begingroup$ @Fabian: It was my big mistake. I will correct it. Many thanks! $\endgroup$ – Américo Tavares May 5 '11 at 11:58
  • $\begingroup$ my try at Q2 after the explanations. Please pardon the mistake if there are any. characteristic equation: $$ x^2 - x - x = 0 $$ $$ (x+1)(x-2) = 0 $$ $$ x = -1, 2 $$ General solution $$ A_n = A_1(-1)^n + A_2(2)^n $$ Now $$ a_0 = 2, a_1 = 4 $$ $$ a_0 = A_1 (-1)^0 + A_2(2)^0 $$ $$ A_1 + A_2 = 2 $$ $$ A_1 = A_1(-1)^1 + A_2(2)^1 $$ $$ 4+2 = -K_1 + 2K_2 + K_1 + K_2 $$ $$ 6 = 3K_2 $$ So $$ K_1 = 0, K_2 = 2 $$ Hence $$ A_n = 0(-1)^n + 2(2)^n $$ $$ A_n = 2(2)^n $$ Please pardon if there any mistakes $\endgroup$ – ilovetolearn May 5 '11 at 12:12
  • $\begingroup$ The independant term is -2. The characteristic equation is $x^2-x-2=0$, which is equivalent to $(x+1)(x-2)=0$. I used the variable $\lambda$ instead. $\endgroup$ – Américo Tavares May 5 '11 at 12:15
  • $\begingroup$ @Américo Tavares: Noted. Your explanation is quite similar to the textbook examples. $\endgroup$ – ilovetolearn May 5 '11 at 12:24
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.