Non-homogeneous recurrence relation

Question

For the recurrence :

$$ a_{n} = 3a_{n-1} - 2a_{n-2} + F(n) $$

find the particular solution when F(n) is

a) $ 2^{n} $

b) $ 2^{n}(n+1) $

c) $ 2^{n} + n+1 $

Try:

I have just finished homogeneous system and tried to cover non-homogeneous of my own.

I have found the roots of the equation and got as 1 and 2.

For part a): I have found that every relation like this will have a solution of the form

$a_{n} = a_{n}^{h} + a_{n}^{p} $ where the term with h is the solution of the homogeneous relation.

I have found $a_{n}^{h}$ . Can someone help me with the $a_{n}^{p}$ and the other 2 parts.

Answer 1

When $F(n)$ is an expression containing $r^n$ and $r$ is a root of the characteristic equation, a particular solution like $r^n$ will not do as it belongs to the set of homogeneous solutions. Instead, you have to make an ansatz like $nr^n$.

Let's try this for part a). We do $a_n^p = An2^n$, for some constant $A$. Substituting into the recurrence relation, we get $$An2^n = 3A(n-1)2^{n-1}-2A(n-2)2^{n-2}+2^n.$$ Dividing through by $2^{n-2}$, we get $$4An=6An-6A-2An+4A+4$$ which simplifies to $A=2$. Thus $a_n^p = n2^{n+1}$ is a particular solution. The full solution is $a_n = a_n^h+a_n^p$. Just plug in your initial conidtions (if you have any) into this expressions, to get your final solution.

In part b), try the ansatz $a_n^p = (An^2+Bn)2^n$

You should get $A=B=1$.

Answer 2

These nonhomogeneous equations are just homogeneous equations in disguise. I'll show you with part (b):

$$a_n = 3~a_{n - 1} - 2~a_{n - 2} + 2^n~(n + 1) \tag{T1}$$

There are 2 nonlinear coefficients, $n~2^n$ and $2^n$, so we need 3 equations to eliminate them:

$$\begin{align} % a_{n + 2} - 3~a_{n + 1} + 2~a_{n + 0} &= n~2^n + 2^n \\ % a_{n + 3} - 3~a_{n + 2} + 2~a_{n + 1} &= 8~n~2^n + 32~2^n \\ % a_{n + 4} - 3~a_{n + 3} + 2~a_{n + 2} &= 16~n~2^n + 80~2^n % \end{align}$$

Now eliminate the $2^n$ and $n~2^n$ terms the normal way:

$$a_{n + 4} - 7~a_{n + 3} + 18~a_{n + 2} - 20~a_{n + 1} + 8~a_{n} = 0 \tag{T2}$$

And this is equivalent to your original equation. The characteristic equation of (T1) is

$$P(x) = x^2 - 3~x + 2 = 0$$

and the characteristic equation of (T2) is

$$Q(x) = x^4 - 7~x^3 + 18~x - 20~x + 8 = 0$$

As it turns out with this technique, $P(x)$ is always a factor of $Q(x)$, specifically:

$$Q(x) = (x^2 - 4~x + 4)P(x)$$

which makes finding the roots fairly easy. No guessing needed. You can even use this when $F(n)$ contains other "closed under addition" terms like sine, cosine, arbitrary products of powers and polynomials, and so forth.