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 $


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.

  • 1
    $\begingroup$ For linear recursions with constant coefficients, an inhomogenous part of $r^n$ gives solutions of the form $(an + b)r^n$. Similarily, $nr^n$ gives solutions of the form $(an^2 + bn + c)r^n$. $\endgroup$ – Arthur Mar 2 '16 at 23:49

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

| cite | improve this answer | |
  • $\begingroup$ I got it what you are trying to say. So, for part c) do I have to divide it into 3 separate terms containing $2^{n}$, n and 1? $\endgroup$ – max Mar 2 '16 at 23:57
  • $\begingroup$ @max Ok, great! I seem to have forgotten part c). For the term $2^n$ you should be able to take the solution from $a)$. For the $n+1$ term, consider the ansatz $An^2+Bn+C$. $\endgroup$ – Étienne Bézout Mar 3 '16 at 0:01
  • $\begingroup$ Thank you so much for helping me out. I will be posting the final solution here in a while. Please check it as my book doesn't have any answers :) $\endgroup$ – max Mar 3 '16 at 0:02
  • $\begingroup$ @max No problem! I saw that I had made a mistake. In part b), it should be $A=B=1$. $\endgroup$ – Étienne Bézout Mar 3 '16 at 0:19
  • $\begingroup$ @max I'm afraid I have to log out. You can check your answers here if you like: wolframalpha.com/input/…. I have entered part c) as an example. $\endgroup$ – Étienne Bézout Mar 3 '16 at 0:21

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.

| cite | improve this answer | |

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.