# HELP with Particular solution in the non-homogeneous recurrence relation

• May 3rd 2009, 02:41 PM
sanorita_belle
HELP with Particular solution in the non-homogeneous recurrence relation
Find the solution of the recurrence relation $a_{n} = 2a_{n-1} + 2n^2$ with initial condition a1 = 4.

As this is the linear non-homogeneous recurrence relation which has a general solution in the form of an = h(n) + p(n).

I tried solving the h(n), homogeneous part first $a_{n} = 2a_{n-1}$.

I got $h(n) = A2^n$ , for some constant A.

• May 3rd 2009, 04:57 PM
Soroban
Hello, sanorita_belle!

Quote:

Find the solution of the recurrence relation: . $a_n \:=\: 2a_{n-1} + 2n^2$
with initial condition $a_1 = 4$

This is a linear non-homogeneous recurrence which has a general solution
of the form: . $a_n \:=\: h(n) + p(n)$

I tried solving the $h(n)$, homogeneous part first: . $a_n \:=\: 2a_{n-1}$

I got: . $h(n) = A\!\cdot\!2^n$, for some constant $A.$ . . . . Good!

But now i am confused about the particular solution $p(n).$
How do i find that?

I don't know the procedure you were taught, but I can guess . . .

You might conjecture that the particular solution is a quadratic ...
. . of the form: . $p(n) \:=\:Bn^2 + Cn + D$

I was taught a different approach . . . quite long and tedious . . .

. . and came up with: . ${\color{blue}a_n \;=\;13\!\cdot\!2^n - 2(n^2 + 4n + 6)}$

. . which cranks out the first few terms: . $4,\: 16,\: 50,\: 132,\; \hdots$

• May 3rd 2009, 09:08 PM
sanorita_belle
Thanks Soroban, Can you please provide the way you learned it? It would be a great help!
• May 3rd 2009, 10:26 PM
Soroban
Hello, sanorita_belle!

For the sake of anyone looking on, here it is.

I warned you that this long and tedious . . .

Quote:

Find the solution of the recurrence relation: . $a_n \:=\: 2a_{n-1} + 2n^2,\;\;a_1 = 4$
We can reduce this to a homogeneous relation ... eventually.

$\begin{array}{ccccc}
\text{previous term:} & a_{n=1} &=& 2a_{n-2} + 2(n-1)^2 & [1] \\
n^{th}\text{ term:} & a_n &=& 2n_{n-1} + 2n^2 & [2] \end{array}$

Subtract [2] - [1]: . $a_n-a_{n-1} \:=\:2a_{n-1} - 2a_{n-2} + 2n^2 - 2(n-1)^2$

$\begin{array}{cccccc}\text{We have:} &a_n - 3a_{n-1} + 2a_{n-2} &=& 4n-2 & [3] \\ \text{Next term:} & a_{n+1} - 3a_n + 2a_{n-1} &=& 4(n+1)-2 & [4] \end{array}$

Subtract [4] - [3]: . $a_{n+1} - a_n - 3a_n + 3a_{n-1} + 2a_{n-1} - 2a_{n-2} \:=\:[4(n-2)-2] - (4n-2)$

$\begin{array}{cccccc}\text{We have:} & a_{n+1} - 4a_n + 5a_{n-1} - 2a_{n-2} &=& 4 & [5] \\
\text{Next term:} & a_{n+2} - 4a_{n+1} + 5a_n - 2a_{n-1} &=& 4 & [6] \end{array}$

Subtract [6] - [5]: . $a_{n+2} - 5a_{n+1} + 9a_n - 7a_{n-1} + 2a_{n-2} \:=\:0$ . . . There! .Homogeneous!

Let $X^n \:=\:a_n$

We have: . $X^{n+2} - 5X^{n+1} + 9X^n - 5X^{n-1} + 2X^{n-2} \:=\:0$

Divide by $X^{n-2}\!:\quad X^4 - 5X^3 + 9X^2 - 7X + 2 \:=\:0$

Lucky for us, this factors: . $(X-1)^3(X-2) \:=\:0$

. . which has roots: . $X \;=\;1,1,1,2$

So the function is: . $f(n) \;=\;A(1^n) + Bn(1^n) + Cn^2(1^n) + D(2^n)$

. . That is: . $f(n) \;=\;A + Bn + Cn^2 + D\cdot2^n$ .(a)

The first four terms of the sequence are: . $4,\:16,\:50,\:132$
. . Substitute these values into (a).

$\begin{array}{ccccc}f(1) = 4 & A + B + C + 2D &=& 4 & [1] \\
f(2) = 16 & A + 2B + 4C + 4D &=& 16 & [2] \\
f(3) = 50 & A + 3B + 9C + 8D &=& 50 & [3] \\
f(4) = 132 & A + 4B + 16C + 16D &=& 132 & [4] \end{array}$

$\begin{array}{ccccc}\text{Subtract [2] - [1]:} & B + 3C + 2D &=& 12 & [5] \\ \text{Subtract [3] - [2]:} & B + 5C + 4D &=& 34 & [6] \\
\text{Subtract [4] - [3]:} & B + 7C + 8D &=& 82 & [7] \end{array}$

$\begin{array}{ccccc}\text{Subtract[6] - [5]:} & 2C + 2D &=& 22 & [8] \\ \text{Subtract [7] - [6]:} & 2C + 4D &=& 48 & [9] \end{array}$

$\text{Subtract [9] - [8]: }\;\;2D \:=\:26 \quad\Rightarrow\quad\boxed{ D \:=\:13}$

Back-substitute and get: . $\boxed{C \:=\:\text{-}2} \quad\boxed{ B \:=\:\text{-}8} \quad \boxed{A \:=\:\text{-}12}$

Therefore: . $f(n) \;=\;-12 - 8n - 2n^2 + 13\!\cdot\!2^n$

I need a nap . . .
.
• May 3rd 2009, 10:31 PM
sanorita_belle
THANKSSSS ALOT SOROBAN for all the time you spent on this question, I really appreciate it. You are the BEST :)

This makes much more sense than what i learned in-class, thanks once again :)