Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Find the solution to the following non-homogenous recurrence relation: $a_{n+2} + a_{n+1} - 2a_n = n$ for $a_0 = 1$, $a_1 = -2$

I have found the homogenous part with the characteristic polynomial is $a_n = C_1(-2)^n + C_2$ but don't know how to find the non-homogenous part?

Thanks in advance.

share|improve this question
    
Oops sorry, it was a non-homogenous recurrence relation I was wanting to solve, I'll edit that. It was because it is a recurrence relation I was getting confused.. –  yhu Oct 21 '13 at 18:22
    
I don't know how to derive a particular solution for the non-homogenous part, but I do know that since $n$ is linear, a general quadratic term would be a good guess. Substituting it back in, you can then easily verify that it works and find the coefficients. –  David H Oct 21 '13 at 18:29

4 Answers 4

Here is a solution using generating functions. Put $$A(z) = \sum_{n\ge 0} a_n z^n$$ and multiply the recurrence $$a_{n+2}+a_{n+1}-2a_n = n$$ by $z^{n+2}$ and sum over $n\ge 0$ to get $$\sum_{n\ge 0} a_{n+2} z^{n+2} + \sum_{n\ge 0} a_{n+1} z^{n+2} - 2\sum_{n\ge 0} a_n z^{n+2} = \sum_{n\ge 0} n z^{n+2}.$$ This gives $$A(z) - a_1 z - a_0 + z (A(z) - a_0) - 2 z^2 A(z) = \sum_{n\ge 1} n z^{n+2}.$$ Further simplification yields $$ A(z) ( 1 + z - 2 z^2) - (a_0+a_1) z - a_0 = z^3 \sum_{n\ge 1} n z^{n-1} = z^3 \frac{1}{(1-z)^2}.$$ Solve this for $A(z)$ and subsitute the values $a_0 = 1$ and $a_1 = -2$ to get $$ A(z) =-{\frac {7}{9}}\, \left( -1+z \right) ^{-2}-{\frac {13}{27}}\, \left( -1+z \right) ^{-1}+{\frac {26}{27}}\, \left( 2\,z+1 \right) ^{-1}-1/3\, \left( -1+z \right) ^{-3 }.$$ Now we can read off the coefficients, which are $$ -\frac{7}{9} (n+1) + \frac{13}{27} + \frac{26}{27} (-2)^n + \frac{1}{3} \frac{1}{2} (n+1)(n+2)$$ which gives $$a_n = \frac{26}{27} (-2)^n + \frac{1}{6} n^2 - \frac{5}{18} n + \frac{1}{27}.$$

share|improve this answer

For every $x=(x_n)$, define $L(x)=y$ by $y=(y_n)$ with $y_n=x_{n+2}+x_{n+1}-2x_n$. One knows that $L(u)=L(v)=0$ where $u=(u_n)$, $v=(v_n)$, $u_n=(-2)^n$ and $v_n=1$ for every $n$.

One wants to solve $L(a)=c$ where $c=(c_n)$ and $c_n=n$ for every $n$. Let $w=(w_n)$ where $w_n=n^2$ for every $n$. Note that $L(c)=3$ and $L(w)=6c+5$.

Thus, $L(3w-5c)=18c$ hence $L(\lambda u+\mu v+\frac16w-\frac5{18}c)=$ $____$ for every scalar $(\lambda,\mu)$.

Can you finish?

share|improve this answer

One way is to find a difference equation that is solved by the function $n \mapsto n$. If $b_n = n$, we see that $b_{n+1}-b_n = 1$ and so $b_{n+2}-2 b_{n+1} + b_n = 0$, with $b_0 = 0, b_1 = 1$.

Now let $x_n= (a_{n+1}, a_n, b_{n+1}, b_n)^T$, then we are looking for a solution to $x_{n+1} = A x_n$ where $A = \begin{bmatrix} -1 & 2 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 2 & -1 \\ 0 & 0 & 1 & 0\end{bmatrix}$, and $x_0=(-2,1,1,0)^T$. We note that $A$ has an eigenvalue of multiplicity $3$ at $\lambda=1$ and an eigenvalue of multiplicity $1$ at $\lambda = -2$.

The solution is $x_n = A^n x_0$. Rather than evaluating $A^n$ explicitly, since we are only interested in $a_n = e_2^T A^n x_0$, we use the eigenstructure of $A$ and assume that $a_n = C_1 (-2)^n + C_2 + C_3 n + C_4 n^2$. Since we know $a_0,a_1,a_2,a_3$, this gives four equations in $C_1,...,C_4$. Solving the equations gives $C_1 = \frac{32}{27}, C_2 = - \frac{5}{27}, C_3 = \frac{7}{18}, C_4 = \frac{1}{6}$, and so $a_n = -\frac{{\left( -2\right) }^{n+5}}{27}+\frac{{n}^{2}}{6}+\frac{7\,n}{18}-\frac{5}{27}$.

share|improve this answer

Hint: The general solution of a non-homogenous recurrence relation is equal to the sum of the general solution of a homogenous recurrence relation and a partial solution of a non-homogenous recurrence relation. So you have only to find the last.

I corrected the rest of the text:

If the right side of the given equation is a polynomial in $n$ of degree $m$ then a partial solution can be found in the form $a_n = n^rf(n)$ where $f(n)$ is a polynomial in $n$ of degree $m$ and $r$ is the multiplicity of the root $1$ of the characteristic equation (in your case $r=1$). Substitute it in your equation and find $f(n)$.

share|improve this answer
    
So I think I understand I set the particular solution of the $a_(n) = A n + B n^2$, substituting this in the recurrence relation gives: $A(n+2) + B(n+2)^2 + A(n+1) + B(n+1)^2 - 2An - 2Bn^2 = n$ Equating equal powers of n, then solving for $A$ and $B, $B + B - 2B = 0, A + 4 B + A + 2 B - 2 A = n$ i.e. $6 B = 1$, so $B = 1/6, also 2 A + 4 B + A + B = 0 so 3 A = - 5 B , A = (1/3) (-5/6) = -5 /18$ So $a_(n) = - 5/18 n + 1/6 n^2$ So the general solution is $a_(n) = - 5/18 n + 1/6 n^2 + c1 + c2 (-2)^n$ –  yhu Oct 21 '13 at 20:00
    
The I set $a_0 = 1, a_1 = -2$ and solved to get $a_n = -5/18n + 1/6(n^2)+ 1/27 + 26/27(-2)^n$. But this solution looks messy,do you mind checking please? –  yhu Oct 21 '13 at 20:04
    
Sorry, I mistaked: a partial solution has a form $(An+B)n$ (the multiplier $n$ appears because the charasteric equation has a root $1$), in final form $\frac{1}{6}n^2-\frac{5}{18}n$. –  Boris Novikov Oct 21 '13 at 22:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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