# Find the solution to the following non-homogenous recurrence relation:

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?

-
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

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

-

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?

-

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

-

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

-
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