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

Question

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.

Answer 1

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

Answer 2

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?

Answer 3

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

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